北京海淀区信息学竞赛 · 2024 北京市海淀区信息学竞赛（初赛）试题 第 9 题

已知字符集 $\{a, b, c, d, e, f, g, h\}$，如果给每个字符进行编码，字符与编码对应如下：

则编码序列 $0100011001001011110101$ 的译码结果分别是（　　）

这道题考的是前缀编码（变长编码）的译码，拿到题先想：编码有没有前缀冲突？没有的话直接按长度贪心匹配，遇到歧义再回溯。

学生容易把编码当成定长处理，或者没发现'001'和'0000'的前缀关系导致乱匹配；还有人会把连续子串和子序列混淆，这里其实是按编码表逐段切分，不是子串计数；另外容易漏掉'0001'和'001'的冲突，导致译码串里多出一个字符或少一个。

这道题考查的是前缀编码（变长编码）的译码规则。核心概念很简单：每个字符对应一段二进制串，译码时从左到右读，只要当前读到的前缀在编码表里出现过，就立刻认定这是一个字符，然后从下一个位置继续——这就是“贪心”匹配，因为题目给的编码表没有前缀冲突（任何编码都不会是另一个编码的前缀），所以每一步都是确定的，不需要回溯。

命题人爱挖的坑就藏在“变长”和“前缀”上：很多学生会下意识用定长思维，比如看到'0100011001001011110101'就按3位切分，结果全错；还有人会把“子串”概念套进来，以为要枚举所有可能的子串再匹配，反而把自己绕晕。其实拿到题先想：有没有前缀冲突？没有的话直接按长度贪心匹配即可。

具体怎么算？先把编码表记熟：a=001, b=10, c=0000, d=0101, e=0100, f=011, g=11, h=0001。然后从左到右扫描编码串'0100011001001011110101'：

• 开头'0100'对应e，剩下'011001001011110101'；
• 接着'011'对应f，剩下'001001011110101'；
• 然后'001'对应a，剩下'001011110101'；
• 再'001'对应a，剩下'011110101'；
• 接着'011'对应f，剩下'110101'；
• 然后'11'对应g，剩下'0101'；
• 最后'0101'对应d。

所以译码结果是e, f, a, a, f, g, d，正好是选项D。

避坑指南：含重复字符的编码串，不同译码结果可能少于理论最大值；这里没有歧义，但学生容易在'001'和'0001'之间犹豫，或者把'0100'误看成'010'（不存在）导致卡住。记住：前缀编码的译码是确定性的，只要表里没前缀冲突，贪心走到底就是唯一答案。

考频与趋势：从历年真题看，这类“给定变长编码表，求译码结果”的题在信息学竞赛中属于高频考点，近3年海淀区、CSP-J/S初赛及复赛均多次出现，通常以单选或填空形式考查，难度中等，重在考察对编码规则和贪心策略的理解。未来命题可能继续用变长编码，但会加入少量前缀冲突或动态编码表，增加回溯判断的复杂度，同时可能结合字符串拼接、长度计算等知识点综合出题。暂无足够依据预测具体年份的题型变化，但掌握前缀编码的贪心译码是必做基础。