题4

题4

题目

设哈夫曼编码的长度不超过 4 , 若已对两个字符编码为 1 和 01 , 则还最多可对 ( ) 个字符编码.
A. 2
B. 3
C. 4
D. 5

分析

那么1和01就不能是新编码的子串，也就是第一个元素不能是1
那么第一个元素只能是0
同时前缀里也不能右01
那么第二个元素只能是0
也是00xx这种结构
后面两个xx，每个右两种选法，一共四种串

解

C
在哈夫曼编码中, 一个编码不能是任何其他编码的前缀。
3 位编码可能是 001 , 对应的 4 位编码只能是 0000 和 0001。
3 位编码也可能是 000 , 对应的 4 位编码只能是 0010 和 0011 。
若全采用 4 位编码,则可以为 和 0011 。
题中问的是最多,所以选择选项 C。
【另解】若哈夫曼编码的长度只允许小于或等于 4 , 则哈夫曼树的高度最高是 5 , 已知一个字符编码为 1, 另一个字符编码是 01 , 这说明第二层和第三层各有一个叶结点, 为使得该树从第 3 层起能够对尽可能多的字符编码, 余下的二叉树应该是满二叉树, 如下图所示, 底层可以有 4 个叶结点, 最多可以再对 4 个字符编码。