当前位置：问答库＞考研试题

一、单项选择题

1． 下列选项中, 满足短任务优先且不会发生饥饿现象的调度算法是（ ）。

A. 先来先服务

B. 高响应比优先

C. 时间片轮转

D. 非抢占式短任务优先

【答案】B

【解析】分析该题目可以看到, 本题所提到的问题是涉及短任务调度也就是属于作业调度, 因此首先排除时间片轮转算法; 因为作业调度算法中没有时间片轮转的算法。其次, 因为问题提到短任务, 则先来先服务的算法也可以排除了, 它与短任务无关。剩余高响应比优先算法和非抢占式短任务优先是哪一个？我们可以通过分析得到, 非抢占式短任务优先算法不能解决饥饿问题, 因为当一个系统短任务源源不断到达是, 长任务必然会得不到调度, 产生饥饿。而解决此方法的最好方式就是采用计算响应比的方法, 并以高响应比值优先调度。这样, 无论短任务或长任务, 均可以得到调度, 而且, 较短任务会得到优先的调度。故满足短任务优先且不会发生饥饿现象的调度算法只有高响应比优先算法。

2． 系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。

A.2

B.3

C.4

D.8

【答案】B

【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框, 题中访问过程中页框的变化如下:

访问页号为7的页时, 内存中存在的页的页号是:3、8、4和5, 根据LRU 定义应淘汰的是3。

3． 若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ）

A.h , c , a , b , d , e , g , f

B.e , a , f , g , b , h , c , d

C.d , b , c , a , h , e , f , g

D.a , b , c , d , h , e , f , g

【答案】D

【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。

4． 现有容量为10GB 的磁盘分区, 磁盘空间以簇(duster)为单位进行分配, 簇的大小为4KB , 若采用位图法管理该分区的空闲空间, 即用一位(bit)标识一个簇是否被分配, 则存放该位图所需簇的个数为（ ）

A.80

B.320

C.80K

D.320K

【答案】A

【解析】磁盘的簇的个数为:

个

而一个簇的位示图能管理的簇的个数为:

所以需要簇的个数为

个

5． 下列关于最小生成树的叙述中, 正确的是（ ）。

Ⅰ. 最小生成树的代价唯一

Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同

IV. 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅲ

D. 仅Ⅱ、Ⅳ

【答案】A 。

【解析】当图中存在相同权值的边时, 其最小生成树可能是不唯一的, 但最小生成树的代价一定是相同的, 所以说法Ⅰ正确。从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路, 所以说法Ⅱ错误。

当某个顶点有权值相同的边, 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树并不一定相同, 所以说法Ⅲ错误。当最小生成树不唯一时, 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树可能相同, 也可能不同, 所以说法Ⅳ错误。由此可得出正确答案。

6． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0, 右孩子的平衡因子为1，则应作（ ）型调整以使其平衡

A.LL

B.LR

C.RL

D.RR

【答案】C

【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2. 则需要进行两次旋转(先右旋后左旋) 。

7． 对矩阵压缩存储是为了（ ）。

A. 方便运算

B. 方便存储

C. 提高运算速度

D. 减少存储空间

【答案】D

【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。

8． 最大容量为n 的循环队列，队尾指针是rear ，队头:front ，则队空的条件是（ ）。

A.(rear+1)MODn＝front

B.rear ＝front

C.rear+1＝front

D.(rear-1)MODn＝front

【答案】B

【解析】循环队列队空的条件是:rear ＝front 。循环队列队满的条件，

通常采用(rear+1)%MAXQSIZE＝front 来判定队满，其中MAXQSIZE 表示队列的长度。

9． 直接插入排序在最好情况下的时间复杂度为（ ）。 A.