计算机软件练习题汇总

三、判断题

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

（ ）非线性数据结构可以顺序存储，也可以链接存储。

（ ）非线性数据结构只能用链接方式才能表示其中数据元素的相互关系。 （ ）完全二叉树一定是满二叉树。

（ ）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 （ ）若一棵二叉树的任意一个非叶子结点的度为2，则该二叉树为满二叉树。 （ ）度为1的有序树与度为1的二叉树是等价的。

（ ）二叉树的先序遍历序列中，任意一个结点均排列在其孩子结点的前面。 （ ）已知一棵二叉树的先序序列和后序序列，就一定能构造出该二叉树。 （ ）在霍夫曼树中，权值最小的结点离根结点最近。 ( )对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访问到该图的每个顶点。

11. （ ）线性数据结构可以采用顺序存储结构或链式存储结构，而非线性数据结构只能

采用链式存储结构。

12. （ ）二叉树中的叶子结点就是二叉树没有左、右子树的结点。 13. （ ）如果一棵树中某结点的度为1，则该结点仅有一棵子树。

14. （ ）在有向图中，若存在有向边,则一定存在有向边。

15. （ ）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历后，并

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

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