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

一、算法设计题

1． 假设以I 和0分别表示入栈和出栈操作。栈的初态和终态均为空，入桟和出找的操作序列可表示为仅由I 和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的？

A.

B.

C.

D.

(2)通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ，否则返回false(假定被判定的操作序列已存入一维数组中) 。

【答案】(1)A和D 是合法序列，B 和C 是非法序列。 (2)设被判定的操作序列已存入一维数组A 中，算法如下:

//判断字符数组A 中的输入输出序列是否是合法序列。

//i为下标

//j和k 分别为I 和字母O 的个数

//入栈次数增

1

//不论A[i]是’I'或’〇' ，指针i 均后移

//算法结束

2． 设有一个数组中存放了一个无序的关键序列

【答案】算法如下:

。现要求将K n 放在将元素排序后

的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n(注:用程序实现) 。

3． 已知无向图采用邻接表存储方式，试写出删除边(i, j) 的算法。

【答案】算法如下:

在用邻接表方式存储的无向图g 中，删除边(i,

j)

删顶点i 的边结点(i, j) , pre 是前驱指针

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

4． 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。

【答案】算法如下:

求以双亲表示法作为存储结构的树的深度

深度加1, 并取新的双亲

最大深度更新

返回树的深度

’结束Depth

5． 当一棵有n(

) 个结点的二叉树按顺序存储方式存储在

中时，试写一个算法，求

出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。

【答案】算法如下:

二叉树顺序存储在数组

中，本算法求结点i 和j 的最近公共祖先结点的值

下标为i 的结点的双亲结点的下标

下标为j 的结点的双亲结点的下标

所査结点的最近公共祖先的下标是

整型

，值是

设元素类型为

二、应用题

6． 对于具有n 个叶结点且所有非叶结点都有左、右孩子的二叉树。

(1)试问这种二叉树的结点总数是多少？ (2)试证明

。其中:表示第i 个叶结点所在的层号(设根结点所在层号为1) 。

【答案】(1)根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n 个叶结点且非叶子结点均有左子树的二叉树的结点数是2n －1。

(2)当i=1时，

，公式成立。设当i=n－1时公式成立，证明当i=n时公式仍成立。

设某叶结点的层号为t ，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公，所以结果不变，这就证明当i=n时公式仍成立。 式中，因为

7． 在堆排序、快速排序和合并排序中:

(1)若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？

(2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 【答案】(1)应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法。 (2)应选取归并排序方法 (3)应选取快速排序方法 (4)应选取堆排序方法

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

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

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