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

一、应用题

1． 设目标为

模式为

（1）计算模式p 的nextval 函数值；

（2）不写出算法，只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 【答案】（1）P 的nextval 函数值为0110132（P 的next 函数值为0111232）。 （2）利用KMP （改进的nextval ）算法，每趟匹配过程如下： 第一趟匹配：abcab （i=5, j=5） 第二趟匹配：abc （i=7，j=3） 第三趟匹配：a （i=7，j=l） 第四趟匹配：

（成功）abcabaa （i=15，j=8）

2． 调用下列C 函数f （n ），回答下列问题：

（1）试指出f （n ）值的大小，并写出，f （n ）值的推导过程；

（2）假定n=5，试指出，f （5）值的大小和执行，f （5）时的输出结果。 C 函数：

【答案】（1）第一层FOR 循环判断n ＋1次，往下执行n 次，第二层FOR 执行次数为（n ＋，第三层循环体受第一层循环和第二层循环的控制，其执行次数如（n －1）＋（n －2）＋... ＋1）表所示。

表 执行次数

执行次数为

（2）在n=5对，f （5）=55，执行过程中，输出结果为：

3． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），试完成下列各题。

（1）按次序构造一棵二叉排序树BS 。

（2）依此二叉排序树，如何得到一个从大到小的有序序列？ （3）画出在此二叉排序树中删除“66”后的树结构。 【答案】（1）构造的二叉排序树如图1所示：

图1 二叉排序树

（2）若二叉树非空，要得到一个从大到小的有序序列可以先中序遍历右子树；再访问根结点；最后中序遍历左子树。

（3）如图2所示：

图2

4． （1）对于有向无环图，叙述求拓扑有序序列的步骤；

（2）对于图1，写出它的四个不同的拓扑有序序列。

图1

【答案】（1）对有向图，求拓扑序列步骤为：

1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。 2）在图中删除该顶点及所有以它为尾的弧。

3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

（2）拓扑有序序列如图2:

图2 拓扑有序序列

5． 证明：置换选择排序法产生的初始归并段的长度至少为m （m 是所用缓冲区的长度）。

【答案】证明：由置换选择排序思想，第一个归并段中第一个元素是缓冲区中最小的元素，，缓以后每选一个元素都不应小于前一个选出的元素，故当产生第一个归并段时（即初始归并段）冲区中m 个元素中除最小元素之外，其他m-1个元素均大于第一个选出的元素，即当以后读入元素均小于输出元素时，初始归并段中也至少能有原有的m 个元素。证毕。 6． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。

（1）试指出判别给定序列是否合法的一般规则；

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举