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

一、单项选择题

1． 在下列存储形式中，哪一个不是树的存储形式？（ ）

A. 双亲表示法

B. 孩子链表表示法

C. 孩子兄弟表示法

D. 顺序存储表示法

【答案】D

【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。

2． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法时间复杂度是（ ）。 A. B. C. D.

【答案】C 。

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,

查找每个顶点的邻接点所需时间为

, 其中n 为图中顶点数。而当以邻接表作图的存储结构时, 找邻接点所需时间为0(e), 其中e 为无向图中边的数或有向图中弧的数。由此, 当以邻接表作存储结构时, 深度优先搜索遍历图的时间复杂度为。即可得出正确答案。

3． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）.

(1)父子关系

(2)兄弟关系

(3)U的父结点与V 的父结点是兄弟关系

A. 只有(1)

B.(1)和(2)

C.(1)和(3)

d.(1)、(2)和(3)

【答案】B

【解析】首先，在二叉树中，若结点U 是结点v 的父结点的父结点，那么u 和v 的关系有如下4种情况：

接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系. 其中： 情况(1)，在原来的森林中u 是v 的父结点的父结点；

情况(2)，在森林中u 是v 的父结点；

情况(3)，在森林中u 是v 的父结点的兄弟；

情况(4)，在森林中u 与v 是兄弟关系.

由此可知，题目中的(1)、(2)是正确的.

4． 对下图进行拓扑排序, 可以得到不同的拓扑序列的个数是（ ）。

图

A.4

B.3

C.2

D.1

【答案】B

【解析】拓扑排序的步骤为:

(1)在有向图中选一个没有前驱的顶点并且输出它;

(2)从图中删除该顶点和以它为尾的弧。重复上述两步, 直至全部顶点均已输出。由于没有前驱的顶点可能不唯一, 所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑排序序列, 分别为abced , abecd , aebcd 。

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

A.80

B.320

C.80K

D.320K

【答案】A

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

个

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

所以需要簇的个数为

个

6． 下列选项中，导致创建新进程的操作是（ ）.

(1)用户登录成功

(2)设备分配

(3)启动程序执行

A. 仅(1)和(2)

B. 仅(2)和(3)

C. 仅(1)和(3)

D. (1)、(2)和(3)

【答案】C

【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是(2).考察一个进程创建的过程是这样的:当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填写PCB 表创建进程. 通常填写PCB 表的过程有一段时间(主要涉及资源分配需要协调），许多操作系统为此设立了一个中间状态称为“初始化”，也有的操作系统不设这个中间状态. 此时操作系统填写进程ID 号、处理机参数、进程参数(状态、特权、优先级) 、分配内存(若是虚拟存储就分配虚拟地址) 、映射文件等，一切就绪，将控制权交给系统进行下一步调度. 设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C.