2. 从业资格
  3. 设有一份电文中共使用a、b、c、d、e、f这6个字符，它们的出现频率如下表所示，

设有一份电文中共使用a、b、c、d、e、f这6个字符，它们的出现频率如下表所示，

练习题库2022-08-02  40
问题 设有一份电文中共使用a、b、c、d、e、f这6个字符，它们的出现频率如下表所示，现通过构造哈夫曼树为这些字符编码。那么，编码长度最长的两个字符是（　　）。A.c、eB.b、eC.b、fD.e、f
选项 A.c、e
B.b、e
C.b、f
D.e、f
答案 C
解析 构造最优二叉树的哈夫曼算法如下：
①根据给定的n个权值{W1，W2，…，Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵树Ti中只有一个带权为Wi的根结点，其左右子树均空；
②在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和；
③从F中删除这两棵树，同时将新得到的二叉树加入到F中；
④重复②、③，直到F中只含一棵树时为止。这棵树便是最优二叉树（哈夫曼树）。
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和。根据算法，那么最长的路径应该就是b、f，故应选择C。
转载请注明原文地址:https://tihaiku.com/congyezige/2426639.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

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