2. 计算机
  3. 由值为29、12、15、6、23的五个叶子结点构造的哈夫曼树为(64)，其带权路径长度为(65)。

由值为29、12、15、6、23的五个叶子结点构造的哈夫曼树为(64)，其带权路径长度为(65)。

admin2008-08-01  74
问题 由值为29、12、15、6、23的五个叶子结点构造的哈夫曼树为(64)，其带权路径长度为(65)。
选项 A、85
B、188
C、192
D、222
答案B
解析 本题考查哈夫曼树。
   构造最优二叉树的哈夫曼算法如下。
   ①根据给定的n个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…， Tn}，其中每棵树Ti中只有一个带权为wj的根结点，其左右子树均空。
   ②在9中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
   ③从9中删除这两棵树，同时将新得到的二叉树加入到9中。
   重复②、③，直到F中只含一棵树时为止。这棵树便是最优二叉树(哈夫曼树)。
   从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和。
   因此，C为最优二叉树，其带权路径长度为(12+6)*4+15*3+23*2+29=192。
转载请注明原文地址:https://kaotiyun.com/show/5IxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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