2. 计算机
  3. 对于给定的一组权值{2，3，4，1 1)，用其构造Huffman树，则其WPL为(52)，根节点的权值为(53)。

对于给定的一组权值{2，3，4，1 1)，用其构造Huffman树，则其WPL为(52)，根节点的权值为(53)。

admin2014-11-11  26
问题 对于给定的一组权值{2，3，4，1 1)，用其构造Huffman树，则其WPL为(52)，根节点的权值为(53)。
选项 A、53
B、40
C、34
D、20
答案C、D
解析 Huffman树又称为最优树，是一类带权路径长度最短的树。路径是指从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径，路径上的分支数目就称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。树的路径长度为树中所有节点的带权路径长度之和，记为，其中n为带权叶子节点数目，WR为叶子节点的权值，lk为叶子节点到根的路径长度。Huffman树是指权值为w1、w2、…、wn的n个叶子节点的二叉树中带权路径长度最小的二叉树。构造Huffman树的算法如下：(1)给定n个节点的集合，每个节点都带权值。(2)选两个权值最小的节点构造一棵新的二叉树，新的二叉树的根节点的权值就是两个子节点权值之和。(3)从n个节点中删除刚才使用的两个节点，同时将新产生的二叉树的根节点放在节点集合中。(4)重复(b)(c)，直到只有一棵树为止。本题构造出的Huffman树如下：根节点的权值为20，对应的WPL为：11×1+4×2+(2+3)×3=34。
转载请注明原文地址:https://jikaoti.com/ti/VKf7FFFM
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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