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

一、应用题

1． 设度为m 的树采用多重链表存储，毎个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。 则空指针的数目是多少？说明这种存储方式的利弊。

【答案】（1）空指针数目：n （n>0）个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有nm-（n-1）=n（m-l ）+1个。

（2）利弊：这种存储结构统一，便于处理但空链域造成存储效率低。

2． 阅读下面的算法，说明算法实现的功能。

【答案】本算法功能是将两个无头结点的循环链表合并为一个循环链表。Head1最后一个结点的链域指向head2, head2最后一个结点的链域指向headl ，headl 为结果循环链表的指针。

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

表 二叉树BT 的存储结构

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

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

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

（3）画出二叉树的后序线索树。

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

图1

（2）前序序列：ABCEDFHGIJ

中序序列：ECBHFDJIGA

后序序列：ECHFJIGDBA

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

图2

4． 文件存储结构的基本形式有哪些? 一个文件采用何种存储结构应考虑哪些因素？

【答案】文件的基本组织方式有顺序组织、索引组织、散列组织和链组织，常用的结构有顺序结构、索引结构、散列结构。

（1）顺序结构，相应文件为顺序文件，其记录按存入文件的先后次序顺序存放。顺序文传本质上就是顺序表。若逻辑上相邻的两个记录在存储位置上相邻，则为连续文件；若记录之间以指针相链接，则称为串联文件。顺序文件只能顺序存取，要更新某个记录，必须复制整个文件。顺序文件连续存取的速度快，主要适用于顺序存取，批量修改的情况。

（2）带索引的结构，相应文件为索引文件。索引文件包括索引表和数据表，索引表中的索引项包括数据表中数据的关键字和相应地址，索引表有序，其物理顺序体现了文件的逻辑次序，实

现了文件的线性结构。索引文件只能是磁盘文件，既能顺序存取，又能随机存取。

（3）散列结构，也称计算寻址结构，相应文件称为散列文件，其记录是根据关键字值经哈希函数计算确定其地址，存取速度快，不需索引，节省存储空间。不能顺序存取，只能随机存取。

文件采用何种存储结构应综合考虑各种因素，如：存储介质类型、记录的类型、大小和关键字的数目以及对文件作何种操作。

5． 证明：在二叉树的三种遍历序列中，所有叶结点间的先后关系都是相同的。要求毎步论断都指出根据。

【答案】前序遍历是“根左右”. 中序遍历是“左根右”. 后序遍历是“左右根”。若将“根”去掉，三祌遍历就剩“左右”。三种遍历中的差别耽足访问根结点的时机不同。二叉树是递归定义的，对左右子树均是按左右顺序来遍历的，因此所有叶结点间的先后关系都是相同的。

6． 设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值？

【答案】有两种方法，具体如下：

（1）对该算术表达式（二叉树> 进行后序遍历. 得到表达式的后序遍历序列，再按后缀表达式求值。

（2）递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、

一、*、/等） 进行求值。

7． 若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

8． 已知图的邻接矩阵为：

当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：

（1）以顶点V1为出发点的唯一的深度优先遍历序列；

（2）以顶点V1为出发点的唯一的广度优先遍历序列；

（3）该图唯一的拓扑有序序列。