首页
登录
从业资格
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带
练习题库
2022-08-02
67
问题
由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(请作答此空),其带权路径长度为( )。
选项
答案
A
解析
本题考察最优二叉树(哈夫曼树)的构造和带权路径长度的计算。构造最优二叉树的哈夫曼算法如下:(1)、根据给定的n个权值{w1, w2, …,wn}, 构成n棵二叉树的集合F= {T1, T2, …Tn},其中,每棵树Ti中只有一个带权为wi的根结点,其左、右子树均空。(2)、在F中选取两棵权值最小的树作为左、右子树构造一棵新的二叉树,新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。(3)、从F中删除这两棵树,同时将新得到的二叉树加入到F中。(4)、重复(2)、(3)步,直到F中只含一棵树时为止,这棵树便是最优二叉树(哈夫曼树)。所以由权值为 9、2、1、6、4 的五个叶子结点构造的哈夫曼树为(红色圈内填写的数字为构造的新节点,在选项中没有体现出来,用空白圆圈进行了替代):
结点的带权路径长度为从该结点到树根之间的路径长度与该结点权值的乘积,而树的带权路径长度为树中所有叶子结点的带权路径长度之和。所以构造的哈夫曼树的带权路径长度为9*1+6*2+4*3+(1+2)*4=9+12+12+12=45。
转载请注明原文地址:https://tihaiku.com/congyezige/2416838.html
本试题收录于:
中级 软件评测师题库软件水平考试初中高级分类
中级 软件评测师
软件水平考试初中高级
相关试题推荐
根据权值集合{0.30,0.25,0.25,0.12,0.08}构造的哈夫曼树中
对下图所示的二叉树进行中序遍历(左子树,根结点,右子树)的结果是( )。 A
在面向对象的系统中,对象是运行时的基本实体,对象之间通过传递(请作答此空)进行通
如图所示的UML类图中,Shop和Magazine之间为(请作答此空)关系,Ma
DHCP协议的功能是();FTP使用的传输层协议为(请作答此空)。A.TC
DHCP协议的功能是(请作答此空);FTP使用的传输层协议为()。A.WI
从下列名词中区分类和对象。其中,(请作答此空)全部是类,()全部是对象。A.课
从下列名词中区分类和对象。其中,()全部是类,(请作答此空)全部是对象。A.课
在一系统中,不同类对象之间的通信的一种构造称为(请作答此空),一个对象具有多种形
通过(请作答此空)关系运算,可以从表1和表2获得表3;表3的主键为()。
随机试题
A.唇形科,含间隙腺毛 B.茎方形,叶对生,叶片3~5羽状裂,穗状轮伞花序顶生
阳性显像
年度状态评价是综合()等各种技术手段,依据电网设备状态评价导则每年集中组织开展的
古代陆上丝绸之路在唐朝达到空前繁荣,这在唐诗中就有大量记载,下列诗句中,描写物质
各种运输方式内外部的各个方面的构成和联系,就是( )。 A.运输系统
(2017年真题)下列不会引起流动资产增加的是()。A.季节性销售增长
对同一问题所提的意见越新奇独特,则其思维的()越高。 A.流畅性B.变通性
张某是某公司的生产总监,他平时总是尽力帮助员工。他的一个下属由于家人生病经常缺勤
(2021年第1批真题)下列设计变更的情形中,属于较大设计变更的有()。A.连续
建设工程生产安全事故应急预案中,针对深基坑开挖可能发生的事故,相关危险源和应急保
最新回复
(
0
)