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

一、算法设计题

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

【答案】算法如下:

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

标。

根结点

左子树或右子树的结点数

将左子树前序序列转

为后序序列

将右子树前序序列转为

后序序列

2． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N

的二叉树的存储结构。

和

分别指示结点i 的左儿子和右儿子，

，使

) 表示i 的左(右) 儿子为空。试写一个

存放结点i 的父亲；然后再写一个判别结点u 是否

算法，由L 和R 建立一个一维数组为结点V 的后代的算法。

【答案】算法如下:

和

是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组

T 数组初始化

若结点i 的左子女是则结点L 的

双亲是结点

i

若结点i 的右子女是R , 则R 的

双亲是

i

判断U 是否是V 的后代

第 2 页，共 36 页

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

本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代

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

【答案】算法如下:

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

j)

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

释放空间

沿链表继续査找

删顶点j 的边结点(j,

i)

释放空间

沿链表继续査找

4． 已知关键字序列(

试写出一算法将(

利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:

''

假设

是大堆，本算法把

(2)

5． 己知L 为链表的头结点地址，表中共有m(m＞3) 个结点，从表中第i 个结点(l＜i ＜m) 起到第m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。

【答案】算法如下:

//L是有m 个结点的链表的头结点的指针。表中从第个结点到第m 个结点构成循环部分链表//本算法将这部分循环链表倒置

第 3 页，共 36 页

) 是大根堆。

) 调整为大根堆；

调成大堆

//p是工作指针，初始指向第二结点(已假定i ＞

l) //pre是前驱结点指针，最终指向第i ﹣i 个结点

//计数器

//查找第i 个结点

//査找结束，P 指向第i 个结点

//暂存第i 个结点的指针

//p指向第i ＋l 个结点，准备逆置

//上面while 循环结束时，j ＝i ﹣1现从第i ＋1结点开始逆置

//暂存P 的后继结点

+

//逆置P 结点

//P恢复为当前待逆置结点

//计数器增

1

//将原第i 个结点的后继指针指向原第m 个结点

二、应用题

6． 在多关键字排序时，LSD 和MSD 两种方法的特点是什么？

【答案】(1)最高位优先(MSD)法

先对最高位关键字K 进行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的

K 0值，然后，分别就每个子序列对关键字K 1进行排序，按K 1值不同再分成若干更小的子序列，依次重复，直至最后对最低位关键字排序完成，将所有子序列依次连接在一起，成为一个有序子序列。

(2)最低位优先(LSD)法 先对最低位关键字

进行排序，然后对高一级关键字进行排序，依次重复，直至对最高

位关键字K 排序后便成为一个有序序列。进行排序时，不必分成子序列，对每个关键字都是整个序列参加排序，

但对

排序时，只能用稳定的排序方法。另一方面，按LSD 进行排序

时，可以不通过关键字比较实现排序，而是通过若干次“分配”和“收集”来实现排序。

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

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

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

，则空闲块大小只能是

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

109

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

第 4 页，共 36 页