GESP 六级 · GESP 202412 C++ 六级 第 7 题

已知字符集 $\{A, B, C, D\}$ 的出现频率如下表所示：

根据哈夫曼编码法，下面（ ）是正确的哈夫曼树。


位运算：&（与）、|（或）、^（异或）、~（取反）、<<（左移）、>>（右移）。异或性质：a^a=0，a^0=a。

区分逻辑运算(&&,||,!)和位运算(&,|,~,!)。左移右移注意符号位的处理（算术右移vs逻辑右移）。负数的位运算要小心。

【考点】哈夫曼树构造｜二叉树合并｜贪心策略

1. 考纲定位：本题考查 GESP 六级《数据结构与算法》模块中"哈夫曼编码"知识点，命题人借构造二叉树的过程，卡住大量考生对"取最小两节点合并"这一核心操作的理解。

2. 解题思维：按频率排序 C(1) B(3) D(6) A(8)，依次合并 C+B→4，再合并 4+D→10，最后合并 8+10→18，得到与选项 A 完全一致的树形。关键步骤是每次从当前节点集合中挑出两个最小权重节点合并，形成新的内部节点。

3. 陷阱拆解：B 项误将 A 与 B 先合并（贪心失效），C 项把 B 与 C 合并后却把 D 挂在更浅层（违反最优性），D 项则把 C 挂在最底层（权重 1 的节点应尽可能深）。命题人利用"按字母顺序合并""只看局部最小""误读图示"等常见误区，让背结论者直接掉坑。

4. 反命题思维：若改频数为 A=5 B=5 C=5 D=5，哈夫曼树不再唯一，命题人会转而考"多解情形下的任意合法树"。刷到类似题先问自己：当前集合里哪两个最小？合并后新节点权重是多少？树形是否还满足最优子结构？