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

一、应用题

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

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

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

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

2． 画出同时满足下列两个条件的两棵不同的二叉树。

(1)按前序遍历二叉树的顺序为ABCDE 。 (2)高度为5其对应的树(森林) 的高度最大为4。 【答案】(1)满足条件的二叉树如图1所示:

图1

(2)满足条件的二叉树如图2所示:

图2

3． 下列关于堆(Heap)的一些问题:

(1)堆的存储表示是顺序的还是链接的？

(2)设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？

(3)对n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O 表示法) ？ 【答案】(1)堆的存储是顺序的。

(2)最大值元素一定是叶结点，在最下两层上。

(3)在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下: 由于第i 层上的结点数至多是

，以它为根的二叉树的深度为h －i+1，则调用

次筛选

算法时总共进行的关键字比较次数不超过下式之值:

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

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

5． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。

【答案】(1)内部排序中的归并排序是在内存中进行的归并排序，辅助空间为O(n)。外部归并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。

(2)因为归并的趟数排序的效率。

，其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都

可减少归并趟数。应用中通过败者树进行多(k)路平衡归并和置换一选择排序减少m ，来提高外部

二、算法设计题

6． 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设

用

表示辅助地址表。初始时

减序) 算法的语句序列。

【答案】算法如下:

一趟排序无交换发生，结束

表示n 个结点的值，用

，在排序中，凡需对结点交换就用它的地址

来进行。例如当n=3时，对K(31，11，19) 则有T(2，3，1) 。试编写实现辅助地址表排序(按非递

7． 试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x 的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为:

{二叉树根结点的指针}

【答案】算法如下:

生成三叉链表的二叉树(题目给出PASCAL 定义，下面用类C 语言书写

)

是二叉树结点指针的一维数组，容量足够大

一维数组最后元素的下标

元素或虚结点

根结点

双亲结点和子女结点用指针链上

结束