2. 计算机
  3. 带权为9，2，4，6的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为______。

带权为9，2，4，6的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为______。

admin2010-12-16  17
问题 带权为9，2，4，6的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为______。
选项 A、21
B、41
C、36
D、39
答案D
解析 本题考查哈夫曼树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的树。路径是从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的长度与该结点权的乘积。哈夫曼是指含有n个权值分别为w1，w2，…，wn的n个叶子结点的二叉树中带权路径长度最小的那棵树。所以应该将权重最大的叶子结点距离根结点最近，权重次小的距离根结点次远，依次类推。所以WPL=9+6*2+(2+4)*3=39。
转载请注明原文地址:https://www.kaotiyun.com/show/QzVZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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