首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若一棵哈夫曼树共有13个顶点,则其叶子结点的个数为(24)。
若一棵哈夫曼树共有13个顶点,则其叶子结点的个数为(24)。
admin
2015-06-03
58
问题
若一棵哈夫曼树共有13个顶点,则其叶子结点的个数为(24)。
选项
A、5
B、6
C、7
D、8
答案
C
解析
哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法,根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下所述。
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w
1
,w
2
,…, w
n
,则哈夫曼树的构造规则如下。
(1)将w
1
,w
2
,…,w
n
看成是有n棵树的森林(每棵树仅有一个结点)。
(2)在森林中选出两个根结点的权值最小的树,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和。
(3)从森林中删除选取的两棵树,并将新树加入森林。
(4)重复第(2)和第(3)步,直到森林中只剩一棵树为止,该树即为所求的哈夫曼树。
从以上构造过程可知,哈夫曼树是严格的二叉树,没有度数为1的分支结点。设二叉树的0度结点(即叶子结点)个数为n
0
,2度结点个数为n
2
,则树的总结点数n=n
0
+n
2
。
又因为二叉树有性质:对任何一棵二叉树,如果其叶子结点数为n
0
,度为2的结点数为n
2
,则n
0
=n
2
+1。所以n=n
2
+1+n
2
。即13=n
2
+1+n
2
,n
2
=6,n
0
=7。
转载请注明原文地址:https://kaotiyun.com/show/G3RZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
ATM(异步传输模式)网络所采用的多路技术是(188),如果它的数据速率为155.5Mb/s,这样每秒大约可以传送(189)万个信元。ATM是为B-ISDN定义的传输和交换方式,可以适应各种不同特性的电信业务,CBR(Constant Bit Rate)模
在OSI七层协议模型中,TCP是(183)的协议。使用(184)次握手协议建立连接,当主动方发出SYN连接请求后,等待对方回答(185)。这种建立连接的方法可以防止(186)。TCP使用(187)进行流量控制。
在下列的各选项中,(19)是Linux中一种常用的引导工具;在Linux操作系统下安装网卡,如果操作系统没有内置的驱动程序,那么用户必须(20),才能完成驱动程序的安装;为一块设备名为eth0的网卡分配中地址和子网掩码的命令是:(21);如果不打算使用DN
OSI网络管理标准定义了网管的五大功能。其中,接收报警信息、启动报警程序、以各种形式发出警报的功能属于(327);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属于(328);对每一个被管理对象的每一个属性设置阈值、控制阈值检查和告警的
向端用户提供尽可能宽的网络接入是引起人们广泛关注的技术。(46)只能提供128kb/s的接入数据速率,(47)则是通过电话双绞线向端用户提供更高信息传输带宽的一种接入技术,而采用(48)和电缆调制解调器也可获得和后者同样数量级的接入带宽。第3代无线通信的(
多路复用技术能够提高传输系统的利用率。常用的多路复用技术有(16)。将一条物理信道分成若干个时间片,轮换地给多个信号使用,实现一条物理信道传输多个数字信号,这是(17)。将物理信道的总频带宽分割成若干个子信道,每个信道传输—路信号,这是(18)。在光纤中采
在网络中使用5类UTP作为传输介质,单段UTP的最长长度为(11)米。采用EIA568A布线标准时,可以达到的最高数据率是(12)Mb/s。STP与UTP的主要区别是(13)。一般而言,单模光纤与多模光纤的主要不同是(14),但为充分利用其容量,都可以使用
在OSI参考模型中,实现端到端的应答、分组排序和流量控制功能的协议层是()。
请采用说明中的词汇,给出数据确认处理所需的数据流在第1层图中的全部可选起点(第0层图和第1层图中均未给出)。打印分户账清单时,必须以下列哪一组数据作为关键字进行排序,才能满足需求?请从下面选项中选择。①储蓄所②账号⑧开户日
The grid computing is a new(66)technology connecting the distributed and(67)resources to the high-speed network and integrating
随机试题
对政府信息的内容要求是?()
元音发音时,()越大,舌位越低。
三年来,某自学考试科目的合格率分别为:0.50,0.30,0.20,设它们的权数分别为0.2,0.4,0.4,那么三年来该科目合格率的加权平均数为()
在ICD-10中,下列疾病应分类于“血液及造血器官疾病和某些涉及免疫机制的疾患”这一章的是
UCITS三号指令,自()起生效。
BT公司是一家内燃机生产企业。最近,公司质量部刘经理感到非常困惑。刘经理是一年前从技术人员升为质量部经理的,长期的基层工作使他认识到一线工人在工作中缺乏质量技术和工具的支持。因此,刘经理一上任,就针对一线工人展开了质量技术和工具的培训,聘请高水平的讲师为工
仓储活动的基本功能包括()。
公安机关在行使管制权时,人民警察可以采取必要手段强行驱散,并对拒不服从的人员()。
下列关于事务处理的叙述中,哪一条是不正确的?()A)事务的ACID特性指的是原子性、一致性、唯一性和持久性B)成功完成执行的事务称为已提交事务C)已提交事务使数据库进入一个新的一致状态D)已中止事务对数据库所做的任何改变必须撤销
Besidesclimatechange,developingcountrieslikeChinaneedtodealwithenergy【C1】______andenvironmentalissues:thedevelopm
最新回复
(
0
)