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

一、填空题

1． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

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

【答案】

3． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

4． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。

【答案】度；出度

5． 已知如下程序段:

语句1执行的时间复杂度为_____:语句2执行的时间复杂度为_____:语句3执行的时间复杂度为_____:语句4执行的时间复杂度为_____。

【答案】(1)n＋1 (2)n

(3)n(n＋3)/2 (4)n(n＋l)/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋(n＋l) 加起来就是n(n＋3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n(n＋l)/2。

6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

7． 应用prim 算法求解连通网络的最小生成树问题。

(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值

)

(2)下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在

图的顶点数，应由用户定义

用二维数组作为邻接矩阵表示

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

从顶点rt 出发构造图G 的最小生成树T , rt 成为树的根结点

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

选具有最小权值的候选边

图不连通，出错处理

修改候选边集合

中

【答案】(1)

(2)

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设是N 上最小生成树边的集合。算法从属于

的边为止。

8． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

9． 外排序的基本操作过程是_____和_____。

【答案】生成有序归并段(顺串) ；归并

10．模式串

【答案】01122312

的next 函数值序列为_____。

，

属于E 中找一条代价最小的边

加入集合

是连通图

，

，v ，

直到

开始，重复执行下述操作:在所有u 属于

，同时将并入

二、判断题

11．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ）

【答案】 ×

【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。

12．若一个广义表的表头为空表，则此广义表亦为空表。（ ）

【答案】 ×

【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。

13．归并排序辅助存储为O(1)（ ）

【答案】×

【解析】归并排序的辅助存储是O Cn)o

14．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ）

【答案】 √

【解析】可以有长度无穷大的广义表，只是在计算机中不能实现。