课后作业部分第六章树和二叉树
2. 将下图所示的树转换为二叉树，
3. 图5-17所示的二叉树转换为树或森林
4. 已知某字符串S中共有8种字符[A,B,C,D,E,F,G,H]，分别出现2次. 1次. 4次. 5次. 7次. 3次. 4次和9次。
1）试构造出哈夫曼编码树，并对每个字符进行编码 2）问该字符串的编码至少有多少位。
H
E
D F
A
B
C
G
A:00000 B:00001 C:100 D:001 E:11 F:0001 G:101 H:01
其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。
四. 算法设计
14
课后作业部分第六章树和二叉树
1. 设计算法求二叉树的结点个数
2. 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲
3. 编写算法交换二叉树中所有结点的左右子树。
15
课后作业部分第七章图
第七章图
一. 填空题
1. 设无向图G中顶点数为n，则图G至少有 0 条边，至多有n(n-1)/2条边；若G为有向图，则至少有 0 条边，至多有n(n-1)条边。 2. 任何连通图的连通分量只有一个，即是它自身
3. 若一个有向图由邻接矩阵表示，则计算第j个顶点入度的方法是求矩阵第j列元素之和
4. 图的深度优先遍历类似于树的先根遍历，广度优先遍历类似于树的层序遍历。 5. 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为Ｏ(n2)，利用Kruskal算法求最小生成树的时间复杂度为Ｏ(elog2e)。
二. 选择题
1. 在一个无向图中，所有顶点的度数之和等于所有边数的（ C）倍。 A 1/2 B 1 C 2 D 4
2. n个顶点的强连通图至少有（ A ）条边。 A n B n+1 C n-1 D n×(n-1)
3. 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ C）。 A 1 B n/2 C n-1 D n
4. 对于一个具有n个顶点的无向图用邻接矩阵存储，则该矩阵的大小是（ D）。 A n B (n-1)2 C n-1 D n2
5. 设无向图G=(V, E)和G' =(V', E' )，如果G' 是G的生成树，则下面的说法中错误的是（ B ）。
A G' 为 G的子图 B G' 为 G的连通分量 C G' 为G的极小连通子图且V= V' D G' 是G的一个无环子图
6. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ D ）。 A 求关键路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法
7. 下面关于工程计划的AOE网的叙述中，不正确的是（ B ） A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完
三. 计算题
1. 已知一个连通图如图所示，试给出图的邻接矩阵和邻接表
16
课后作业部分第七章图
存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。
邻接矩阵表示如下：
深度优先遍历序列为：v1 v2 v3 v5 v4 v6
广度优先遍历序列为：v1 v2 v4 v6 v3 v5
邻接表表示如右：
2. 已知无向图G的邻接表如下图所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相应的生成树。
深度优先遍历序列为：1，2，3，4，5，6 对应的生成树为：
广度优先遍历序列为：1，2，4，3，5，6 对应的生成树为：
3. 下图所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。
17
课后作业部分第七章图
4. 如右图所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。
从源点v1到其他各顶点的最短路径如下表所示。
源点终点最短路径最短路径长度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45
5. 已知一个AOV网如下图所示，写出所有拓扑序列。
拓扑序列为：v0 v1 v5 v2 v3 v6 v4、 v0 v1 v5 v2 v6 v3 v4、 v0 v1 v5 v6 v2 v3 v4。
四. 算法设计
1. 设计算法，将一个无向图的邻接表转换成邻接矩阵。
18