首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
admin
2019-05-10
42
问题
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
选项
A、23
B、37
C、44
D、46
答案
C
解析
由权值为9、2、5、7的四个叶子构造的哈夫曼树可如下图所示。
该树的带权路径长度=9×1+7×2+2×3+5×3=44。
[归纳总结]对哈夫曼树特征的总结:
(1)用n个权值(对应n个叶子结点)构造哈夫曼树,共需要n-1次合并,即哈夫曼树中非叶子结点的总数为n-1,总结点个数为2n-1。
(2)哈夫曼树中没有度为1的结点,因为非叶子结点都是通过两个结点合并而来。但是,没有度为1的二叉树并不一定是哈夫曼树。
(3)用n个权值(对应n个叶子结点)构造的哈夫曼树,形态并不是唯一的。
建立哈夫曼树的过程中有以下三种常见的错误:
(1)在合并中不是选取根结点权值最小的两棵二叉树(包括已合并的和未合并的),而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并。
(2)每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。
(3)有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树,但那只是巧合,没有规律性,而没有规律性的解法不利于用计算机进行处理。
转载请注明原文地址:https://www.kaotiyun.com/show/L2Ci777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
阅读史料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合
《关于建国以来党的若干历史问题的决议》指出:“我们现在赖以进行现代化建设的物质技术基础,很大一部分是这个期间建设起来的,全国经济文化建设等方面的骨干力量和他们的工作经验,大部分也是在这个期间培养和积累起来的,这是这个期间党的T作的主导方面。”“这个期间”是
欧洲历史上第一部系统完备的法典是()。
下列关于提督学政的说法不正确的是()。
关于井田,最具权威性的最早的叙述者是()
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT、服务器上,并且通过NAT服务器连接到Internet上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
某系统有R1、R2和R3共3种资源,在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示,此时系统的可用资源向量为(2,1,2)。试问:如果此时P1和P2均发出资源请求向量Request(1,0,1),为了保证系统的安全性,应
随机试题
证券之星的主页上设置的主要板块有
符合诊断要求的X线照片密度是
环境影响评价工程师可主持进行的工作包括()。
建设单位领取了施工许可证,但因故不能按期开工的,应当在期满前向发证机关申请延期,并说明理由,延期以2次为限,每次不超过( )个月。
下列属于会计的基本等式的是( )。
有关工业厂房可靠性鉴定标准的相关表达不正确的是()。
滑冰是人们利用冰刀在冰上滑行的冬季运动项目,起源于十世圮的_______。
下列合成词全属于动宾型的一组是()。
当观察者与周围环境中的物体相对运动时,近处物体看上去移动得快,方向相反,远处物体移动较慢,方向相同,这就是()。
下列不属于计算机特点的是
最新回复
(
0
)