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

一、应用题

1． 二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：

其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：

（1）给出算法的基本设计思想；

（2）使用C 或C++语言，给出二叉树结点的数据类型定义；

（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。

【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。

（2）

typedef struct BiNode

（3）具体算法实现如下：

如果当前节点为空节点

//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的

WPL

//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和

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

【答案】（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺

序文件不能像顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。

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

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

3． 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading ”和“being ”的存储映像如图所示。

图 存储映像7K 意图

设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为符i 所在结点的位置p ）。要求：

（1）给出算法的基本设计思想。 （2）根据设计思想，采用C 或【答案】

（1）算法的基本设计思想：

①分别求出strl 和str2所指的两个链表的长度m 和n ;

②将两个链表以表尾对齐：令指针p 、q 分别指向strl 和str2的头结点，若表中的第

个结点；若

则使q 指向链表中的第

表尾的长度相等。

③反复将指针p 和q 同步向后移动，并判断它们是否指向同一结点。若p 和q 指向同一结点，则该点即为所 求的共同后缀的起始位置。

（2）用C 语言算法描述如下：

请设计一

个时间上尽可能高效的算法，找出由strl 和str2所指的两个链表共同后缀的起始位置（如图中字

或JA V A 语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度。

则使p 指向链

个结点，即使指针p 和q 所指的结点到

两个指针同步向后移动

（3）参考答案的时间复杂度为：

或

其中m 、n 分别为两个链表的

长度。 4． 设有n 个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J 趟起泡通常需要进行多少次关键字比较? 在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。

【答案】n 个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j 趟起泡排序要进行

次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排

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

表 二叉树BT 的存储结构

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

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

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

【答案】（1）二叉树的逻辑结构如图1所示： 序结束，下面语句段说明了标记flag 的使用。

返回共同C 缀的起始点