数据结构复习资料--覆盖所有知识点(2)

二叉树有哪几种基本形态? 画图说明之。

2. 写出下列二叉树的前序，中序，后序遍历序列及对应的森林 。

3. 设一棵二叉树的先序、中序遍历序列分别为

先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C

(1) 画出这棵二叉树。

(2)画出这棵二叉树的后序线索树。

(3)将这棵二叉树转换成对应的树(或森林)。

4. 已知二叉树的中序和后序遍历序列如下，试构造该二叉树。

中序：A C B D H G E F 后序：A B C D E F G H

b c a + * d - / e

5. 试将森林 F={ T1,T2,T3,T4 }转换为一棵二叉树。

6

T1 T2 T3 T4

6. 画出下列二叉树对应的先序、中序、后序线索二叉树存储结构。a b c d e f g h i

7

7. 已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。

8. 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩

子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。

8

9.

已

知

有

向

图

G=(V,E)

，

其

中

V={V1,V2,V3,V4,V5,V6,V7}

，

E={,,,,,,,,},G的拓扑序列是( )。

10. 有7个顶点（v1,v2,v3,v4,v5,v6,v7） 的有向图的邻接矩阵如右图。请回答相关问题： （1） 画出该有向图。

（2） 写出从v1出发的深度优先遍历和广度优先遍历序列。

9

∞ ∞ ∞ ∞ ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ ∞ ∞ 5 2 ∞ ∞ ∞ ∞ ∞ 3 ∞ 1 ∞ ∞ ∞ ∞ ∞ ∞ 3 5 ∞ ∞ ∞ ∞ 8 5 ∞ 3 ∞ ∞ ∞ ∞ ∞ ∞ 9 5 ∞

（1）画出该有向图

（2）画出邻接表

（3）写出从v1出发的深度优先遍历和广度优先遍历序列（4分） 深度dfs v1 v4 v5 v7 v6 v3 v2 广度bfs v1 v4 v3 v2 v5 v6? v7

（4）将图看成AOE网，画出关键活动及相应的有向边，写出关键路径的长度

关键路径的长度为20

11. 已知如图所示的有向图，请给出该图的 :答案不全

10