数据结构
树
习题4 习题4b：画出与题目中的树相对应的二叉树 1 1 2 4 7 10 11 5 8 3 6 9 4 2 7 10 11 5 8 12 3 6 9
12 先序：1 2 4 7 10 11 5 3 6 8 9 12 先序：
中序： 中序：4 10 7 11 2 5 1 3 8 6 12 9 后序：10 11 7 4 5 2 8 12 9 6 3 1 后序：
数据结构
树
习题5 写出二叉树的三种序列， 习题 5a ： 写出二叉树的三种序列 ， 并将其恢复 为森林 A A B B E G H K I L C D F J K L G H I J F E C D
数据结构
树
习题5 习题5b：画出与题目中的树相对应的二叉树 1 1 2 11 2 11 3 3 6 9 4 7 5 8 10 12 13 14 9 10 8 6 7 4 5 12 13 14
19 12
B 5 7 3 D 21 C
E 16 8
F
21
第7章 图习题
5
15
10
2
2 4 20
4
10 4
数 据 结 构
30
1
15
6
10
3
最短路径 （1, 3） （1, 3, 2） （1, 3, 6） （1, 3, 2, 5) （1, 3, 6, 4）
dist
长度 15 19 25 29 29
S 1 1,3
数据结构习题
数据结构
树
补充习题1、试分别画出具有3个结点的树和二叉树的 补充习题 、试分别画出具有 个结点的树和二叉树的 所有不同形态。 所有不同形态。
树： 2种
注意： 注意： 树的孩子没有左右之分 二叉树的孩子有左右孩子之分
二叉树：
5种
2
数据结构
树
习题3.已知一棵度为 的树中有 个度为1的结点 的结点， 习题 已知一棵度为k的树中有 1个度为 的结点，n2个度 已知一棵度为 的树中有n 个度为m的结点 的结点， 的结点， 为2的结点，…nm个度为 的结点，则该树中有多少个 的结点 终端结点。 终端结点。 解：设n为总结点数，则有 (总结点数 n=n0+n1+n2+…nm 总结点数) 总结点数 (总边数 n-1=1*n1+2*n2+…m*nm 总边数) 总边数 两式相减得：1=n0-n2-2n3-…-(m-1)nm n0=1+n2+2n3+…+(m-1)nm m =1+∑(i-1)ni
7
图
13. 对下图写出3个拓扑排序和2个逆拓扑序列
数 据 结 构
拓扑排序： 7 8 2 4 6 9 3 5 1 1 1 7 8 4 9 6 2 3 5 7 1 7 8 4 6 9 3 2 5 2 逆拓扑排序： 5 3 6 4 9
23
8
5 2 3 6 9 4 8 7 1 5 3 2 6 9 4 8 7 1
0 2 010
111 2 3
WPL=7*2+8*2+2*3+3*3+4*3+5*3=72
第7章 图习题
1.已知有向图，给出该图的：每个顶点的入度、出 度;邻接矩阵；邻接表;逆邻接表。 ①每个顶点的入度、出度;
数 据
1 入度 出度 3 0
2 2 2
3 1 2
4 1 2 5 0 0 0 0 0 1 6 0 0 1 1 0 0
例如:
4 4 2 5
已知权值 W={ 4, 2, 3, 5, 7, 8} 29 12 3 9 3 9 4 5 7 5 2 12 5 3 2 3 4 5 7 5 8 17 9 3 7 5 8 2 7 5 8
构造哈夫曼树如下： 构造哈夫曼树如下：
7
8 2
5
8 4
29 0 0 7 7 00 12 12 1 5 5 0 8 8 1 10 3 011 0 4 4 110 1 17 17 1 9 9 1 55
1 2 3 4 6 578
深度优先生成树：
数 据
1 2 6 3 4
16
5 8 7
第7章 图习题
2&7. （2）广度优先遍历顶点序列：
数 据
1 2 6 5 8 347 或者 1 2 5 6 8 3 7 4
广度优先生成树：
1 2 6 3 4 7 5 8 3 2
1 5 6 7 4
17
8
第7章 图习题
3. （1）深度优先遍历顶点序列：
F
20
第7章 图习题
a. kruskal算法
3 5 7 8 12 14 16 (D,C) (B,C) (B,D) (D,E) (B,E) (A,E) (G,E) × × √ √ √ √ √
数 据
18 19 21 27 (A,G) (A,B) (F,D) (F,G) × × √
A 18 G 27 14
i=1 3
数据结构
树
习题8 先序序列为ABC ABC的二叉树有几种形态 习题8：先序序列为ABC的二叉树有几种形态
A A A
B A C B
B
C A
B
C B
C
C
数据结构
树
习题9 先序序列: 习题9：先序序列:A B C D E F G H I 中序序列: 中序序列:B C A E D G H F I 画出来并写出后序序列。 画出来并写出后序序列。
数据结构
树
习题4 写出二叉树的三种序列， 习题 4a ： 写出二叉树的三种序列 ， 并将其恢复 为森林 C A A B E G H C B D I D E F H I G F C
先序： 先序：A B D F H C E G I J J 中序： 中序：F H D B A E I G J C 后序： 后序：H F D B I J G E C A
V2 20(1,2)
V3
V4
V5
V6 ∞ 25(1,3,6) 25(1,3,6) √ //////// ////////
15(1,3) ∞ ∞ √ 1,3,2 19(1,3,2) //////// 2 ∞ ∞ √ 1,3,2,6 //////// //////// 29(1,3,2,5) ∞ 3 //////// 29(1,3,6,4) 29(1,3,2,5) 4 1,3,2,6,5 //////// √ //////// 1,3,2,6,5,4 //////// //////// 29(1,3,6,4) 5 √
1 ∧ 2 3 4 5 6
1 2 3 1 ∧ 1
4 ∧ 6 ∧ 6 ∧ 5 ∧
14
2
第7章 图习题 ④逆邻接表（入度表） 2
1 6 3
5
4
数 据
1 2 3 4 5 6
1 2 3 4 5 6
2 3 4 ∧ 2 ∧ 6 ∧ 3
5 6 ∧
6 ∧
4 ∧
15
第7章 图习题
2&7. （1）深度优先遍历顶点序列：
5 1 1Байду номын сангаас
6 2 3 1 非 对 称 矩 阵 2 3 13 6 4 5
1 2 3 4 ②邻接矩阵; 1 0 0 0 0 2 1 0 0 1 3 0 1 0 0 4 0 0 1 0 5 1 0 0 0 6 1 1 0 0
第7章 图习题 （出度表） ③邻接表 2
1 6 3
5
4
数 据
1 2 3 4 5 6
A B C E G H D F
后序序列: 后序序列: C B E H G I F D A
I
数据结构
树
习题16：编写算法，实现交换二叉树的左右子树。 习题16：编写算法，实现交换二叉树的左右子树。 16
void exchange(Bitree *bt) { BitNode *p; if((*bt)!=NULL) { p=(*bt)->lchild; (*bt)->lchild=(*bt)->rchild; (*bt)->rchild=p; /*交换当前根节点的左右子树 交换当前根节点的左右子树*/ 交换当前根节点的左右子树 exchange(&(*bt)->lchild); exchange(&(*bt)->rchild); } }
1 2 3 4 5
数 据
1 5 2
4
3
18
第7章 图习题
4. （2）广度优先遍历顶点序列：
1 2 3 4 5
数 据
1 5 2
4
3
19
第7章 图习题
用prim算法和kruskal算法生成最小生成树 a.prim算法(从顶点A出发)
数 据
A 18 G 27 14
19 12 E 16 8
B 5 7 3 D 21 C