问题
单项选择题
霍夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：i)以每个字符的出现频率作为关键字构建最小优先级队列；ii)取出关键字最小的两个结点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入到最小优先级队列中，直至得到一颗最优编码树。 霍夫曼编码方案是基于____(64)____策略的。用该方案对包含a到f六个字符的文件进行编码，文件包含100，000个字符，每个字符的出现频率(用百分比表示)如下表所示，则与固定长度编码相比，该编码方案节省了____(65)____存储空间。
（64）处填（）。
A．分治
B．贪心
C．动态规划
D．回溯
答案
参考答案：B
解析：
试题(64)、(65)分析 霍夫曼编码在构造最优编码树时，每次总是取出权值最小的两个结点来生成它们的父结点(新的中间结点)，因此霍夫曼编码方案是基于贪心策略的。对应该实例构造最优编码树如下图所示。
实例中包含6个字符，若用定长编码，则需要三位，对包含100，000个字符的文件，需要3*100，000＝300，000位的存储空间。而采用霍夫曼编码，则需要(18+26+32)*2+12*3+(4+8)*4＝236，000位的存储空间，节省了21％的存储空间。