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

一、填空题

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

【答案】

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

2． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

(1)若

是边，则

的值等于_____，若

不是边，则A(i, j) 的值是一个比任何

置

边的权_____，矩阵的对角线元素全为0。

(2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素成_____，若

【答案】(1)

已包括进生成树，就把矩阵元素

置成_____。

(3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。

边上的权值；都大的数；(2)1; 负值；(3)为负；边

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

【答案】

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

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

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

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

)

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

的值在

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

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

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

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

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

选具有最小权值的候选边

图不连通，出错处理

修改候选边集合

【答案】(1)

(2)

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

中

是连通图

，

，v ，

直到

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

加入集合

，同时将并入

的边为止。

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

6． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

7． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。

【答案】（ ）；(（ ）) ；2；2

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

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

【答案】O(1)；O(n)

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

9． 设有N 个结点的完全二叉树顺序存放在向量 中，其下标值最大的分支结点为_____。

【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

10．若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】

【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因. 。 为每条边重复出现两次，所有无向完全图的边数为

11．遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。 12． —棵深度为k 的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。

13．完善算法:求KMP 算法.next 数组。

k :＝_____；next[1]:＝0；