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

一、填空题

1． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

2． G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

3． 求最短路径的Dijkstra 算法的时间复杂度为_____。

【答案】

4． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

5． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

6．

=_____

【答案】5

7． 完善算法：求KMP 算法.next 数组。

END ； 【答案】

8． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为

9． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树 【解析】二叉排序树

或者是一棵空树，或者是具有下列性质的二叉树：①若它

的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

10．已知一循环队列的存储空间为其中队头和队尾指针分别为front 和rear , 则此循环队列判满的条件是（ ）

【答案】

二、选择题

11．n 个结点的完全有向图含有边的数目（ ）。

A.n*n

B.n （n+l） C.n/2

D.n*（n-l ）

【答案】D

【解析】在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n 的无向图，最多有

条边。如是有向图，需要在无向图的最多边的基础上乘以2，则

为n （n-l ）。

12．在下述结论中，正确的有（ ）。

①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换，④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A. ①②③ B. ②③④ C. ②④ D. ①④ 【答案】D

【解析】只有根节点的二叉树的度为0，二叉树的左右子树隐含着他们的位置关系。因此，

②③均错。

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

A. B. C. D. 【答案】D

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

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

用户登录成功

设备分配

启动程序执行 A.

仅

和B.

仅

和C.

仅

和D.

和

【答案】C

【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间（主要涉及资源分配需要协调），也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”

统填写进程ID 号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。

15．设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。