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

一、应用题

1． 为什么文件的倒排表比多重表组织方式节省空间？

【答案】倒排表有两项，一是次关键字值，二是具有相同次关键字值的物理记录号，这些记录号有序且顺序存储，不使用多重表中的指针链接，因而节省了空间。

2． 将下列出三棵树组成的森林转换为二叉树（只要求给出转换结果）。

图1

【答案】森林转换为二叉树分以下三步：

（1）连线（将兄弟结点相连，各树的根看作兄弟）。

（2）切线（保留最左边子女为独生子女，将其他子女分支切掉）。 （3）旋转（以最左边树的根为轴. 顺时针向下旋转45度）。 所以由上面三棵树转换得到的二叉树如图2所示：

图2

3． 对下面的关键字集若查找表的装填因子为0.8，采用线性探

测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。

【答案】（1）由于装填因子为0.8，关键字有8个，所以表长为哈希函数，哈希函数为

（2）哈希表如表所示：

表 哈希表

（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，

当其哈希地址为

时的查找次数。本例中

（4）算法如下：

4． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。

【答案】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点：叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点：叶结点或仅有左子树的结点。命题得证。

5． 在模试匹配KMP 算法中所用失败函数的定义中，为何要求真子串？且为最大真子串？

【答案】失败函数（即next ）的值只取决于模式串自身，若第j 个字符与主串第i 个字符失配时，假定主串不回溯，模式串用第k （即next[j]个字符与第i 个相比，有

用除留余数法设计

故查找失败和查找成功时的平均查找长度分别为：

两头匹配的

为了

不因模式串右移与主串第i 个字符比较而丢失可能的匹配，对于上式中可能存在的多个k 值，应取其中最大的一个。这样，因j-k 最小，即模式串向右滑动的位数最小，避免因右移造成可能匹配的丢失。

6． 画出对算术表达式表所示。

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

求值时操作数栈和运算符栈的变化过程。

求值，过程如

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

7． 设二叉树BT 的存储结构如表：

表 二叉树BT 的存储结构

其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：

（1）画出二叉树BT 逻辑结构；

（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列： （3）画出二叉树的后序线索树。