首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面关于哈夫曼树的叙述中,正确的是(58)。
下面关于哈夫曼树的叙述中,正确的是(58)。
admin
2021-01-13
22
问题
下面关于哈夫曼树的叙述中,正确的是(58)。
选项
A、哈夫曼树一定是完全二叉树
B、哈夫曼树一定是平衡二叉树
C、哈夫曼树中权值最小的两个结点互为兄弟结点
D、哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点
答案
C
解析
哈夫曼树又称最优二叉树或最优搜索树,是一种带权路径长度最短的二叉树。具有以下特征:
(1)当叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。即哈夫曼树不一定是完全二叉树。
(2)在最优二叉树中,权值越大的叶子离根越近。
(3)最优二叉树的形态不唯一,但WPL最小。
哈夫曼树的构造:
(1)根据给定的n个权值{w1,w2,…,wn}构造n棵二叉树的集合F={Tl,T2,…,Tn},其中Ti中只有一个权值为wi的根结点,左右子树为空;
(2)在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树,且置新的二叉树的根结点的权值为左、右予树上根结点的权值之和。
(3)将新的二叉树加入到F中,删除原两棵根结点权值最小的树;
(4)重复(2)和(3)直到F中只含一棵树为止,这棵树就是哈夫曼树。
平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。而哈夫曼树并未要求左右两个子树的高度差的绝对值不超过1,根据其构造可知,是从上往下顺序排下来的,且左孩子结点大于父孩子结点。
转载请注明原文地址:https://kaotiyun.com/show/zJCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和E-R图,回答问题1至问题3,将解答填入对应栏内。[说明]设有下列关于学生成绩管理系统的E-R图(见图2-1)。图中矩形表示实体,圆表示属性,双圆表示关键字属性,菱形表示实体间的联系。假定已通过下列SQL语言建立了基本表:
阅读以下说明和Jrdva代码,将应填入(n)处的字句写在对应栏内。[说明]在销售系统中常常需要打印销售票据,有时需要在一般的票据基础上打印脚注。这样就需要动态地添加一些额外的职责。如下展示了Decorator(修饰)模式。SalesOr
阅读下列函数说明和C++代码,将应填入(n)处的字句写在对应栏内。[说明]在销售系统中常常需要打印销售票据,有时需要在一般的票据基础上打印脚注。这样就需要动态地添加一些额外的职责。如下展示了Decorator(修饰)模式。SalesOr
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。[说明]HufTman树又称最优二叉树,是一类带权路径长度最短的树,在编码中应用比较广泛。构造最优二叉树的Huffman算法如下:①根据给定的n各权值{W
阅读以下说明和Java代码,回答问题[说明]对多个元素的聚合进行遍历访问时,需要依次推移元素,例如对数组通过递增下标的方式,数组下标功能抽象化、一般化的结果就称为迭代器(Iterator)。模式以下程序模拟将书籍(Book)放到书架(BookSh
阅读下列说明和C++代码,将应填入(n)处的字句写在对应栏内。[说明]某饭店在不同的时段提供多种不同的餐饮,其菜单的结构图如图5-1所示。现在采用组合(Composition)模式来构造该饭店的菜单,使得饭店可以方便地在其中增加新的
阅读下列说明和图。[说明]Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域的道路交通网的信息。道路交通网由若干个路段(RoadSegment)构成,每个路段由两个地理坐标点(Node)标
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】公司IT部门决定开发一个计算机管理系统以记录期刊的传阅情况。期刊在公司内部传阅,员工可以要求加入传阅队列。图书室登记公司收到的期刊,交给名单中的第一名员工。员工应在三个工作日内完
某一确定性有限自动机(DFA)的状态转换图如下图所示,令d=0|1|2|…|19,则以下字符串中,不能被该DFA接受的是(28),与该DFA等价的正规式是(29)。(其中,ε表示空字符)①3857 ②1.2E+5 ③-123. ④.576
在下图所示的树型文件系统中,方框表示目录,圆圈表示文件,“/”表示路径中的分隔符,“/”在路径之首时表示根目录。图中,(10)。假设当前目录是D1,进程A以如下两种方式打开文件f1。①fd1=open("(11)/fl",
随机试题
A、Itisanobjectiveevaluationofaperson’scharacter.B、Itisamentalprocessinfluencedbymanyfactors.C、Itcontributest
下列哪项不是辨别中风闭证与脱证的依据
葡萄酒斑状血管瘤属于
安乃近片剂
李先生拟在5年后用200000元购买一辆车,银行年复利率为12%,李先生现在应存入银行()元。[2014年6月证券真题]
确认培训需求仅仅是企业内部培训部门的职责。()
①食物是人类生存之本,但饮食的意义却并不局限于保证人的生理生存②简单来说,就是以食物为载体的各种教育③因此,食育可以看作德育、智育和体育的基础④孩子通过各种各样的饮食体验,不仅可以学习与食物相关的知识,而且可以提高选择和搭配食物的能力⑤食育,是日本
虽然让每个人都感到正义永远是社会追求的目标,但对于充满内部张力的转型社会,要实现这个目标仍然有漫长的路要走。在相当多的时刻,我们除了渴求正义,也必须求助于忍耐,更不能以不择手段、祸及无辜的方式追求正义。因为这样的做法,实际上是以正义的名义把社会变成了大鱼吃
Animalsthathavetastedunpalatableplantstendto____themafterwardonthebasisoftheirmostconspicuousfeatures,suchas
______,thefirstnovelbyJackLondon,waspublishedin1902.
最新回复
(
0
)