CSP-J 入门级 · CSP 2021 入门级第一轮 第 11 题

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（ ）的策略。

这题其实就在考你对算法策略的直觉。拿到题别急着背定义，先想：哈夫曼树是怎么建出来的？每次都是挑频率最小的俩合并，绝不回头，也不管后面会不会更优。这种‘当下最优’的决策模式，一眼就能对应到贪心。

学生最容易把贪心和动态规划（D）搞混。为什么？因为贪心也是‘局部最优’，而动态规划也是‘局部最优’，但本质完全不同。贪心是‘一次决策定生死’，选了最小俩合并，后面不管怎么变，这步都不会反悔；动态规划则是‘步步为营’，每一步都要看所有子问题，甚至要倒推、要记录状态。哈夫曼编码里，每次合并后的新节点频率是确定的，不需要再重新计算其他路径，这就是贪心的铁证。如果你选了 D，多半是被‘最优子结构’这个词忽悠了——贪心也有最优子结构，但贪心不需要‘重叠子问题’，也不需要‘状态转移方程’。

这道题考查什么

哈夫曼编码的本质是贪心策略。

把概念说人话

哈夫曼编码是用来给字符设计二进制码的，目标是让总编码长度最短。怎么设计？先统计每个字符出现的频率，然后把所有字符放进一个优先队列（小根堆）。每次从堆里拿出频率最小的两个字符，把它们合并成一个新节点，新节点的频率就是这两个字符频率之和，再把新节点放回去。重复这个过程，直到堆里只剩一个节点，那它就是哈夫曼树的根。

命题人怎么挖坑

命题人最喜欢在‘局部最优’和‘全局最优’之间设陷阱。贪心算法的核心就是：每一步都选当前看起来最好的，希望这样能走到全局最好。哈夫曼编码完美符合这个套路——每次挑最小的俩合并，绝不回头，也不考虑‘万一以后有更小的组合怎么办’。动态规划虽然也追求全局最优，但它必须考虑所有子问题，甚至要倒推、要记录状态。哈夫曼编码里，每次合并后的新节点频率是确定的，不需要再重新计算其他路径，这就是贪心的铁证。

拿到题先想什么

看到‘哈夫曼编码’四个字，第一反应：它是怎么建出来的？第二步：建的过程中有没有‘回头’或者‘重新计算’？第三步：有没有‘状态转移’？如果都没有，那基本可以锁定贪心。

一步步推

1. 把所有字符按频率放入优先队列（小根堆）。 2. 每次取出频率最小的两个节点，合成一个新节点。 3. 新节点频率 = 两者之和，再入队。 4. 重复直到只剩一个节点（即哈夫曼树的根）。

每次选择最小的两个合并——这就是贪心策略的体现（局部最优→全局最优）。

选 B（贪心）。

考频与趋势

哈夫曼树在题库中已考过 44 题，覆盖 5 个级别，近年考频明显上升：2023 年 5 题、2024 年 10 题、2025 年 10 题、2026 年 11 题，说明命题人越来越喜欢拿它当‘概念辨析’的载体。贪心算法共考过 71 题，分布较广，2024 年 16 题、2025 年 12 题、2026 年 24 题，显示贪心仍是高频考点。

预测

基于上述数据，未来 1-2 年内，哈夫曼树很可能继续以‘概念辨析’或‘简单计算’的形式出现，尤其是和贪心、动态规划的对比题。暂无足够依据预测具体年份或题型变体。