Lab 05-T-03：哈夫曼树与编码题精练

目标

独立辨析哈夫曼树与编码中的核心概念、结构性质与算法关系；
对选择题写出排除干扰项的依据，而不只记忆答案字母；
对本组已有的综合题完成推导、算法设计或复杂度分析。

前置知识

建议先阅读5.3 赫夫曼树与赫夫曼编码，再开始本组练习。

环境、输入与预期输出

环境：任意现代浏览器；综合题建议准备纸笔或本地编辑器。
输入：20 道四选一选择题，5 道综合题。
预期输出：一份独立作答记录，以及每道错题或综合题的完整推理过程。

作答方法

选择题先独立判断并记录依据，再点击“提交答案”；
提交后核对正确答案和解析，做错的题使用“重新作答”；
综合题先完成推导、伪代码或代码，再展开参考答案逐项核对；
对易混概念主动构造反例，说明条件变化后结论是否仍成立。

选择题

答题进度已答 0/20正确 0

第 1 题

难度★★★考点二叉树基础（性质+存储）、哈夫曼树与编码、哈夫曼树、完全二叉树、树的性质

对 n (n≥ 2) 个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是( )。

该树一定是一棵完全二叉树

树中一定没有度为 1 的结点

树中两个权值最小的结点一定是兄弟结点

树中任一非叶结点的权值一定不小于下一层任一结点的权值

第 2 题

难度★★★★考点哈夫曼树与编码、哈夫曼树、三叉、WPL、补虚节点

已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权(外部)路径长度最小是( )。

第 3 题

难度★★考点哈夫曼树与编码、前缀编码、哈夫曼编码、唯一可译

5 个字符有如下 4 种编码方案，不是前缀编码的是( )。

01, 0000, 0001, 001, 1

011, 000, 001, 010, 1

000, 001, 010, 011, 100

0, 100, 110, 1110, 1100

第 4 题

难度★★★★考点哈夫曼树与编码、哈夫曼树、路径权值、父子和

下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是( )。

24, 10, 5 和 24, 10, 7

24, 10, 5 和 24, 12, 7

24, 10, 10 和 24, 14, 11

24, 10, 5 和 24, 14, 6

第 5 题

难度★★★考点哈夫曼树与编码、哈夫曼编码、前缀码、译码

已知字符集 {a, b, c, d, e, f, g, h}，若各字符的哈夫曼编码依次是

0100, 10, 0000, 0101, 001, 011, 11, 0001

则编码序列 0100011001001011110101 的译码结果是( )。

a c g a b f h

a d b a g b b

a f b e a g d

a f e e f g d

第 6 题

难度★★★★考点哈夫曼树与编码、哈夫曼编码、前缀码、WPL

已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为 6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是( )。

00, 1011, 01, 1010, 11, 100

00, 100, 110, 000, 0010, 01

10, 1011, 11, 0011, 00, 010

0011, 10, 11, 0010, 01, 000

第 7 题

难度★★考点哈夫曼树与编码、哈夫曼树、哈夫曼编码、严格二叉树

对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有 115 个结点，则 n 的值是( )。

第 8 题

难度★★★考点哈夫曼树与编码、哈夫曼树、WPL、贪心合并

若某二叉树有 5 个叶结点，其权值分别为 10、12、16、21、30，则其最小的带权路径长度(WPL)是( )。

200

208

289

第 9 题

难度★★★考点二叉树基础（性质+存储）、哈夫曼树与编码、哈夫曼树、定长编码、二叉树性质

对任意给定的含 n (n > 2) 个字符的有限集 S, 用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。下列叙述中，正确的是 ( )。

T1 与 T2 的结点数相同

T1 的高度大于 T2 的高度

出现频次不同的字符在 T1 中处于不同的层

出现频次不同的字符在 T2 中处于相同的层

第 10 题

难度★★★考点哈夫曼树与编码、哈夫曼树、加权平均长度、WPL、哈夫曼编码

在由 6 个字符组成的字符集 S 中，各个字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼树的加权平均长度为( )。

2.4

2.5

2.67

2.75

第 11 题

难度★★★★考点哈夫曼树与编码、哈夫曼编码、哈夫曼树、编码长度、WPL

设字符集 S 包含 7 个字符，各字符出现的频次分别是 2, 3, 4, 6, 8, 10, 11。为 S 中的各字符构造哈夫曼编码，编码长度不小于 3 的字符个数是( )。

第 12 题

难度★★★考点哈夫曼树与编码、哈夫曼树、WPL、结点深度

假设二叉树中节点权值为 a=1, b=2, c=4, d=5, e=8, f=10, g=12。当带权路径长度 (WPL) 最小时，与节点 e（权值 8）处于相同深度的节点是哪些？

d, f

f, g

第 13 题

难度★★★考点哈夫曼树与编码、哈夫曼树、贪心合并、根结点

字符 a, b, c, d, e 的权值依次为 1, 4, 9, 16, 25。按标准哈夫曼构造算法（每次从森林中取出权值最小的两棵子树合并）建出哈夫曼树。构造完成后，哈夫曼树根结点的两个孩子结点的权值分别是( )。

5 和 9

9 和 46

25 和 30

14 和 41

第 14 题

难度★★考点哈夫曼树与编码、哈夫曼树、性质辨析、严格二叉树

关于哈夫曼树的性质，下列说法正确的是( )。

哈夫曼树是平衡二叉树（AVL 树）

哈夫曼树中权值较大的叶子距根不会比权值较小的叶子更远

含 n 个叶子结点的哈夫曼树共有 2n+1 个结点

给定一组互不相同的权值，对应的哈夫曼树形态唯一

第 15 题

难度★★★考点哈夫曼树与编码、哈夫曼树、构造过程、合并步骤

字符 a, b, c, d, e, f 的权值依次为 2, 3, 6, 8, 9, 13。按标准哈夫曼算法构造哈夫曼树。在整个构造过程中第 3 次合并产生的新内部结点权值是( )。

第 16 题

难度★★★考点哈夫曼树与编码、WPL、带权路径长度、哈夫曼树

字符 a, b, c, d, e 的权值分别为 2, 4, 5, 7, 12。按标准哈夫曼算法构造哈夫曼树，则该树的带权路径长度 WPL 为( )。

第 17 题

难度★★★考点哈夫曼树与编码、哈夫曼树、结点数、严格二叉树、性质

一棵哈夫曼树共有 25 个结点（包括叶子和内部结点）。该树用于编码的字符（叶子）个数 n 是( )。

第 18 题

难度★★★★考点哈夫曼树与编码、哈夫曼树、同权合并、早入森林优先、构造步骤

字符 a, b, c, d, e, f, g 的权值依次为 1, 2, 3, 3, 5, 8, 14。按本组约定（同权时早入森林优先；新合并出的子树排在原叶子之后）构造哈夫曼树，在构造过程中第 4 次合并产生的新内部结点是由哪两棵子树合并得到的( )?

"由 c、d 合成的权 6 子树" + "由 a、b、e 合成的权 8 子树"

"由 c、d 合成的权 6 子树" + 单叶 f（权 8）

单叶 f（权 8）+ "由 a、b、e 合成的权 8 子树"

单叶 e（权 5）+ 单叶 f（权 8）

第 19 题

难度★★★★考点哈夫曼树与编码、WPL、哈夫曼树、非叶子之和、合并验证

字符 a, b, c, d, e, f 的权值分别为 2, 3, 6, 9, 14, 25。按标准哈夫曼算法构造哈夫曼树，该树的 WPL 为( )。

129

188

132

第 20 题

难度★★★★考点哈夫曼树与编码、哈夫曼编码、编码生成、左0右1

字符 a, b, c, d, e 的权值分别为 4, 6, 7, 9, 14。按标准哈夫曼算法构造哈夫曼树（权小者作左孩子），并按"左 0 右 1"约定生成哈夫曼编码。字符 e（权值 14）的哈夫曼编码是( )。

110

答案总览（建议完成全部题目后查看）

第 1 题：A
第 2 题：B
第 3 题：D
第 4 题：D
第 5 题：D
第 6 题：A
第 7 题：C
第 8 题：B
第 9 题：D
第 10 题：B
第 11 题：D
第 12 题：D
第 13 题：C
第 14 题：B
第 15 题：C
第 16 题：B
第 17 题：B
第 18 题：B
第 19 题：B
第 20 题：B

综合题

综合题 1

难度：★★★★ · 分值：10 分

考点：哈夫曼树与编码、归并排序、哈夫曼树、多有序表合并、最优合并策略

设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：

(1) 给出完整的合并过程，并求出最坏情况下比较的总次数。

(2) 根据你的合并过程，描述 N（N ≥ 2）个不等长升序表的合并策略，并说明理由。

参考答案与详细解析

详细解析

预备：合并两个有序表的最坏比较次数

合并长度分别为 a、b 的两个升序表（归并步），最坏情况下比较次数 = a + b − 1（最后一个元素无需比较即可放入位置）。总比较次数 = 各次合并的代价之和。

要让总和最小，本质就是「构造一棵 N 个叶子的合并树（每片叶子是初始表），让"加权路径长度（WPL）"最小」——这正是哈夫曼树的目标，权值就是各表的长度。

(1) 6 个表的合并过程与最坏比较次数

答案：按哈夫曼策略每轮合并当前最短两个表，最坏总比较次数 = 825 次。

逐轮模拟（粗体为本轮选出的最短两个）：

轮	当前各表长度	选中合并	合并后表长	本次最坏比较
1	10, 35, 40, 50, 60, 200	10 + 35	45	10 + 35 − 1 = 44
2	40, 45, 50, 60, 200	40 + 45	85	40 + 45 − 1 = 84
3	50, 60, 85, 200	50 + 60	110	50 + 60 − 1 = 109
4	85, 110, 200	85 + 110	195	85 + 110 − 1 = 194
5	195, 200	195 + 200	395	195 + 200 − 1 = 394

总比较次数 = 44 + 84 + 109 + 194 + 394 = 825 次。

编者注（生僻术语）：部分教材把单次合并的代价简化记作 a + b（忽略 −1），按该口径总和会算成 45 + 85 + 110 + 195 + 395 = 830。常见解答通常接受两种口径，关键是策略正确（哈夫曼合并）+ 中间过程清晰。

(2) N 个不等长升序表的合并策略

策略：每次从当前所有有序表中挑出最短的两个进行合并，直到只剩一个表。等价于以各表长度为权值构造一棵 N 个叶子的哈夫曼树，按"自底向上"方式合并。

为什么这是最优的？

把每次合并视为合并树中一个内部结点：它的两个孩子是被合并的两个子表，该内部结点的"代价"= 左右子表长度之和（即被合并产生的新表长）；
总比较次数 = 所有内部结点代价之和 ≈ 所有叶子的（长度 × 该叶子在合并树中的深度）之和 = WPL（带权路径长度）；
哈夫曼算法（每次合并权值最小两棵子树）保证 WPL 最小——这是哈夫曼定理的直接应用。

直观理解：长表越早卷入合并，其每个元素就在后续合并中被搬动越多次（贡献到的内部结点越多）。最优策略是让长表"最后参与"、短表"最早合并掉"，正好对应"每次选最短的两个"。

实现要点：用小根堆维护当前所有表长。每次 pop 两个最小值 a、b，push a+b 回去，统计 a+b−1 次比较；重复 N−1 次。整体复杂度 O(N log N)。

综合题 2

难度：★★★ · 分值：10 分

考点：哈夫曼树与编码、树与森林、前缀编码、二叉树、译码、数据结构设计

任一个字符的编码都不是其它字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数 ≥ 2）的不等长编码，每个字符的编码均为二进制的 0、1 序列，最长为 L 位，且具有前缀特性。请回答下列问题：

(1) 哪种数据结构适宜保存上述具有前缀特性的不等长编码？

(2) 基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。

(3) 简述判定某字符集的不等长编码是否具有前缀特性的过程。

参考答案与详细解析

详细解析

(1) 适合存放前缀编码的数据结构

答案：二叉树（编码树 / 前缀码 trie）。

构造规则：

每个字符存放在一个叶子结点——保证从根到该叶子的 0/1 路径就是该字符的编码；
内部结点不存字符——只起"路径分叉"作用；
左分支记 0，右分支记 1（约定即可，反过来也行）；
树最多有 $L + 1$ 层（编码最长 L 位 → 路径最长 L 条边）。

为什么这种结构天然就是"前缀码"：因为字符只在叶子。叶子的祖先全是内部结点，任何字符的编码（根→叶子路径）都不可能是另一字符编码（也是根→另一叶子路径）的前缀——否则前者那个叶子会出现在后者的路径中间，与"叶子"地位矛盾。

编者注（生僻术语）：哈夫曼树（Huffman tree）就是这种"编码树"的一种特殊构造（按字符频率构造使加权路径长度最短）。本题不要求最优编码，任何"字符全在叶子"的二叉树都满足前缀特性。

(2) 译码过程

答案：从根开始，按位读 0/1 串，0 走左、1 走右；遇到叶子就输出该叶子上的字符并回到根；继续读下一位。直到 0/1 串读完。

伪代码：

text

cur ← 根
result ← 空字符串
对 0/1 串中每一位 b：
    若 b = 0：cur ← cur.left
    否则：    cur ← cur.right
    若 cur 是叶子：
        result ← result + cur.char
        cur ← 根         // 回到根，准备下一个字符
返回 result

关键点：

由于编码具备前缀特性，每次到达叶子的时刻是唯一确定的——没有"提前停下"或"该停而没停"的歧义；
若读完 0/1 串时 cur 不在根（说明最后一段路径走了一半还没到叶子），则 0/1 串本身有问题（不是合法编码）；
时间复杂度 $O (比特总数)$ ，每位常数次操作。

(3) 判定一组不等长编码是否具备前缀特性

答案：把每个编码作为一条 0/1 路径插入空二叉树，过程中违反以下两条之一即不具备前缀特性，全部插完未违反则具备：

"穿越"已有叶子：插入新编码时，途中走到了一个已经被标记为叶子的结点（说明已有某字符的编码是新编码的前缀）；
新叶子位置已是分叉：把新编码的最后一位走到的结点要标为新叶子，但这个结点已经有左/右孩子（说明新编码是某已有编码的前缀）。

伪代码：

text

建一棵只有根的空树
对每个字符的编码 code：
    cur ← 根
    对 code 中每一位 b：
        若 cur 已被标记为叶子：返回 "不具备前缀特性"   // 情况 1
        若 cur 沿 b 方向无孩子：建该孩子
        cur ← cur 沿 b 方向的孩子
    若 cur 已有孩子：返回 "不具备前缀特性"             // 情况 2
    把 cur 标记为叶子（绑定到当前字符）
返回 "具备前缀特性"

关键点说明：

两种违反情况对称：情况 1 是"老编码是新编码前缀"；情况 2 是"新编码是老编码前缀"；
复杂度 $O (\sum | 每个编码长度 |)$ ，即总比特数；最坏情况下 $O (k L)$ （k 个字符、最长 L 位）；
替代方法——也可以两两比较所有编码对，看一个是否是另一个的前缀串。但这要 $O (k^{2} L)$ ，比建树法慢，且代码更繁琐，不推荐。

综合题 3

难度：★★★ · 分值：12 分

考点：哈夫曼树与编码、哈夫曼树、Huffman编码、WPL、带权路径长度

本组统一约定：
构造规则：每一步从当前森林中取两棵权值最小的树，作为新节点的左右孩子合并；规定较小权值作左孩子、较大权值作右孩子（同值时取出顺序在前的作左孩子）
编码规则：从根到叶的每条路径，左分支记 0、右分支记 1
WPL（带权路径长度）： $WPL = \sum_{i} f_{i} \cdot l_{i}$ ，其中 $f_{i}$ 是叶子 $i$ 的权值（频次）、 $l_{i}$ 是叶子 $i$ 从根出发的路径长度（以边数计，根本身深度 0）

某文本中含有 6 个字符 $A, B, C, D, E, F$ ，统计后频次如下：

字符	A	B	C	D	E	F
频次	5	9	12	13	16	45

(1) 按本组构造规则与编码规则，画出对应的哈夫曼树。

(2) 计算该哈夫曼树的带权路径长度 WPL。

(3) 给出每个字符的哈夫曼编码，并计算平均码长（= WPL / 总频次）。

参考答案与详细解析

详细解析

(1) 哈夫曼树的构造

构造过程拆解（5 次合并 = 6 个叶子需要 6 - 1 = 5 次合并）

Step 1: 初始森林

森林按权值升序写出： ${A : 5, B : 9, C : 12, D : 13, E : 16, F : 45}$ 。

Step 2: 合并 $A$ 、 $B$ （取权值最小的两个）

最小两个： $A : 5$ 与 $B : 9$ ，合并为内部节点 $N_{1} = 5 + 9 = 14$ （A 作左孩子、B 作右孩子）。

森林： ${C : 12, D : 13, N_{1} : 14, E : 16, F : 45}$ （ $N_{1}$ 按权值 14 插入有序位置）。

text

14(5, 9)

Step 3: 合并 $C$ 、 $D$

最小两个： $C : 12$ 与 $D : 13$ ，合并为 $N_{2} = 25$ （C 左、D 右）。

森林： ${N_{1} : 14, E : 16, N_{2} : 25, F : 45}$ 。

text

25(12, 13)

Step 4: 合并 $N_{1}$ 、 $E$

最小两个： $N_{1} : 14$ 与 $E : 16$ ，合并为 $N_{3} = 30$ （ $N_{1}$ 左、E 右）。 $N_{1}$ 是子树根，其子树形态 14(5, 9) 整体作为 $N_{3}$ 的左子树。

森林： ${N_{2} : 25, N_{3} : 30, F : 45}$ 。

text

30(14(5, 9), 16)

Step 5: 合并 $N_{2}$ 、 $N_{3}$

最小两个： $N_{2} : 25$ 与 $N_{3} : 30$ ，合并为 $N_{4} = 55$ （ $N_{2}$ 左、 $N_{3}$ 右）。

森林： ${F : 45, N_{4} : 55}$ 。

text

55(25(12, 13), 30(14(5, 9), 16))

Step 6: 合并 $F$ 、 $N_{4}$ （最后一步）

最小两个： $F : 45$ 与 $N_{4} : 55$ ，合并为根 $N_{5} = 100$ （F 左、 $N_{4}$ 右）。

text

100(45, 55(25(12, 13), 30(14(5, 9), 16)))

最终哈夫曼树

为方便后续讨论，标出每个叶子对应的字符：

text

100(F45, 55(25(C12, D13), 30(14(A5, B9), E16)))

各叶子从根出发的路径长度（边数）：

叶子	A	B	C	D	E	F
权值 $f$	5	9	12	13	16	45
路径长度 $l$	4	4	3	3	3	1

(2) WPL 计算

方法 1：逐叶子相加（定义法）

WPL = \sum_{i} f_{i} \cdot l_{i}

叶子	$f$	$l$	$f \cdot l$
A	5	4	20
B	9	4	36
C	12	3	36
D	13	3	39
E	16	3	48
F	45	1	45

WPL = 20 + 36 + 36 + 39 + 48 + 45 = 224

方法 2：所有内部节点权值求和（复核用）

哈夫曼树有一个重要性质：WPL = 所有内部节点权值之和（每个内部节点权值 = 其所有后代叶子权值之和，所以一个叶子在每经过一个祖先内部节点时被加 1 次，恰好与其路径长度相等）。

内部节点	$N_{1}$	$N_{2}$	$N_{3}$	$N_{4}$	$N_{5}$
权值	14	25	30	55	100

WPL = 14 + 25 + 30 + 55 + 100 = 224 ✓

两种方法结果一致，互为独立验算。

(3) 哈夫曼编码与平均码长

按"左 0 右 1"约定，沿根到每个叶子的路径写出编码：

字符	从根的路径	编码	码长
F	左	`0`	1
C	右 → 左 → 左	`100`	3
D	右 → 左 → 右	`101`	3
E	右 → 右 → 右	`111`	3
A	右 → 右 → 左 → 左	`1100`	4
B	右 → 右 → 左 → 右	`1101`	4

前缀码合法性验证：6 个编码两两之间都不是彼此的前缀（任意取两个对比，都从某一位起字符相异）——这是哈夫曼编码"叶子才是有效编码、内部节点不参与"的天然保证。

平均码长：

\bar{l} = \frac{WPL}{\sum_{i} f_{i}} = \frac{224}{5 + 9 + 12 + 13 + 16 + 45} = \frac{224}{100} = 2.24

相比定长编码（6 个字符需 $⌈ \log_{2} 6 ⌉ = 3$ 位定长），哈夫曼编码节省 $(3 - 2.24) / 3 \approx 25.3 %$ 的码长——这就是变长前缀编码相对定长编码的压缩优势所在。

易错点

盲区 A：「同值并列时怎么选不定」
本题数据 $A : 5, B : 9, C : 12, D : 13, E : 16, F : 45$ 各不相同，构造过程没有同值并列。但教辅常见变体（如频次为 ${5, 5, 7, 8, 10}$ ）会出现"两个 5 并列最小、再选一个时还有第二个 5"的情形，此时哈夫曼树形态不唯一。
错误推演：学习者看到两个相同权值的子树，常常随意选一个左、一个右，但不同选法会得到拓扑不同的两棵哈夫曼树——叶子的路径长度可能各异，但WPL 必然唯一（因为只取决于"合并次数"与"权值和"的组合方式，而非具体的左右排布）。
正解共识：哈夫曼树形态不唯一，但 WPL 唯一。本组统一约定"较小权值作左孩子、同值时取出顺序在前的作左孩子"以保证答案的唯一性；如果题目没给约定，建议自行声明一个并坚持到底，避免后续 (3) 的编码与"标准答案"碰巧不一致。
盲区 B：「编码左右方向（左 0 右 1 vs 左 1 右 0）是约定」
不同教辅可能给"左 1 右 0"的相反约定，学习者套用本组"左 0 右 1"得到编码后看见参考答案不一致就慌乱。
错误推演：若按"左 1 右 0"，本题编码会变成 F=1、C=011、D=010、E=000、A=0011、B=0010——码长不变、WPL 不变、平均码长不变，但具体编码字符串相反。
正解共识：只要全程坚持一个约定，编码就合法（前缀性质与码长都由树形决定，不由 0/1 方向决定）。课程做题时若题目没明示，按本组"左 0 右 1"主流约定即可；若教辅有不同约定，全程对齐就不会错。
⚠️ 答题策略：课程大题里出现哈夫曼编码时，务必在答题开头一句话声明"约定左 0 右 1"，让阅卷者按你的约定核对——这是规避无谓扣分的关键习惯。
盲区 C：「构造时选最小两棵时漏掉刚合并的子树」
学习者第一次见哈夫曼构造时，常常在 Step 3 后只看原始 ${C, D, E, F}$ 选两个最小，忘记 $N_{1} : 14$ 也参与排序——即把"刚合并的子树"排除在"下一轮选择"之外。
错误推演：本题 Step 3 若忽略 $N_{1}$ ，应该是从 ${C : 12, D : 13, E : 16, F : 45}$ 选最小两个 $C : 12, D : 13$ （恰好正确，但运气好）。真正暴露错误是在后续：森林 ${14, 16, 25, 45}$ 时若漏掉 $N_{3} : 30$ 之类的中间节点，构造完全错位。
正解共识：哈夫曼构造是"森林森林森林"的迭代——每一步合并完产生的新节点立刻视作新树进入森林，与原始叶子（已合并的不再单独存在于森林）平等参与下一轮选择。没有"叶子优先"、没有"小子树优先"：唯一标准是"权值最小的两棵子树"。
盲区 D：「WPL 算成内部节点 + 叶子全求和」
方法 2 的"WPL = 内部节点权值之和"是个反直觉的公式，学习者容易记成"WPL = 所有节点权值之和"（即把叶子也加进去）。
错误推演：若误算 WPL = 内部 + 叶子 = $224 + (5 + 9 + 12 + 13 + 16 + 45) = 224 + 100 = 324$ ，与正确值 224 差了恰好"叶子频次之和"——这个差值就是"如果叶子也算作 1 次内部节点的贡献"对应的虚高量。
正解共识：叶子不参与 WPL 求和（叶子是"被路径长度加权"的对象，不是"贡献到 WPL 累加里"的内部节点）。方法 2 的"内部节点权值之和"等价于方法 1，因为每个内部节点的权值恰好是其所有后代叶子权值之和，而每个叶子被它的所有祖先内部节点（共"路径长度"个）各算 1 次——加起来正好是 $\sum f_{i} \cdot l_{i}$ 。
盲区 E：「平均码长用 WPL / 字符种类数」
学习者看到字符种类是 6 个，常错用 $\bar{l} = WPL / 6 = 224 / 6 \approx 37.3$ 。这显然不对。
错误推演：把"加权平均"算成"算术平均"是统计口径错位。 $\bar{l}$ 是"按出现频次加权的平均码长"，分母是"总字符数（含重复）"，不是"字符种类数"。
正解共识： $\bar{l} = \frac{\sum_{i} f_{i} \cdot l_{i}}{\sum_{i} f_{i}} = \frac{WPL}{\sum f_{i}}$ ，其中分子 $\sum f_{i} \cdot l_{i}$ 是总码长（所有出现的字符的编码长度之和）、分母 $\sum f_{i}$ 是总字符数。本题分母 = $5 + 9 + 12 + 13 + 16 + 45 = 100$ （恰好凑成 100 便于心算）。

最终答案

(1) 哈夫曼树形态：100(F:45, 55(25(C:12, D:13), 30(14(A:5, B:9), E:16)))
(2) WPL = 224
(3) 哈夫曼编码：F=0，C=100，D=101，E=111，A=1100，B=1101；平均码长 = 2.24

综合题 4

难度：★★★★ · 分值：12 分

考点：哈夫曼树与编码、哈夫曼树、WPL、优先队列、最小堆、算法设计

给定 $n$ 个字符的频次数组 $f r e q [0. . n - 1]$ （频次可能未排序），请构造该字符集的哈夫曼树并返回其带权路径长度 WPL（Weighted Path Length）。

哈夫曼构造规则（本组统一约定）：

维护一个最小优先队列（最小堆），初始放入所有 $n$ 个频次
重复 $n - 1$ 次：从队列中取两个最小值 $a, b$ ，将合并值 $a + b$ 累加到 WPL，把 $a + b$ 放回队列
直到队列只剩一个元素（即根节点权值），此时累加的合并值之和即为 WPL

为什么"合并值累加 = WPL"：哈夫曼树有性质 WPL = 所有内部节点权值之和。每次合并产生的新节点权值正是 $a + b$ ，是一个新的内部节点。 $n$ 个叶子的哈夫曼树共有 $n - 1$ 个内部节点，所以累加 $n - 1$ 次合并值就等于 WPL。

数据结构定义（C 语言，）：

#define MAXN 1001

/* freq[0..n-1]：n 个字符的频次（频次为非负整数，未排序）
   返回：该字符集哈夫曼树的 WPL */

函数签名：

int huffmanWPL(int freq[], int n);

约束：

$1 \leq n \leq 1000$ ， $0 \leq f r e q [i] \leq 10^{6}$
特殊约定： $n = 1$ 时，哈夫曼树退化为单一叶子节点，路径长度为 $0$ ，故 $WPL = 0$
时间复杂度： $O (n \log n)$ （ $n - 1$ 次堆操作，每次堆操作 $O (\log n)$ ）
空间复杂度： $O (n)$ （堆数组本身）

测试覆盖维度：

$n = 1$ （特殊约定 WPL = 0）
$n = 2$ （最小有效情形，一次合并）
$n = 5$ 一般情形（5 个不同频次）
$n = 8$ 满二叉树平衡形态（频次全等时哈夫曼树是平衡的）
全相同频次（任意 $n$ ，验证"同值取出顺序"不影响 WPL）
单频次极大值（验证不溢出）
$n$ 接近 $1000$ 大规模（验证 $O (n \log n)$ 算法时空可控）

参考答案与详细解析

详细解析

思路分析

核心难点：哈夫曼算法每一步都要从当前森林中取两个最小值——朴素做法是每次线性扫描找最小，复杂度 $O (n^{2})$ ；高效做法用最小堆（二叉堆），每次取最小 $O (\log n)$ ，总计 $O (n \log n)$ 。

两种解法对比：

解法 1（朴素 $O (n^{2})$ ）

arr = freq.copy()
size = n
wpl = 0
for _ in range(n - 1):
    # 找最小两个，线性扫描
    i1 = argmin(arr[0..size-1])
    swap arr[i1] with arr[size-1], size -= 1
    i2 = argmin(arr[0..size-1])
    swap arr[i2] with arr[size-1], size -= 1
    a, b = arr[size], arr[size+1]
    arr[size] = a + b
    size += 1
    wpl += a + b

时间 $O (n^{2})$ （ $n - 1$ 次合并，每次 $O (n)$ 找最小）
空间 $O (n)$
简单但慢， $n = 1000$ 时大约 $10^{6}$ 操作，仍可通过

解法 2（最小堆 $O (n \log n)$ ）

heap = build_min_heap(freq)
wpl = 0
for _ in range(n - 1):
    a = heap.pop_min()    # O(log n)
    b = heap.pop_min()    # O(log n)
    wpl += a + b
    heap.push(a + b)      # O(log n)
return wpl

时间 $O (n \log n)$
空间 $O (n)$
$n = 1000$ 时约 $10^{4}$ 操作，比解法 1 快 100 倍

为什么解法 2 更优：

渐近复杂度更低，适合 $n$ 大的真实场景
课程大纲明文考察"用优先队列实现哈夫曼算法"——解法 2 是教科书标准实现
堆 + 合并循环 + WPL 累加这三个组件可独立验证，工程上更便于调试

参考实现采用解法 2。

参考实现（C）

static int heap[2 * MAXN];   /* 最小堆静态数组（容量 2n 留余量） */
static int hsize;            /* 当前堆大小 */

static void siftDown(int i) {
    while (2 * i + 1 < hsize) {
        int c = 2 * i + 1;                              /* 左孩子 */
        if (c + 1 < hsize && heap[c + 1] < heap[c]) c++; /* 取较小孩子 */
        if (heap[i] <= heap[c]) break;                   /* 已满足堆序 */
        int t = heap[i]; heap[i] = heap[c]; heap[c] = t;
        i = c;
    }
}

static int popMin(void) {
    int top = heap[0];
    heap[0] = heap[--hsize];                            /* 末尾元素填顶 */
    siftDown(0);
    return top;
}

static void push(int v) {
    heap[hsize++] = v;                                  /* 末尾追加 */
    int i = hsize - 1;
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {      /* 向上调整 */
        int p = (i - 1) / 2;
        int t = heap[i]; heap[i] = heap[p]; heap[p] = t;
        i = p;
    }
}

int huffmanWPL(int freq[], int n) {
    if (n <= 1) return 0;                               /* 特殊约定：单字符 WPL = 0 */
    hsize = 0;
    for (int i = 0; i < n; i++) push(freq[i]);          /* 建堆 */
    int wpl = 0;
    for (int k = 0; k < n - 1; k++) {
        int a = popMin();
        int b = popMin();
        int merged = a + b;
        wpl += merged;                                  /* WPL = 所有内部节点权值之和 */
        push(merged);
    }
    return wpl;
}

复杂度证明

时间：

初始 $n$ 次 push 建堆：每次 $O (\log n)$ ，合计 $O (n \log n)$
主循环 $n - 1$ 次合并：每次两次 popMin 一次 push，共 $3 \cdot O (\log n) = O (\log n)$ ，合计 $(n - 1) \cdot O (\log n) = O (n \log n)$
总计 $O (n \log n) + O (n \log n) = O (n \log n)$

下界论证：哈夫曼问题至少需要"读完所有 $n$ 个频次" $Ω (n)$ + "排序 $n$ 个数" $Ω (n \log n)$ （基于比较的排序下界），所以 $Ω (n \log n)$ 是问题下界，本算法渐近最优。

空间：堆数组占 $O (n)$ ，递归栈无（用迭代实现 sift），其他常数变量 $O (1)$ 。总计 $O (n)$ 。

易错点

盲区 A：「合并次数错（ $n$ 次 vs $n - 1$ 次）」【算法层】
学习者易混淆"合并次数"。 $n$ 个叶子的哈夫曼树共有 $n - 1$ 个内部节点（二叉树性质 $n_{0} = n_{2} + 1$ 的反推：满二叉哈夫曼树里 $n_{1} = 0$ ，故 $n_{2} = n_{0} - 1 = n - 1$ ），所以恰好需要 $n - 1$ 次合并。
错误推演：若错写循环为 for (int k = 0; k < n; k++)，最后一次合并时堆里只剩 1 个元素，popMin 第二次调用会读到非法位置（hsize 变成负数或访问越界元素），即使没崩，WPL 也会多累加一次错误值。
正解共识： $n$ 个叶子 → $n - 1$ 个内部节点 → $n - 1$ 次合并，写成 for (k = 0; k < n - 1; k++) 或等价的循环条件 while (hsize > 1)。两种写法都对，但要明确"为什么是 $n - 1$ 次"。
盲区 B：「单字符（ $n = 1$ ）边界没处理」【元层-正确性认知】
$n = 1$ 时哈夫曼树退化为单一叶子节点，没有内部节点。算法循环 $n - 1 = 0$ 次，根本不进入合并，自然 $WPL = 0$ 。但学习者若没在题面看到这条特殊约定，可能尝试"让单字符也走一次合并"或返回 $f r e q [0]$ （认为单字符 WPL = 频次 × 1 = $f r e q [0]$ ）。
错误推演：若返回 $f r e q [0]$ ，会把"单字符的编码长度"误算为 $1$ 位——但实际上单字符没有"编码"概念（无须区分），约定 WPL = $0$ 更符合数学定义（路径长度为 $0$ 时无加权贡献）。
正解共识：题面明示约定 $n = 1$ 时 WPL = $0$ ，主流教辅、课程标准答案、本组约定都按此处理。代码层面用 if (n <= 1) return 0; 提前 return。
盲区 C：「同值取出顺序不影响 WPL，但影响树形」【算法层】
两个频次相同时（如 $f r e q = [5, 5, 7, 8]$ ），堆的"取出顺序"在标准最小堆实现下是确定但不唯一的（依赖建堆顺序与 sift 实现细节）。学习者若用"自己排序后顺序合并"的简化实现，可能得到与标准堆不同的取出顺序。
错误推演：学习者若以为"取出顺序不同 → WPL 不同"，会担心自己的实现是否"正确"。但实际上 WPL 只取决于合并次数与合并值之和——不同的同值排列产生的"哈夫曼树形态"可能不同，但每一步合并值之和恒等于"所有内部节点权值之和"，所以 WPL 必然唯一。
正解共识：WPL 是哈夫曼问题的唯一不变量（最小可能加权路径长度），同值取出顺序对树形有影响、对 WPL 无影响。测试验证 WPL 是否正确即可，不要求树形与"标准答案"完全一致。
盲区 D：「sift-down 时孩子比较方向错」【算法层】
siftDown 的核心是"找左右孩子中较小的那个，与当前节点比较"。学习者易写成"先比较当前节点与左孩子，再与右孩子分别比较两次"——两次比较看似"覆盖更广"，实际上会导致与较大孩子交换，破坏堆序。
错误推演：设当前节点 $h [i] = 5$ 、左孩子 $h [2 i + 1] = 7$ 、右孩子 $h [2 i + 2] = 3$ 。错误写法"若 $h [i] > h [2 i + 1]$ 则交换"看到 $5 < 7$ 不交换；接着判 $h [i] > h [2 i + 2]$ 看到 $5 > 3$ 交换，得到 $h [i] = 3, h [2 i + 2] = 5$ ——但左孩子还是 $7$ ，违反"父 $\leq$ 子"堆序（ $3 < 7$ 对，但若进一步对子树 sift， $5 > 7$ 是错的，因为左孩子位置仍是 $7$ ）。错误更隐蔽：表面看堆序可能在某些 case 下歪打正着，复杂 case 下出错。
正解共识：先选出"较小的孩子"，再决定要不要交换——即先在 2i+1 与 2i+2 之间挑较小的（设为 $c$ ），然后比较 $h [i]$ 与 $h [c]$ 。一次比较 + 一次潜在交换，逻辑清晰且正确。
盲区 E：「WPL 用"叶子频次 × 路径长度"求和而非"内部节点权值之和"」【元层-数据结构本质认知】
定义上 $WPL = \sum_{i} f_{i} \cdot l_{i}$ （叶子频次 × 路径长度），这是 WPL 的"原始定义"。但要按定义算 WPL，必须先显式构造哈夫曼树（保留树结构）、再 DFS 求每个叶子的深度、再加权求和——工程量明显更大（需要节点结构体 + 左右孩子指针 + DFS）。
错误推演：学习者若坚持按定义实现，会写出 ~100 行代码（节点结构 + 堆改成存节点指针 + 合并时 new 节点 + DFS 求深度 + 加权求和）。这是"哈夫曼完整实现"，超综合题工程量上限。
正解共识：利用哈夫曼树性质 WPL = 所有内部节点权值之和——每次合并产生的"合并值"恰好是一个新内部节点的权值，累加 $n - 1$ 次合并值即得 WPL。这个等价让 WPL 计算不需要保留树结构，只需在主循环里维护一个累加器 wpl，复杂度与空间都大幅简化。

最终答案

参考实现见上方"参考实现（C）"段。核心算法 ~38 行 C 代码（含最小堆静态实现 + 合并循环 + WPL 累加）。复杂度 $O (n \log n)$ ，空间 $O (n)$ 。

综合题 5

难度：★★★ · 分值：13 分

考点：哈夫曼树与编码、哈夫曼树、Huffman编码、解码、平均码长

本组统一约定：
构造规则：每一步从当前森林中取两棵权值最小的树，作为新节点的左右孩子合并；规定较小权值作左孩子、较大权值作右孩子（同值时取出顺序在前的作左孩子）
编码规则：从根到叶的每条路径，左分支记 0、右分支记 1
WPL（带权路径长度）： $WPL = \sum_{i} f_{i} \cdot l_{i}$ ，其中 $f_{i}$ 是叶子 $i$ 的权值（频次）、 $l_{i}$ 是叶子 $i$ 从根出发的路径长度（以边数计，根本身深度 0）
平均码长： $\bar{l} = WPL / \sum f_{i}$ （即"加权平均码长"，分母是总字符数含重复）

某文本中含有 5 个字符 $A, B, C, D, E$ ，统计后频次如下：

字符	A	B	C	D	E
频次	6	8	10	15	21

(1) 按本组构造规则与编码规则，画出对应的哈夫曼树，并列出每个字符的哈夫曼编码与码长。

(2) 计算该哈夫曼树的带权路径长度 WPL 与平均码长，给出两种独立方法互为验算。

(3) 对下列比特串按上述哈夫曼编码进行唯一解码，写出原文本：

0111101010

并简述"哈夫曼编码是前缀码"如何保证解码的唯一性。

参考答案与详细解析

详细解析

(1) 哈夫曼树的构造与字符编码

构造过程拆解（4 次合并 = 5 个叶子需要 5 - 1 = 4 次合并）

Step 1: 初始森林

森林按权值升序写出： ${A : 6, B : 8, C : 10, D : 15, E : 21}$ 。

Step 2: 合并 $A$ 、 $B$

最小两个： $A : 6$ 与 $B : 8$ ，合并为内部节点 $N_{1} = 6 + 8 = 14$ （A 作左孩子、B 作右孩子）。

森林： ${C : 10, N_{1} : 14, D : 15, E : 21}$ （ $N_{1}$ 按权值 14 插入有序位置）。

text

14(6, 8)

Step 3: 合并 $C$ 、 $N_{1}$

最小两个： $C : 10$ 与 $N_{1} : 14$ ，合并为 $N_{2} = 10 + 14 = 24$ （C 作左、 $N_{1}$ 作右； $N_{1}$ 已是子树根，其形态 14(6, 8) 整体作 $N_{2}$ 的右子树）。

森林： ${D : 15, E : 21, N_{2} : 24}$ 。

text

24(10, 14(6, 8))

Step 4: 合并 $D$ 、 $E$

最小两个： $D : 15$ 与 $E : 21$ ，合并为 $N_{3} = 15 + 21 = 36$ （D 左、E 右）。

森林： ${N_{2} : 24, N_{3} : 36}$ 。

text

36(15, 21)

Step 5: 合并 $N_{2}$ 、 $N_{3}$ （最后一步）

最小两个： $N_{2} : 24$ 与 $N_{3} : 36$ ，合并为根 $N_{4} = 24 + 36 = 60$ （ $N_{2}$ 左、 $N_{3}$ 右）。

text

60(24(10, 14(6, 8)), 36(15, 21))

最终哈夫曼树（标出字符）

text

60(24(C10, 14(A6, B8)), 36(D15, E21))

各叶子从根出发的路径长度（边数）：

叶子	A	B	C	D	E
权值 $f$	6	8	10	15	21
路径长度 $l$	3	3	2	2	2

字符编码（左 0 右 1）

按约定沿根到每个叶子的路径写出编码：

字符	从根的路径	编码	码长
C	左 → 左	`00`	2
A	左 → 右 → 左	`010`	3
B	左 → 右 → 右	`011`	3
D	右 → 左	`10`	2
E	右 → 右	`11`	2

前缀码合法性验证：5 个编码两两之间都不是彼此的前缀。逐对验证——

对	验证
C(`00`) vs A(`010`)	第 2 位 `0` vs `1`（A 第 2 位 1），分叉 ✓
C(`00`) vs B(`011`)	第 2 位 `0` vs `1`，分叉 ✓
A(`010`) vs B(`011`)	第 3 位 `0` vs `1`，分叉 ✓
C(`00`) vs D(`10`)	第 1 位 `0` vs `1`，分叉 ✓
C(`00`) vs E(`11`)	第 1 位 `0` vs `1`，分叉 ✓
A(`010`) vs D(`10`)	第 1 位 `0` vs `1`，分叉 ✓
其他对	类似可验证两两分叉 ✓

核心保证：哈夫曼树的叶子才是"有效编码"，内部节点不参与；任意两个叶子从根的路径在第一个不同处分叉——这是"前缀码"成立的几何根源。

(2) WPL 与平均码长

方法 1：逐叶子相加（定义法）

WPL = \sum_{i} f_{i} \cdot l_{i}

叶子	$f$	$l$	$f \cdot l$
A	6	3	18
B	8	3	24
C	10	2	20
D	15	2	30
E	21	2	42

WPL = 18 + 24 + 20 + 30 + 42 = 134

方法 2：所有内部节点权值求和（独立复核）

哈夫曼树性质：WPL = 所有内部节点权值之和（每个叶子在每经过一个祖先内部节点时被加 1 次，恰好与其路径长度相等）。

内部节点	$N_{1}$	$N_{2}$	$N_{3}$	$N_{4}$
权值	14	24	36	60

WPL = 14 + 24 + 36 + 60 = 134 ✓

两种独立方法结果一致，验算通过。

平均码长

总字符数（含重复）= $\sum f = 6 + 8 + 10 + 15 + 21 = 60$ 。

\bar{l} = \frac{WPL}{\sum f} = \frac{134}{60} = \frac{67}{30} \approx 2.2 \dot{3}

具体小数 = $2.2 \bar{3}$ （即 $2.2333 \dots$ 无限循环）。

关键数值二次验算（条 26）：

验算项	方法 1（逐叶子）	方法 2（内部和）	一致？
WPL	18+24+20+30+42 = 134	14+24+36+60 = 134	✓
总字符数	6+8+10+15+21 = 60	n/a	n/a
平均码长	134/60 ≈ 2.2333	同	✓

与定长编码对比：5 个字符的定长编码需 $⌈ \log_{2} 5 ⌉ = 3$ 位。哈夫曼平均码长 $2.2 \bar{3} < 3$ ，节省比例 $(3 - 67 / 30) / 3 = (90 / 30 - 67 / 30) / 3 = (23 / 30) / 3 = 23 / 90 \approx 25.6 %$ ——这就是变长前缀编码相对定长编码的压缩优势。

(3) 解码与前缀码唯一性

解码过程

待解码比特串： $0111101010$ （共 10 位）

按"从根出发，读 0 走左、读 1 走右，遇到叶子输出字符并回到根"的解码规则：

Step	当前位	累计读入	状态	动作
1	位 0 = `0`	`0`	根 → 左	走到 $N_{2}$
2	位 1 = `1`	`01`	$N_{2}$ → 右	走到 $N_{1}$
3	位 2 = `1`	`011`	$N_{1}$ → 右 = 叶子 B	输出 `B`，回根
4	位 3 = `1`	`1`	根 → 右	走到 $N_{3}$
5	位 4 = `1`	`11`	$N_{3}$ → 右 = 叶子 E	输出 `E`，回根
6	位 5 = `0`	`0`	根 → 左	走到 $N_{2}$
7	位 6 = `1`	`01`	$N_{2}$ → 右	走到 $N_{1}$
8	位 7 = `0`	`010`	$N_{1}$ → 左 = 叶子 A	输出 `A`，回根
9	位 8 = `1`	`1`	根 → 右	走到 $N_{3}$
10	位 9 = `0`	`10`	$N_{3}$ → 左 = 叶子 D	输出 `D`，回根

读完 10 位、恰好回到根（没有未消费的位），解码完成。

原文本 = BEAD

解码合法性验算（按编码反推）

按 (1) 的编码表反向编码 BEAD：

字符	编码
B	`011`
E	`11`
A	`010`
D	`10`

拼接 = 011 + 11 + 010 + 10 = 0111101010（3+2+3+2 = 10 位）✓ 与题面待解码串完全一致。

前缀码与解码唯一性

前缀码定义：编码集合中任意两个编码都不互为前缀。即不存在两个字符 $x, y$ 使得 $code (x)$ 是 $code (y)$ 的开头（前若干位）。

为什么前缀码保证解码唯一：

设比特串 $S = s_{0} s_{1} \dots s_{m - 1}$ ，从根出发按位下降——每读一位就沿"左 0 / 右 1"走一层；当走到一个叶子时，恰好读完了某个字符的完整编码（叶子对应该字符）。

不会"提前命中"：内部节点不是任何字符的编码——只有叶子是。读到内部节点不输出字符，继续读下一位
不会"错过命中"：从根到叶子的路径上不存在另一个叶子作为内部节点（哈夫曼树中所有字符都是叶子，路径上中间全是内部节点）——所以解码到叶子时别无选择，必须输出该字符
回根后下一字符独立：输出字符后回到根、从下一位开始解码——前一字符的解码不影响后一字符的判读

反例（如非前缀码会怎样）：假设 $code (A) = 01$ 、 $code (B) = 011$ （B 以 A 为前缀，非前缀码）。比特串 011 既可解为 A 后剩下 1（但 1 不是任何字符编码，解码失败），也可整体解为 B——歧义出现。

哈夫曼树的前缀码性是结构保证（不是约定保证）：

所有字符都是叶子（不是内部节点）
从根到任意叶子的路径不经过其他叶子（路径上的非端点全是内部节点）
所以任意两个字符编码（即"两个叶子从根的路径"）在第一个分叉处之后就完全分开，不可能一个是另一个的前缀

这是哈夫曼编码作为"无歧义变长编码"的几何根源。

易错点

盲区 A：「解码时'贪心读最短'反而失败」
学习者看到比特串第一反应是"贪心从最短编码开始匹配"——读 1 位看是不是某个 1 位编码、读 2 位看是不是某个 2 位编码……这其实没必要（前缀码已保证唯一解），但写代码时容易写错。
- 错误推演：读 0111101010 时，学习者看到 0 想：是不是 1 位编码？翻表无 1 位编码，读第 2 位 01——也无 01 编码，读第 3 位 011——有！B。但若编码表里同时有 01 编码（违反前缀码），学习者先匹配到 01 就停手了，漏掉 011 这种更长匹配。
- 正解共识：沿树下降而非"按长度试匹配"——从根出发按位走，遇叶即输出。哈夫曼前缀码保证"沿树下降"必落在唯一叶子，不存在"短码 vs 长码歧义"。本盲区命名为「贪心读最短陷阱」。
盲区 B：「左 0 右 1 vs 左 1 右 0 约定漂移」
不同教辅可能给"左 1 右 0"约定——若学习者按本组"左 0 右 1"得到编码后看见参考答案不一致就慌乱。
- 错误推演：若按"左 1 右 0"约定，本题编码变为 C=11、A=101、B=100、D=01、E=00——码长不变、WPL 不变、平均码长不变，但具体编码字符串相反。原文本 BEAD 在"左 1 右 0"约定下编码为 100 00 101 01 = 1000010101（10 位），与本题给出的 0111101010 处处相反。
- 正解共识：只要全程坚持一个约定，编码就合法。课程做题时若题目没明示约定，务必在答题开头声明"约定左 0 右 1"，让阅卷者按你的约定核对——这是规避无谓扣分的关键习惯。**
盲区 C：「解码到内部节点也输出字符」
有同学写解码代码时把"非根节点"误以为"叶子节点"——每走到一个非根节点就输出字符。
- 错误推演：在本题哈夫曼树上读位 01——走到 $N_{2}$ （内部节点），错解输出" $N_{2}$ "或乱码（ $N_{2}$ 不是字符，没有对应输出）；继续读位 1——本应继续走到 $N_{1}$ ，但错解可能"以为上一帧已输出"重新从根读，错位 1 位导致后续全错。
- 正解共识：只有叶子节点才有字符输出——内部节点是"路径中转点"，不输出。解码代码用 if (node->left == NULL && node->right == NULL) { 输出; 回根; } 判定叶子。本盲区命名为「叶子 vs 内部节点输出混淆」。
盲区 D：「平均码长按字符种类数算」
学习者看到 5 个字符种类，常错用 $\bar{l} = WPL / 5 = 134 / 5 = 26.8$ ——把"加权平均"算成"算术平均"。
- 错误推演：分母 5 是"字符种类数"，但平均码长定义里的分母应是"总字符数（含重复）" $\sum f$ 。本题 $\sum f = 60$ ，错解 $134 / 5 = 26.8$ ，比真实值 $2.2 \bar{3}$ 大了 12 倍——明显不合理（每个字符的编码长度都在 2-3 之间，平均不可能超过 3）。
- 正解共识： $\bar{l} = \frac{\sum_{i} f_{i} \cdot l_{i}}{\sum_{i} f_{i}} = \frac{WPL}{\sum f}$ ，分母是"总字符数（含重复）"。直觉验证：平均码长应介于最短编码长度（本题 2）与最长编码长度（本题 3）之间， $2 \leq \bar{l} \leq 3$ ； $2.2 \bar{3}$ 满足，26.8 显然不满足。
盲区 E：「构造时小权值不放左、大权值不放右」
- 错误推演：学习者若反过来"大权值作左、小权值作右"，构造出的树形与本题答案左右镜像——所有"左 0 右 1"编码变成镜像：原 C=00 变 11、原 A=010 变 101……码长不变、WPL 不变、平均码长不变，但每个字符的具体编码相反，解码结果也相反（待解码串 0111101010 在镜像约定下解为镜像字符）。
- 正解共识：形态约定决定具体编码，但不决定 WPL / 平均码长。考试做题前先看清题目给的约定（小左大右 / 大左小右 / 还是没约定），按约定执行；没约定就自己声明一个并坚持到底。

最终答案

(1) 字符编码：C=00、A=010、B=011、D=10、E=11；码长依次为 2、3、3、2、2
(2) WPL = 134；平均码长 $\bar{l} = 134 / 60 = 67 / 30 \approx 2.2 \bar{3}$
(3) 解码结果 = BEAD；前缀码保证解码唯一是因为"沿树下降必落于唯一叶子"——所有字符都是叶子，路径上不经过其他叶子，故任意两个编码的路径在第一个分叉处之后就完全分开

完成清单

20 道选择题均已独立作答，错题能说明其余选项为何不成立；
5 道综合题均已独立完成，并在展开解析前写出推导或算法；
能把本组题目涉及的关键性质、操作过程或算法复杂度说清楚；
已记录仍需回到教材复习的知识点。

复盘

哪道题最容易因结构关系、边界口径或算法步骤判断失误？
我能否不用背答案，重新画出结构或写出关键操作过程？
如果题目改变一个条件，原结论是否仍成立？

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

理论 Theory

实验 Exercise

工程 Project

目标 ​

前置知识 ​

环境、输入与预期输出 ​

作答方法 ​

选择题 ​

综合题 ​

综合题 1 ​

预备：合并两个有序表的最坏比较次数 ​

(1) 6 个表的合并过程与最坏比较次数 ​

(2) N 个不等长升序表的合并策略 ​

综合题 2 ​

(1) 适合存放前缀编码的数据结构 ​

(2) 译码过程 ​

(3) 判定一组不等长编码是否具备前缀特性 ​

综合题 3 ​

(1) 哈夫曼树的构造 ​

构造过程拆解（5 次合并 = 6 个叶子需要 6 - 1 = 5 次合并） ​

最终哈夫曼树 ​

(2) WPL 计算 ​

方法 1：逐叶子相加（定义法） ​

方法 2：所有内部节点权值求和（复核用） ​

(3) 哈夫曼编码与平均码长 ​

易错点 ​

最终答案 ​

综合题 4 ​

思路分析 ​

参考实现（C） ​

复杂度证明 ​

易错点 ​

最终答案 ​

综合题 5 ​

(1) 哈夫曼树的构造与字符编码 ​

构造过程拆解（4 次合并 = 5 个叶子需要 5 - 1 = 4 次合并） ​

最终哈夫曼树（标出字符） ​

字符编码（左 0 右 1） ​

(2) WPL 与平均码长 ​

方法 1：逐叶子相加（定义法） ​

方法 2：所有内部节点权值求和（独立复核） ​

平均码长 ​

(3) 解码与前缀码唯一性 ​

解码过程 ​

目标

前置知识

环境、输入与预期输出

作答方法

选择题

综合题

综合题 1

预备：合并两个有序表的最坏比较次数

(1) 6 个表的合并过程与最坏比较次数

(2) N 个不等长升序表的合并策略

综合题 2

(1) 适合存放前缀编码的数据结构

(2) 译码过程

(3) 判定一组不等长编码是否具备前缀特性

综合题 3

(1) 哈夫曼树的构造

构造过程拆解（5 次合并 = 6 个叶子需要 6 - 1 = 5 次合并）

最终哈夫曼树

(2) WPL 计算

方法 1：逐叶子相加（定义法）

方法 2：所有内部节点权值求和（复核用）

(3) 哈夫曼编码与平均码长

易错点

最终答案

综合题 4

思路分析

参考实现（C）

复杂度证明

易错点

最终答案

综合题 5

(1) 哈夫曼树的构造与字符编码

构造过程拆解（4 次合并 = 5 个叶子需要 5 - 1 = 4 次合并）

最终哈夫曼树（标出字符）

字符编码（左 0 右 1）

(2) WPL 与平均码长

方法 1：逐叶子相加（定义法）

方法 2：所有内部节点权值求和（独立复核）

平均码长

(3) 解码与前缀码唯一性

解码过程

解码合法性验算（按编码反推）

前缀码与解码唯一性

易错点

最终答案

完成清单

复盘