数据结构每日一题 2020 Nov

目录

• 数据结构每日一题 2020 Nov
  • 目录
  • 1. Week 1
    • 1.1. 快速排序
    • 1.2. 共享资源
    • 1.3. SPOOLing系统
    • 1.4. 批处理系统
    • 1.5. 分布式操作系统
    • 1.6. Cache
    • 1.7. 信号量机制
  • 2. Week 2
    • 2.1. 用户态线程
    • 2.2. 段式存储的逻辑地址
    • 2.3. 递归时间复杂度
    • 2.4. 连通图
    • 2.5. 二叉树遍历
    • 2.6. 完全二叉树
    • 2.7. 时间复杂度
  • 3. Week 3
    • 3.1. 顺序表的存储
    • 3.2. 基数排序
    • 3.3. 归并排序
    • 3.4. 循环队列
    • 3.5. 图的邻接矩阵表示
    • 3.6. 双向链表的优点

1. Week 1

1.1. 快速排序

对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是 [中国科学院大学]

A．70，75，82，90，23，16，10，68

B．70，75，68，23，10，16，90，82

C．82，75，70，16，10，90，68，23

D．23，10，16，70，82，75，68，90

答案

答案：A
解析：快速排序第一趟划分的方法是：将第1个元素放在最终排好序列的最终位置上，则在这个位置右边小于该元素值的元素都移到其左边，则在这个位置左边小于该元素值的元素都移到其右边。故选A。

1.2. 共享资源

设计某一资源造成与时间有关的错误的原因，正确的是 ［南京理工大学］

A. 一个进程多次申请，释放该资源

B. 若干并发进程互斥使用该资源

C. 若干并发进程同时使用该资源

D. 以上说法均不对

答案

答案：C
解析：本题考查进程互斥、同步及资源分配的相关知识。由于某一资源造成与时间有关的错误，意思是在时间上对同一资源的竞争而产生的错误，在一个进程占用该资源时，另一进程希望能得到该资源，而该资源在此刻又不能同时为两个进程共享而造成的错误。若干并发进程互斥使用该资源时，系统采用了P、 V操作对其资源进行管理，不会产生错误。当若干个并发进程需要同时使用该资源，而资源有限时，就会成为系统正常运行的瓶颈。

1.3. SPOOLing系统

下面四个选项中不属于SPOOLing系统特点的是 ［电子科技大学］

A. 提高了内存的利用率

B. 提高了I/O操作的速度

C. 将独占设备改造为共享设备

D. 实现了虚拟设备功能

答案

答案：A
解析：SPOOLing是外部设备联机并行操作，很明显它跟内存没有什么直接的关系。SPOOLing:将一台物理I/O设备虚拟为多台逻辑I/O设备，同样允许多个用户共享一台物理I/O设备，其特点有：
(1)提高了I/O速度。
(2)将独占设备改造为共享设备。
(3)实现了虚拟设备功能。

1.4. 批处理系统

在不同类型的操作系统中，批处理操作系统的主要缺点是 ［南京理工大学］

A. CPU利用率低

B. 不能并发执行

C. 缺少交互性

D. 周转时间太长

答案

答案：C
解析：批处理系统的设计其目标是加大吞吐量，减少周转时间。为达到此目的，系统一般要尽可能地提高CPU利用率，并采用多道并发程序设 计，而与用户的交互不在其考虑范围之内，此问题交由交互式操作系统来解决。

1.5. 分布式操作系统

分布式操作系统与网络操作系统本质上的不同之处在于 ［南京理工大学］

A. 实现各台计算机之间的通信

B. 共享网络中的资源

C. 满足较大规模的应用

D. 系统中若干台计算机相互协作完成同一任务

答案

答案：D
解析：分布式操作系统和网络操作系统的本质区别在于：分布式操作系统能使系统中若干计算机相互协作完成一个共同的任务。这使得各台计算 机组成一个完整的、功能强大的计算机系统，网络操作系统则没有共同协作这个功能。

1.6. Cache

在页式存储管理系统中，当一道程序占有处理机时，应将它的地址送入 ，然后程序才开始执行。［中国科学技术大学］

A. 相连存储器 associative memory）

B. 主存储器（main memory）

C. 后备存储器（backing store）

D. I/0缓冲区（I/O buffer）

答案

答案：A
解析：为了提高地址变换的速度，可在地址变换机构中增设一组数量不多的寄存器，把它作为高速缓冲存储器 Cache）即通过硬件技术，又称 为“联想存储器”或“快表”。即快表的概念，是与相连存储器的使用紧密相连的。当使用快表时，就要输入相连存储器。

1.7. 信号量机制

如果有4个进程共享同一程序段，每次允许2个进程进入该程序段,若用信号量PV操作作为同步机制，则信号量S为-1时表示什么？（中国科学院大学2017年）

A. 有2个进程进入了该程序段

B. 有1个进程在等待

C. 有2个进程进入了程序段,有1个进程在等待

D. 有1进程进入了该程序段，其余3个进程在等待

答案

答案：C
解析：同步信号量S初始值设置为2，表示还有两个进程可以进入该程序段。信号量S为-1时，有一个程序段尝试进入该程序段，其中两个进程进入，一个进程在等待进入。

2. Week 2

2.1. 用户态线程

与内核态线程相比，用户态线程的优点不包括 （中国科学院大学 2017年）

A. 线程切换不需要转换到内核空间

B. 可以采用定制的调度算法

C. 可以避免系统调用引起进程阻害

D. 实现与操作系统平台无关

答案

答案：C
解析：对一个进程而言，其所有线程的管理数据结构均在该进程的用户空间中，管理线程切换的线程庠也在用户地址空间运行，因此进瘟不必切模到内核方式来做线程管理，A正确：在不干扰OS调度的情况下，不同的进程可以根据自身需要选择不同的调度算法，对自己的线程进行管理和调度，B正确；用户级线程的实现与OS平台无关，因为对于线程管理的代码是属于用户程序的一部分，所有的应用程序辱可以对之进行关享。用户级线程甚至可以在不支持线程机制的操作平台上实现，D正确。
操作系统内核不知道多线程的存在，因此一个线程阻塞将使得整个进程（包括它的所有线程）阻塞。

2.2. 段式存储的逻辑地址

段式存储管理的逻辑地址是_____（北京航空航天大学2015）

A. 一维线性的

B. 二维的

C. 三维的

D. 由操作系统决定的

答案

答案：B
解析：在段式存储管理中，每个段地址的说明为两个量：一个段名和一个位移。在段内，是连续完整存放的。而在段与段之间是不一定连续编址的。段名和位移构成了一种二维编址。

2.3. 递归时间复杂度

设计一个递归函数按n!=n*(n-1)！计算n!，则其时间复杂度为_____。 （南开大学2013）

A. O(log2n)

B. O(n)

C. O(n2)

D. O(n!)

答案

答案：B
解析这是一个递归过程，可以看出每递归一次n的规模小一，所是结果是线性的。

2.4. 连通图

若具有n个定点的连通图采用邻接矩阵表示，则该矩阵中的非零元素至少是____（北京航空航天大学2015）

A．2（n-1）

B.n-1

C．n+1

D. n/2

答案

答案：A
解析：如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。所谓连通图一定是无向图,有向的叫做强连通图 连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树 由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次（也就是说是对称矩阵）,因此至少有2(n-1)个非零元素。

2.5. 二叉树遍历

设某颗二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为_（中国科学院大学2012）

A. BADC

B. BCDA

C. CDAB

D. CBDA

答案

答案：A
解析：通过中序遍历和前序遍历可以将树构建出来，再求其后序遍历结果。前序遍历（先根排序），故C为根节点，再看中序遍历可知，AB为C的左子树，D为其右子树。AB - C - D。前序遍历第二个节点为A，则A为根节点，再看中序遍历B在A后面，则B为右子树，最终构建树，后序遍历结果为：BADC。

2.6. 完全二叉树

某完全二叉树的第六层有24个叶结点，则该完全二叉树的结点总数最大为____（北京航空航天大学2016）

A. 78

B. 79

C. 80

D. 81

答案

答案：B
解析：完全二叉树第六层叶结点为24，树的高度可以为6或7，显然为7的情况下结点总数最多，结点总数为2的7次方减1再减去24乘2，即128-1-48=79个。

2.7. 时间复杂度

某算法的时间复杂度为O(n^2)，表明该算法的 。（武汉大学 2006年）

A．问题规模是n^2

B．执行时间等于n^2

C．执行时间与n^2成正比

D．问题规模与n^2成正比

答案

答案：C
解析：时间复杂度为O(n^2)，说明算法的执行时间T(n)≤c×n^2（c为比例常数），即T(n)=O(n^2)，时间复杂度T(n)是问题规模n的函数，其问题规模仍然是n而不是n^2。

3. Week 3

3.1. 顺序表的存储

一个顺序表所占用的存储空间大小与 无关。（北京航空航天大学 2004年）

A．表的长度

B．元素的存放顺序

C．元素的类型

D．元素中各字段的类型

答案

答案：B
解析：顺序表是线性表的数组存储表示，占用的存储空间大小与元素存放顺序无关。

3.2. 基数排序

对给定的关健字序列321, 156 , 057 , 046, 028 , 331, 033,采用最低位优先进行基数排序，则第2趟分配收集后得到的关健字序列是 。

A. 321, 331, 033 , 057 , 028, 156 , 046

B. 033, 028, 046, 057, 156, 321, 331

C. 321, 028, 331, 033, 046, 156, 057

D. 321, 028, 331, 033, 046, 057, 156

答案

答案：C
解析：根据最低位优先的基数排序，第一趟比较个位之为321,331,033,156,046,057,028,第二趟比较十位之后为321,028,331,033,046,156,057。

3.3. 归并排序

若对27个元素只进行3趟多路归并排序，则选取的归并数为 。（中国科学院大学 2017）

A. 2

B. 3

C. 4

D. 5

答案

答案：B
解析：设进行K路归井排序，则27/K向上取整为第一次归并后子表数；再/K向上取整得第二次归井后子表数，再/K向上取整=1；所以选B。

3.4. 循环队列

若用一个大小为5的数组实现循环队列，且当前rear和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素，再删除一个元素后，rear和front的值分别为 。（中国科学院大学 2018年）

A. 2和4

B. 3和0

C. 2和0

D. 4和1

答案

答案: C
解析: 队列删除元素只能在队首，而添加元素只能在队尾。对于循环队列而言，rear在0，front 在3，则4、5是元素所在的位置。删除元素，front在4；加入两个元素，rear在2，再删除一个元素，front在0。

3.5. 图的邻接矩阵表示

若图的邻接矩阵中主对角线上的元素皆为0，其余元素全为1，则可以断定该图一定 。（北京航空航天大学 2004年）

A．是无向图

B．是有向图

C．是完全图

D．不是带权图

答案

答案: C
解析: 图的邻接矩阵对角线元素必为0，其余元素全为1代表任何两个顶点之间都存在边，也就是完全图。

3.6. 双向链表的优点

与单链表相比较，双向链表的优点之一是 。（北京航空航天大学 2005年）

A．可以省略头结点指针

B．可以进行随机访问

C．插入、删除操作更简单

D．顺序访问相邻结点更灵活

答案

答案：D
解析：A错，双向链表也可以有头指针。B是顺序存储的特点。C与单链表相比，双向链表增加了指针数量，使得插入、删除操作更麻烦。D正确，因为双向链表即可以访问前驱结点，也可以访问后继结点。

在非空双向循环链表中q所指的链接点前面插入一个由p指的链接点的过程是依次执行语句p->rlink=q；p->llink=q->llink；q->llink=p； 。（北京航空航天大学 2007年）

A．q->rlink->llink=p；

B．q->llink->rlink=p；

C．p->rlink->llink=p；

D．p->llink->rlink=p；

答案

答案: D
解析: 执行完以上三步之后，只需要再将原线性表前面结点的rlink指向p即可，即p->llink-> rlink=p。