NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 7 题

最优前缀编码，也称 Huffman 编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码，以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。

这题考前缀编码定义。拿到选项别急着看长度，直接拿最短的那串去套最长的：看长的有没有以短的开头，有就不是合法前缀编码。

最容易栽跟头的是选错D。D里确实有个1，但仔细看剩下全是0开头，1跟它们毫无前缀关系，所以D是合法的。真正不合法的是B，因为B里出现了0和00、1和11这种短串是长串前缀的情况，只要有一对触犯定义，整个编码组合就作废。

考点与概念

最优前缀编码（Huffman 编码）的核心要求只有一条：任意一个编码都不能是另一个编码的前缀。所谓“前缀”，就是短的串能完整地出现在长的串开头。满足这一条，解码时读到一串比特就能立刻确定是哪个字符，不会出现歧义。

命题人怎么挖坑

这类单选最爱在“看起来像前缀”的地方下套： 1. 把短串和长串都塞进同一个选项，诱导你只挑出那个短串，却忘了检查它是不是真的在长串开头。 2. 故意放一个孤立短串（比如 D 里的 1），让你误以为它一定有问题，其实它跟其他全是 0 开头的串毫无关系。 3. 用典型哈夫曼树结构（如 C）作为干扰项，让你下意识觉得“哈夫曼编码一定对”，从而忽略定义本身。