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

一、应用题

1． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

（1）试问这种二叉树的结点总数是多少？

（2）试证明 。其中：表示第i 个叶结点所在的层号（设根结点所在层号为1）。

【答案】（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-l 。

（2）证明：当i=l时，

成立。

设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1, 对于公式的变化，是减少了一个原来的叶结点，増加了两个新叶结点，反映到公式中. 因为

2． 在树和，所以结果不变，这就证明当i=n时公式仍成立。证毕。 树中查找关键字时，有什么不同？

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关, 公式成立。设当i=n-1时公式成立，证明当i=n时公式仍【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。字后，要继续查到最下层结点，得到查找成功与否的结论。另外，

键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

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

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

}

算法中第4行有第六行中也有两处比较语句相同。请分析说明此两处比较

语句的含义是什么? 分析此算法在最坏情况下的时间复杂度是多少？

【答案】第4行的语句是测试模式串的第J 个字符是否等于第K 个字符，如是，则

语句的意义是，当第J 个字符在模式匹配中失指针J 和K 均増加1，继续比较。第6行的

配时，若第K 个字符和第J 个字符不等，则下个与主串匹配的字符是第K 个字符；否则，若第K 个字符和第J 个字符相等，则下个与主串匹配的字符是第K

个字符失配时的下一个（即

）。该算法在最坏情况下的时间复杂度

4． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？

【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元

，将非零元素存储在向量中，元素的下标i 和j 和该素分配单元（对值相同元素只分配一个单元）

元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小且分布没有规律。用十字链表作存储结构自然失去了随机

最差情况下是因此也失去存取的功能。即使用三元组表的顺序存储结构，存取下标为i 和j 的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为了随机存取的功能。

5． 试比较顺序文件、索引非顺序文件、索引顺序文件、哈希文件的存储代价，检索、插入、删除记录时的优点和缺点。

【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。

（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。

（3）散列文件也称直接存取文件，根据关键字的哈希函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。

6． 下面程序段的时间复杂度是什么？

【答案】赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O （m*n）。

7． 外排序中为何采用k 一路

么？

【答案】外排序用路归并合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什是因为k 越小，归并趟数越多，读写外存次数越多，时间效率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。

8． 画出对算术表达式求值时操作数栈和运算符栈的变化过程。

【答案】设操作数栈是opnd ，运算符栈是optr ，对算术表达式

表所示。

表 操作数栈和运算符找的变化过程

求值，过程如

二、算法设计题

9． 输入一个字符串，内有数字和非数字字符，如：

作为一个整体，依次存放到一数组a 中，例如123放入

多少个整数，并输出这些数。

【答案】算法如下：

456放入将其中连续的数字编程统计其共有