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

一、综合题

1． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？

【答案】(1)最高位优先(MSD)法

先对最高位关键字K 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的

K 0值，然后，分别就每个子序列对关键字K 1进行排序，按K 1值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。

(2)最低位优先(LSD)法 先对最低位关键字

进行排序，然后对高一级关键字进行排序，依次重复，直至对最高

位关键字K 排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，

但对

排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序

时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。

2． 下列广义表，可以唯一对应一棵二叉树的有（ ）。并归纳出唯一对应的条件。

(1)(A(B(D，E) ，C(F))) (2)(A(B(D，E) ，C)) (3)(A)

(4)(A(B(C，D(E))))

(5)（ ）

【答案】唯一对应一棵二叉树的有(2)、(3)和(5)。唯一对应的条件:空表、只有一个元素的表、每个子表个数是零或是2的表。

3． 请回答下列关于图(Graph)的一些问题:

(1)有n 个顶点的有向强连通图最多有多少条边? 最少有多少条边？

(2)表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素? 是否稀疏矩阵？

(3)对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 【答案】⑴最多有n(n－1) 条边；最少有n 条边。 (2)有有

个矩阵元素；不一定是稀疏矩阵(稀疏矩阵的定义是非零元素个数远小于该矩阵元

素个数，且分布无规律)

(3)使用深度优先遍历，按退出DFS 过程的先后顺序记录下的顶点是逆向拓扑有序序列。如果在执行DFS(v)未退出前，出现顶点u 到v 的回边，则说明存在包含顶点v 和顶点u 的环。

4． 证明:具有n 个顶点和多于n －1条边的无向连通图G —定不是树。

【答案】证明:具有n 个顶点n －1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。若边数多于n －1条，因一条边要连接两个结点，则必因加上这一条边而使两个结点多了一条通路，即形成回路。形成回路的连通图不再是树。

5． 模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m ，模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式

，请给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是O(m＋n) 。

p 的next 和nextval 值分别为01112212321和01102201320。

6． 己知n 阶下三角矩阵A(即当i ＜j 时，有序分配方式时在B 中确定元素

) ，按照压缩存储的思想，可以将其主对角线以

下所有元素(包括主对角线上元素) 依次存放于一维数组B 中，请写出从第一列开始采用列序为主

的存放位置的公式。

第1列有n 个元素，第j 列有n ﹣j ＋1个

在第j 列上的位置是为i

在一维数组B 中的存储位置k 与i 和j 的关

7． 在一棵表示有序集S 的二叉搜索树(binary search tree)中，任意一条从根到叶结点的路径将S 分为3部分:在该路径左边结点中的元素组成的集合S1; 在该路径上的结点中的元素组成的集合S2; 在该路径右边结点中的元素组成的集合S3; 有

？为什么？

【答案】该结论不成立。例如，本题中对于任一f 的左子树上。对于从a 到根结点路径上的所有

，可在S2中找到a 的最近祖先f 。a 在，有可能f 在b 的右子树上，因而a 也就在。若对于任意的

是否总

【答案】2阶下三角矩阵元素

﹣j ＋1。所以n 阶下三角矩阵A 按列存储，其元素系为:

元素，第1列到第j ﹣1列是梯形，元素数为(n＋(n﹣j ＋2)(j﹣1)/2，而

b 的右子树上，这时a>b，因此a

均有a

8． 在改进了的(无回溯) 字符串模式匹配中，要先求next 数组的值。下面是求nextval 值的算法。

{在模式P 中求nextval 数组的值

}

算法中第4行有P[J]＝P[K]，第六行中也有P[J]＝P[K]。两处比较语句相同。请分析说明此两处比较语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？

【答案】第4行的P[J]＝P[K]语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则指针J 和K 均增加1，继续比较。第6行的p[J]＝p[K]语句的意义是，当第J 个字符在模式匹配中失配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K 个字符失配时的下一个(即NEXTV AL[K])。该算法在最坏情况下的时间复杂度0(m2)。

9． 某博物馆最多可容纳500人同时参观, 有一个出入口, 该出入口一次仅允许个通过。参观者的活动描述如下:

Cobegin

参观者进程i : {

进门; 参观;

出门; } coend

请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 以实现上述操作过程中的互斥与同步。要求写出完整的过程, 说明信号量含义并赋初值。

【答案】定义两个信号量

博物馆可以容纳的最多人数

用于出入口资源的控制