(2012年下半年上午试题64、65)哈夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：i)以每个字符的出现频率作为关键字构建最小优先级队列；ii)取出关键字最小的两个节点生成子树，根节点的关键字为孩子节点关键字之和，并

admin2021-01-13 92

问题 (2012年下半年上午试题64、65)哈夫曼编码将频繁出现的字符采用短编码，出现频率较低的字符采用长编码。具体的操作过程为：i)以每个字符的出现频率作为关键字构建最小优先级队列；ii)取出关键字最小的两个节点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入最小优先级队列中，直至得到一棵最优编码树。哈夫曼编码方案是基于_______(64)策略的，用该方案对包含a到f六个字符的文件进行编码，文件包含100000个字符，每个字符的出现频率(用百分比表示)如表9．3所示，则与固定长度编码相比，该编码方案节省了_______(65)存储空间。

(64)

选项 A、分治
B、贪心
C、动态规划
D、回溯

答案B

解析贪心算法在解决最优化问题上是仅根据当前已有的信息做出选择，即不是从整体最优考虑，它所做出的选择只是力求局部最优。本题给出的哈夫曼编码操作过程基于典型的贪心策略。
采用固定长度编码，需要3位二进制数字来表示6个字符，即a=000，b=001，c=010，d=011，e=100，f=101。这种方法需要300000位来对整个原文件编码。采用哈夫曼编码，频繁出现的字符采用短编码，出现频率较低的字符采用长编码，这种编码方式需要(32×1+26×3+18×3+12×3+4×4+8×4)×1000=248000位。因此，与固定长度编码相比，该编码方案节省的存储空间为(300000-248000)／300000=17．3％。

转载请注明原文地址:https://kaotiyun.com/show/4tCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类