? ?
① ②
（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为，，，，，，，。
① 试为这8个字母设计赫夫曼编码。
② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例，比较两种方案的优缺点。 答案：方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32
（100）
（40） （60）
19 21 32 （28）
（17） （11）
7 10 6 （5） 2 3
方案比较： 字 母编号 1 2 3 4 5 0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 7 10 6 0 1 2 3 对应编码 1100 00 11110 1110 10 11111 01 出现频率 字母编号 1 2 3 4 5 6 7 对应编码 000 001 010 011 100 101 110 出现频率 6 7
方案1的WPL＝2+++4+++5+=++= 方案2的WPL＝3+++++++=3
结论：哈夫曼编码优于等长二进制编码
?（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。
答案： 初态:
? 1 2 3 4 5 6 7 8 9 10 11 12 13 ? 终态：
? 1 2 3 4 5 6
weight 3 12 7 4 2 8 11 ? ? ? ? ? ? parent 0 0 0 0 0 0 0 0 0 0 0 0 0 lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 rchild 0 0 0 0 0 0 0 0 0 0 0 0 0
weight 3 12 7 4 2 8 parent 8 12 10 9 8 10 lchild 0 0 0 0 0 0 rchild 0 0 0 0 0 0
7 8 9 10 11 12 13 11 5 9 15 20 27 47 11 9 11 12 13 13 0 0 5 4 3 9 2 11 0 1 8 6 7 10 12 3．算法设计题
以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。
[题目分析]如果二叉树为空，返回0，如果二叉树不为空且左右子树为空，返回1，如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述]
int LeafNodeCount(BiTree T) {
if(T==NULL)
return 0; c;} 1 C1 C8 C队列
C. 树 D．图
答案：B
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 （9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 答案：A
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 （10）深度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：A
（11）广度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：D
（12）图的BFS生成树的树高比DFS生成树的树高（ ）。
A．小 B．相等 C．小或相等 D．大或相等 答案：C
解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生
成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。
（13）已知图的邻接矩阵如图所示，则从顶点v0出发按深度优先遍历的结果是（ ）。
? 图 邻接矩阵
（14）已知图的邻接表如图所示，则从顶点v0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。
图 邻接表
A．0 1 3 2 答案：D、D
B．0 2 3 1 C．0 3 2 1 D．0 1 2 3
（15）下面（ ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 答案：B 2．应用题
（1）已知图所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；
④ 逆邻接表。
? 图 有向图 图 无向网
答案：
（2）已知如图所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 答案：
① ③
数据结构课后习题答案
