首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
admin
2019-08-10
10
问题
由权值为9、2、5、7的四个叶子构造一棵哈夫曼树,该树的带权路径长度为( )。
选项
A、23
B、37
C、44
D、46
答案
C
解析
由权值为9、2、5、7的四个叶子构造的哈夫曼树可如图2—5所示。
(1)该树的带权路径长度=9×1+7×2+2×3+5×3=44。中非叶子结点的总数为n-1,总结点个数为2n-1。
(2)哈夫曼树中没有度为1的结点,因为非叶予结点都是通过两个结点合并而来。但是,没有度为1的二叉树并不一定是哈夫曼树。
(3)用n个权值(对应n个叶子结点)构造的哈夫曼树,形态并不是唯一的。
建立哈夫曼树的过程中有以下三种常见的错误:
(1)在合并中不是选取根结点权值最小的两棵二叉树(包括已合并的和未合并的),而是选取未合并的根结点权值最小的一棵二叉树与已经合并的二叉树合并。
(2)每次都是在未合并的二叉树中选取根结点的权值最小的两棵子树。
(3)有时没有严格按照哈夫曼算法也构造出带权路径长度与哈夫曼树相同的二叉树,但那只是巧合,没有规律性,而没有规律性的解法不利于用计算机进行处理。
转载请注明原文地址:https://kaotiyun.com/show/syCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
完整地表述电磁场理论的物理学家是()。
商朝号称青铜时代,下列叙述不符合当时的历史情况的是()
中国第一个资产阶级革命团体兴中会建立的时间是()。
中世纪战争史上有过两次君士坦丁堡陷落,分别简述其发生的时间、征战的双方、导致的历史变动。
北宋在统一南方割据势力的过程中特设(),把征南所得的财富统一存放,以作日后恢复幽燕之费。
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
某中央处理器的数据通路如图所示。MDR为内存数据寄存器,PC为程序计数器,IR为指令寄存器。所有的单线箭头为控制微命令。(1)请说明图中部件X的名称和功能、寄存器Y的名称和功能。(2)请解释:为什么要设置T暂存器?(3)假定指
随机试题
函数fun的功能是:将一副扑克牌编号为1,2,3,…,53,54,以某种特定的方式洗牌,这种方式是将这副牌分成两半,然后将它们交叉,并始终保持编号为1的牌在最上方,如第一次这样洗牌后的结果为:1,28,2,29,…,53,27,54。两次洗牌后的结果为:1
左图为给定的多面体,将其从任一面剖开,哪项不可能是该多面体的截面?
A.横小管B.终末池C.肌小节D.肌动蛋白E.肌钙蛋白能够释放再聚集Ca2+的是
若级数收敛,则下列级数中不收敛的是()。
下列关于巻材铺贴的叙述,正确的是()。
在产品销售业务的核算中,期末结转后,下列账户应无余额的有()。
明确提出税制建立必须遵循平等、确实、便利、最少征收费用四原则的人是()。
对固定资产发生的后续支出资本化的价值加入固定资产成本。()
19世纪印象派画家_______曾说:“我作画犹如鸟儿在唱歌。”
我国现阶段在分配上采取以按劳分配为主体,其他分配形式为补充的分配制度。()
最新回复
(
0
)