计算机软件练习题汇总(6)

不一定能访问到该图的每个顶点。

16. （ ）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间

大小只与图中结点个数有关，而与图的边数无关。

四、简答题

1. 什么叫有序树？什么叫无序树？有序树和二叉树的差别是什么？ 2. 什么叫完全二叉树？什么叫满二叉树？它们之间的关系是什么？

3. 什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？

五、综合题

1. 如图所示的两棵二叉树，分别给出它们的顺序存储结构。

A B C

D E

F G

I J K

第1棵树

D

A B C E F I J 第2棵树

2. 已知一棵二叉树的中序、后序序列分别如下：

中序：D C E F B H G A K J L I M 后序：D F E C H G B K L J M I A 要求：⑴ 画出该二叉树；

⑵ 写出该二叉树的先序序列。

3. 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格

处的内容，并画出该二叉树。 先序：_ B _ F _ I C E H _ G 中序：D _ K F I A _ E J C _ 后序：_ K _ F B H J _ G _ A

4. 将下图中的树转化为二叉树，并写出转换后的二叉树的后序遍历序列。

A

B C D E F G H

5. 将下图所示的树转换成二叉树，并写出转换后二叉树的先序、中序、后序遍历结果。

33

12 3 54 15 2 44 9G 2I 2H 35 15

6. 将下列一棵二叉树进行前序遍历、中序遍历、后序遍历，并转化为树。

22 3

33 16

1 56 58

52 2 34 4 9 7. 写出下面二叉树的先序、中序、后序遍历结果，并将它转换为树。 A B E C D F

G

H

I

8. 分别写出下图所示二叉树的先序、中序和后序遍历序列。

A

B

D C

F E

G H

9. 写出下图中的二叉树先序和后序遍历序列。

10. 输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，

要求：⑴ 画出该二叉排序树；

⑵ 画出删除结点302后的二叉排序树。

11. 按给出的一组权值{4，5，7，8，11}，建立一个霍夫曼树，并请计算出该树的带权路径

长度WPL。

12. 以{5,9,15,18,22}作为叶子结点的权值构造一棵Huffman树，并计算其带权路径长度

(WPL)。

13. 以{4,7,10,15,23}作为叶子结点的权值构造一棵Huffman树，并求出其带权路径长度。 14. 以{5,6,7,8,9,10,15,18,22}作为叶子结点的权值构造一棵Huffman树，并计算其带权

路径长度(WPL)。

15. 以{10,12,16,21,30}作为叶子结点的权值构造一棵Huffman树，并计算其带权路径长度

(WPL)。

16. 如右所示的有向图，请给出它的：

（1） 每个顶点的a e 入度和出度；

（2） 邻接矩阵；

f （3） 邻接表； （4） 强连通分量。 b d c

17. 已知一棵二叉树的中序和先序序列如下，求该二叉树的后序序列，并将它转换为树。 先序结果：A,B,E,F,C,D,G,H,I 中序结果：E,F,B,C,G,H,I,D,A

18. 已知一棵二叉树的中序和后序遍历结果如下所示，求该二叉树的先序遍历序列。 中序结果：E,F,B,C,G,H,I,D,A 后序结果：F,E,I,H,G,D,C,B,A

19. 请给出按自左向右的顺序依次将关键字为{30，5，20，23，9，27，6，14，45，22}的

记录插入到一个初始时为空的二叉排序树后所建立的二叉排序树。

20. 请将序列51，17，60，32，6，10，23，3，80，40，44，7排列为二叉排序树。 21. 请将序列28，55，06，33，161，81，91，11，25，56，57，02排列为二叉排序树。 22. 构造插入序列为{10，18，3，8，12，2，7，13}的二叉排序树，（要求过程）。 23. 请给出下面的二叉树的先序、中序和后序遍历结果。

A

B C D E F G

24. 请给出下面的有向图的邻接矩阵、邻接表形式的存储结构，并计算出每个顶点的入度和

出度。

A B

C D

F

25. 已知某无向图的邻接表存储结构如下图所示，（1）请画出此无向图，（2）给出无向图的

邻接矩阵表示。

A VA

B A A B C A C D E F F C ∧ ∧ ∧ F F D ∧ ∧ E ∧ B VB

C VC

D VD

E VE

F

VF