(接64题)该编码方案节省了(65)存储空间。A.21%B.27%C.18%D.36%

Question

(接64题)该编码方案节省了（65）存储空间。

A.21%

B.27%

C.18%

D.36%

Answer 1

正确答案：A
根据题目对霍夫曼编码的描述，我们不难知道，每次都是选择当前最小的情况，这符合贪心算法总是找当前看来最优的情况，因此属于贪心策略。如果对包含100,000个字符，且这些字符都属于a到f。那么如果采用固定长度的编码，针对于每个字符需要3位来编码（因为有6个不同的字符，至少需要3位才能表示6种不同的变化）。那么对100000个字符编码，其编码长度为300000。如果采用霍夫曼编码，那么首先我们就要根据字符出现的频率构造出其霍夫曼树。首先选择出现频率最低的4和8，生成子树，其父节点为12，然后放入出现频率队列中，后面的采用同样的道理，以此类推。构造出的霍夫曼树如下图所示：由图可以知道，a的编码为00，b的编码为11，c的编码为0100，d的编码为0101，e的编码为011，f的编码为10。因此总的编码长度为（2*18%+2*32%+4*4%+4*8%+3*12%+2*26%）*100000=23600，因此节省的存储空间大小为30000-23600=6400。因此节省的存储空间为比例为6400/30000=21%。