5数据结构复习题.pdfVIP

数据结构复习题

1.何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性

表的存储结构，通常有以下几方面的考虑：

A.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，

为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存

储规模时，采用动态链表作为存储结构为好。

B.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，

采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等

的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的

首尾两端，则采用尾指针表示的单循环链表为宜。

2.解释拓扑排序，并简述如何进行拓扑排序。

由某个集合上的一个偏序得到该集合上的一个全序，这个操作就成为拓扑排序。

拓扑排序的操作如下：

1）在有向图中选一个没有前驱的顶点并输出之；

2）从图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。

后一种情况则说明有向图中存在环。

四、已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树对应

的二叉树。

123456789101112131415

dataABCDEFGHIJKLMNO

parent011122334456678

3.写出下图所示的AOV网的可能拓扑序列，要求至少写出五个。

D

B

AEF

C

答案：可能的拓扑序列有：

1）Abdcef

2）Abcdef

3）bcedf

4）Cabdef

5）Cabedf

6）Acbdef

7）Acbedf

4.设有一个求解汉诺塔（Hanoi）的递归算法

voidHANOI(intn,intpeg1,intpeg2,intpeg3)

{

if(n==1)

printf（”move%dto%d

”,peg1,peg3）;

else

{

HANOI(n-1,peg1,peg3,peg2);

printf（”move%dto%d

”,peg1,peg3）;

HANOI(n-1,peg2,peg1,peg3);

}

}

假定采用HANOI（3，1，2，3）去调用上述算法，则写出整个输出结果的前四行

内容。

答案：

汉诺塔的递归处理过程如下表示：

move1to3

move1to2

move3to2

move1to3

5.若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由

其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列

却不一定能唯一地确定一棵二叉树。

(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请

画出此二叉树。

(2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画

出此二叉树。

(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同

的二叉树。

答：已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前

序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB

和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可

画出所有结点：

○A