2. 从业资格
  3. 已知某文档仅包含6种不同的字符，其每个字符出现的频率如下表所示，采用霍夫曼编码对

已知某文档仅包含6种不同的字符，其每个字符出现的频率如下表所示，采用霍夫曼编码对

免费题库2022-08-02  66
问题 已知某文档仅包含6种不同的字符，其每个字符出现的频率如下表所示，采用霍夫曼编码对该文档压缩存储，则单词“face”的编码为（　　），该文档的压缩比为（　　）。问题1选项A.110001001101B.101000010100C.001101001100D.110101001100问题2选项A.20%B.25%C.30%D.40%
选项
答案 AB
解析 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+…+ Wn*Ln)，N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树的WPL是最小的。构造哈夫曼树的算法如下：1）对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,…,Ti,…, Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。4）重复2）和3），直到集合F中只有一棵二叉树为止。用二叉树设计二进制前缀编码：以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’； 每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。构造的哈弗曼树和节点编码如下所示：对应各字符的编码为：a（0）、b（101）、c（100）、d（111）、e（1101）、f（1100）face的编码为：1100 0 100 1101平均码长 =0.45╳1+0.12╳3+0.13╳3+0.16╳3+0.05╳4+0.09╳4=0.45+0.36+0.39+0.48+0.20+0.36=2.24由于6个字符，至少需要3位二进制才能完成编码。压缩比为：1-2.24/3=0.25
转载请注明原文地址:https://tihaiku.com/congyezige/2418134.html
本试题收录于： 中级 软件评测师题库软件水平考试初中高级分类

中级 软件评测师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)