数据结构课后习题答案

? ?

① ②

（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）已知如图所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 答案：

① ③