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

哈夫曼编码是一种有损压缩算法。

哈夫曼编码的核心是变长编码，但解码能完全还原原数据，所以它属于无损压缩，题目说‘有损’是错的。

学生容易把‘编码’等同于‘丢信息’，或者混淆JPEG/MP3等媒体压缩与哈夫曼编码的区别，导致误选A。

考点定位

本题考查数据压缩类型（有损 vs 无损）的基本概念，属于GESP六级《信息学基础》中“算法与数据结构”模块的常考知识点。命题人专门在此处挖坑，利用考生对“编码”一词的泛化理解，把“有损压缩”这个术语当作所有压缩算法的默认属性，从而诱导望文生义的误判。

概念厘清

在信息学里，压缩分两种：

• 有损压缩：丢弃部分信息以换取更高压缩比，比如JPEG图像、MP3音频，解码后无法100%还原原数据。
• 无损压缩：不丢任何信息，解码后能完全恢复原数据，比如ZIP、哈夫曼编码、LZW等。

哈夫曼编码的核心是构建最优二叉树：统计每个字符出现频率（权值），每次合并权值最小的两个节点，最终得到一棵带权路径长度（WPL）最小的二叉树。每个字符对应一个从根到叶子的路径，路径上左走记0、右走记1，就得到该字符的变长编码。

关键点在于：编码过程只改变表示方式，不丢弃任何比特。解码时，从根开始按编码串走，走到叶节点就输出对应字符，这个过程是严格可逆的。因此哈夫曼编码属于无损压缩。

命题视角与思考心法

拿到这类判断题，先别急着背结论，按这个顺序想： 1. 它丢不丢信息？ 只要解码能100%还原，就是无损；否则是有损。 2. 它叫“编码”还是“压缩”？ “编码”只是变长表示，不等于丢信息；“压缩”是目的，但实现方式决定有无损。 3. 有没有混淆场景？ 比如JPEG先做DCT变换再量化（丢高频），最后才用哈夫曼编码。此时哈夫曼只是最后一道工序，整体仍是有损压缩，但哈夫曼算法本身仍是无损的。

陷阱拆解

本题的坑在于“有损”二字偷换概念——JPEG/MP3确实丢弃信息，但哈夫曼编码只统计词频、分配码长，不丢弃任何比特。若考生只背“编码必丢信息”的片面结论，就会误选A。更阴险的是把“有损压缩”这个术语当作“压缩算法”的默认属性，仿佛所有压缩都得牺牲精度，这是典型的望文生义。

反命题思维

若改成“哈夫曼编码属于无损压缩算法”，答案变A；若改成“JPEG采用哈夫曼编码”，答案变B（JPEG先丢信息再哈夫曼）。刷到类似题先问自己“它丢不丢信息”——这是区分有损/无损的唯一本质标准，而非看它叫“编码”还是“压缩”。

考频趋势

哈夫曼树在题库共考过44题，覆盖5个考试级别（2009-2026）；逐年分布：2009年1题、2011年2题、2015年1题、2021年1题、2022年1题、2023年5题、2024年10题、2025年10题、2026年11题、null年2题；分赛事：GESP六级31题、GESP七级5题、CSP入门级4题、NOIP提高组初赛3题、NOIP普及组初赛1题。基础算法共考过30题，覆盖3个考试级别（2007-2025）；逐年分布：2007年2题、2008年1题、2009年4题、2010年4题、2011年5题、2012年1题、2013年1题、2014年2题、2016年1题、2019年1题、2021年4题、2024年2题、2025年2题；分赛事：NOIP提高组初赛13题、CSP提高级9题、NOIP普及组初赛8题。

预测

从数据看，哈夫曼树近四年考频飙升（2024年10题、2025年10题、2026年11题），且GESP六级占比最高（31题）。未来六级仍可能高频考查哈夫曼编码与无损压缩的辨析，或结合其他编码（如算术编码、LZW）对比考“丢不丢信息”。暂无足够依据预测具体题型变化。