GESP 六级 · GESP 202309 C++ 六级 第 9 题

某内容仅会出现 ABCDEFG ，其对应的出现概率为 0.40、0.30、0.15、0.05、0.04、0.03、0.03，如下图所示。

按照哈夫曼编码规则，假设 B 的编码为 11 ，则 D 的编码为（ ）。


先按频率从小到大两两合并建哈夫曼树，再根据已知B的编码11反推树形，最后读出D的路径即可。

学生容易只算编码长度而忽略具体路径，或者在合并时把相同频率的节点顺序搞混。本题陷阱在于若先合并0.04与0.05得到0.09，再与0.06合并时，若把0.15当作原字符E而非合并节点，会导致树形错位，从而算出错误编码。正确做法是严格按频率自底向上合并，确保B的编码为11时树形唯一，再据此确定D的编码。

【考点】哈夫曼树构造｜哈夫曼编码｜二叉树遍历

哈夫曼编码的核心是：按字符频率从小到大两两合并，每次将最小的两个频率相加生成新节点，继续合并直到只剩一棵树。编码规则通常是“左支标0、右支标1”，从根到叶子的路径即为该字符的编码。本题已知B的编码为11，说明从根到B的路径是右‑右，这直接锁定了树形结构。

具体构造过程：

• 将7个频率排序：0.03, 0.03, 0.04, 0.05, 0.15, 0.30, 0.40
• 合并两个0.03 → 0.06（记为X）
• 合并0.04与0.05 → 0.09（记为Y）
• 合并X(0.06)与Y(0.09) → 0.15（记为Z）
• 合并原E(0.15)与Z(0.15) → 0.30（记为W）
• 合并原D(0.30)与W(0.30) → 0.60（记为V）
• 合并V(0.60)与原A(0.40) → 1.00（根）

此时根只有两个子树：左子树A，右子树V。右子树V的左孩子是D，右孩子是W；继续展开W：左孩子是E，右孩子是Z；Z的左孩子是Y，右孩子是X；Y的左孩子是0.04，右孩子是0.05；X的左孩子是0.03，右孩子是0.03。

已知B的编码为11，对应路径右‑右，说明B位于根→V→W→Z→X→右。检查树形：根→右是V，V→右是W，W→右是Z，Z→右是X，X→右是0.03（即B）。完全吻合，树形唯一确定。

现在求D的编码：从根出发，D是V的左孩子，路径为左‑右‑左。按“左0右1”规则，D的编码为10011。

【命题视角】这类题常考“已知部分编码反推整棵树”，因为只背长度无法应对。命题人会在合并顺序、相同频率节点优先级、左右分支约定上设坑，比如把0.15当作原字符而非合并节点，导致树形错位，编码串自然不同。

【避坑】若按相反约定（左1右0）会算出10111，对应选项C，这是典型陷阱。务必先根据已知B=11验证树形方向，再推导其他字符。

【考频与趋势】哈夫曼树在题库共44题，2023年5题、2024年10题、2025年10题、2026年11题，六级占比31题，说明该考点近年高频且六级仍是主力。图形结构213题中六级26题，图的基本概念281题中六级27题，组合数学与排列组合在六级也占一定比例，整体趋势是图形与组合类题目持续升温。

【预测】基于2024-2026三年六级哈夫曼树考题数量激增，未来六级很可能继续以“已知编码反推树形”或“结合图形遍历”的形式出现，难度略有提升。暂无足够依据预测具体年份，但建议重点复习哈夫曼树构造与编码反推，这是六级的高频得分点。