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

一、算法设计题

1． 请运用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第f(

【答案】算法如下:

在后半部分继续进行划分

在前半部分继续进行划分

2． 写出算法，求出中序线索二叉树中给定值为X 的结点之后继结点，返回该后继结点的指针。线索树中结点结构为；

。其中，data 存放结点的值；lc 、rc 为指向左、

右孩子或该结点前驱、后继的指针，ltag 、rtag 为标志域，若值为0, 则lc 、rc 为指向左、右孩子的指针；若值为1，则lc 、rc 为指向其前驱、后继结点的指针。

【答案】算法如下:

先在带头结点的中序线索二叉树T 中査找给定值为x 的结点，假定值为x 的结点存在

设P 指向二叉树的根结点

结束

在中序线索二叉树T 中,, 求给定值为x 的结点的

后继结点

第 2 页，共 37 页

) 小元素。

首先在T 树上査找给定值为x 的结点，由p 指向

' 若P 的右标志为1, 则P 的rc 指针指向其后继

结点P 的右子树中最左边的结点是结点P 的中序后继

结库

.

3． 已知二叉树T ，试写出复制该二叉树的算法(t→T) 。

【答案】算法如下:

复制二叉树t 的非递归算法

是二叉树的结点指针的队列，容量足够大

结束本题

4． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下:

在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回

确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情

况

返回第一邻接点，

和

中必有一个等于

i

取第一个边结点

5． 设T 是一棵满二叉树，写一个把T 的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下:

将满二叉树的后序序列转为前序序列，

标。

根结点

第 3 页，共 37 页

是序列初始和最后结点的下

左子树或右子树的结点数

将左子树前序序列转

为后序序列

将右子树前序序列转为

后序序列

二、应用题

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

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

7． 分析ISAM 文件() 和

VSAM 文件(

) 的应用场合、优缺点等。

【答案】ISAM 是一种专为磁盘存取设计的文件组织形式，采用静态索引结构，对磁盘上的数据文件建立盘组、柱面、磁道三级索引。ISAM 文件中记录按关键字顺序存放，插入记录时需移动记录并将同一磁道上最后的一个记录移至溢出区，同时修改磁道索引项，删除记录只需在存储位置作标记，不需移动记录和修改指针。经过多次插入和删除记录后，文件结构变得不合理，需周期整理ISAM 文件。

VSAM 文件采用B+树动态索引结构，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然联系。VSAM 文件结构包括索引集、顺序集和数据集三部分，记录存于数据集中，顺序集和索引集构成B+树，作为文件的索引部分可实现顺链查找和从根结点开始的随机查找。

优缺点:与ISAM 文件相比，VSAM 文件有如下优点:动态分配和释放存储空间，不需对文件进行重组；能保持较高的查找效率，且查找先后插入记录所需时间相同。因此，基于B+树的VSAM 文件通常作为大型索引顺序文件的标准组织。 8． 已知有6个顶点(顶点编号为0--5) 的有向带权图G , 其邻接矩阵A 为上三角矩阵, 按行为主序(行优先) 保存在如下的一维数组中。

要求:

(1)写出图G 的邻接矩阵A 。 (2)画出有向带权图G 。

(3)求图G 的关键路径, 并计算该关键路径的长度。

【答案】(1)由题可以画出待定上三角矩阵的结构图如下(图中？为待定元素) :

第 4 页，共 37 页