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

一、应用题

1． 组织待检索文件的倒排表的优点是什么？

【答案】倒排表作为索引的优点是索引记录快，因为从次关键字值直接找到各相关记录的物理记录号，倒排因此而得名（因通常的查询是从关键字查到记录）。在插入和删除记录时，倒排表随之修改，倒排表中具有相同次关键字的记录号是有序的。

2． 解答问题。设有数据逻辑结构为：

（1）画出这个逻辑结构的图示。

（2）相对于关系R ，指出所有的开始结点和终端结点。 （3）分别对关系R 中的开始结点，举出一个拓扑序列的例子。 （4）分别画出该逻辑结构的正向邻接表和逆向邻接表。 【答案】 ⑴如图1所示：

图1

（2）开始结点（入度为0）:（3）拓扑序列：

规则：开始结点为

或

之后，若遇多个入度为0的顶点，按顶点编号顺序选择。

（4）正向邻接表如图2所示，逆向邻接表如图3所示：

终端结点（出度为0）:

图2 正向邻接表

图3 逆邻接表

3． 试叙述动态存储分配伙伴系统的基本思想，它和边界标识法不同点是什么？

【答案】（1）动态存储分配伙伴系统的基本思想

在伙伴系统中，无论占用块或空闲块，其大小均为（k 为大于等于0的正整数）。若内存容

量为

则空闲块大小只能是

由同一大块分裂而得的两个小块互称“伙伴空

（若

）

，

如内存大小为

间”或

的块分裂成两个大小为的块。只有两个“伙伴空间”才能合并成一个大（若

（2）和边界标识法的不同

边界标识法在每块的首尾均有“占用”/“空闲”标志，空闲块合并方便。伙伴系统算法简单、速度快，但只有互为伙伴的两个空闲块才可合并，因而易产生虽空闲但不能归并的碎片。

4． 一个ISAM 文件除了主索引外，还包括哪两级索引？

【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。

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

表 二叉树BT 的存储结构

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

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

空间。起始地址为P ，

大小为的内存块，其伙伴的起始地址为：

）。

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

【答案】（1）二叉树的逻辑结构如图1所示：

图1

（2）前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA

（3）:二叉树的后续线索树如图2所示：

图2

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

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

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