首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
关于哈夫曼树、最优二叉树、哈夫曼算法,有以下说法: ①最优二叉树的形态不唯一,但是其WPL值是唯一确定的。 ②哈夫曼树一定是最优二叉树,但最优二叉树不一定由哈夫曼算法来构造。 则______。
关于哈夫曼树、最优二叉树、哈夫曼算法,有以下说法: ①最优二叉树的形态不唯一,但是其WPL值是唯一确定的。 ②哈夫曼树一定是最优二叉树,但最优二叉树不一定由哈夫曼算法来构造。 则______。
admin
2009-09-04
17
问题
关于哈夫曼树、最优二叉树、哈夫曼算法,有以下说法:
①最优二叉树的形态不唯一,但是其WPL值是唯一确定的。
②哈夫曼树一定是最优二叉树,但最优二叉树不一定由哈夫曼算法来构造。
则______。
选项
A、①正确②错误
B、①错误②正确
C、都对
D、都错
答案
C
解析
假设有n个权值{w1,w2,…,wn),构造一棵有n个叶子结点的二叉树,则称带权路径长度WPL最小的二叉树为最优二叉树,亦称哈夫曼树。值得注意的是,最优二叉树的形态不唯一,但是其WPL值是唯一确定的。这好比一个班里,张三、李四和王五体型各异但身高一样,而且是最高的,显然最高的身高值只有一个。用哈夫曼算法构造出来的哈夫曼树一定是最优二叉树,定性地说,在哈夫曼算法中,每次构造新树时都是将权值最小的树尽量放在离根最远的地方,而将权值大的尽量放在离根近的地方,从而使得WPL最小。因此,哈夫曼树一定是最优二叉树。值得特别注意的是,哈夫曼算法可以确保构造出来的树是最优二叉树,但是最优二叉树并不一定非得用哈夫曼算法来构造。例如,给定权值{2,3,4,7,8,9},可以构造出两棵最优二叉树T1、T2,如图3-72所示。
显然它们的WPL都是80,所以T1、T2都是是最优二叉树。T1是用哈夫曼算法构造出来的,但T2却不是用哈夫曼算法构造出来的,而是用上文中提及的构造哈夫曼树最容易犯的错误想法构造出来的一棵树。从上面的例子可以看出,哈夫曼算法只是构造最优二叉树的“充分条件”,而不是“必要条件”。至于为什么将哈夫曼树称为最优二叉树,原因可能是由于哈夫曼最早给出了带有一般规律的构造最优二叉树的哈夫曼算法,为了纪念他,就用哈夫曼树来称呼所有的最优二叉树。
转载请注明原文地址:https://kaotiyun.com/show/duxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
用户李四给数据库服务器发命令,要求将文件“张三.dbf”删除。数据库服务器上的认证机制需要确定的主要问题是(33)。
在互连的网络设备中,交换机的工作与网桥相比,区别在于(27),网桥是根据(28)知道是应该转发还是应该过滤数据包。交换机与Hub相比,优点是(29),网桥中为了防止产生循环路径,需要运行(30);算法。具有自学习功能的网桥是(31)。
自标准实施之日起,至标准重申重新确认、修改或废止的时间,称为标准的有效期(标龄),我国的国家标准有效期一般为(48)年,国家标准是由政府或国家级的机构制定或批准的,适用于全国范围的标准,是一个国家标准体系的主体和基础,国内各级标准必须服从且不得与之相抵触。
A向B发送消息P,并使用公钥体制进行数字签名。设E表示公钥,D表示私钥,则B要保留的证据是(5)。基于数论原理的RSA算法的安全性建立在(6)的基础上。Kerberos是MIT为校园网设计的身份认证系统,该系统利用智能卡产生(7)密钥,可以防止窃听者捕获认
在Linux系统的路由配置中,若设置静态路由,则需(17)命令。在使用该命令时为了防止出现错误,可以将网络名字代替网络号,而网络名字可以在文件(18)中定义。为了将手工配置的命令存储下来,在系统启动时自动执行,可以通过(19)来实现。若运行动态路由,则(2
计算机内存中是按字节编址的,现在有一地址范围是从A4000H到CBFFFH,那么此地址范围共占据(31)个字节。若用存储容量为16K×8bit的存储芯片构成该内存,至少需要(32)片。
计算机内存中是按字节编址的,现在有一地址范围是从A4000H到CBFFFH,那么此地址范围共占据(31)个字节。若用存储容量为16K×8bit的存储芯片构成该内存,至少需要(32)片。
ISDN的承载业务类型有那些?简述ISDN的协议模型。
简述NetBIOS与TCP/IP关系。NetBIOS包括哪些服务功能?
OSI网络管理标准定义了网管的五大功能。比如对每一个被管理对象的每一个属性设置阈值、控制域值检查和告警的功能属于(54);接收报警信息、启动报警程序、以各种形式发出警报的功能属于(55);接收告警事件、分析相关信息、及时发现正在进行的攻击和可疑迹象的功能属
随机试题
单纯恐怖障碍平均起病年龄为()
世界贸易组织的协商一致决策程序是指()
属于人员招募过程的是【】
简述受胁迫而为的民事行为的构成要件。
男性,45岁,肝硬化腹水患者,拟行肠内营养支持,宜选择的肠内营养制剂是
下列关于城市维护建设税及教育费附加的说法中正确的有()。
国内某高校张教授2016年取得部分收入项目如下:(1)5月份出版了一本书稿,获得稿酬15000元,后因出版社添加印数,获得追加稿酬5000元。(2)9月份,教师节期间获得全国教学名师奖,获得教育部颁发的资金50000元。
设有两个数列{an}{bn}若
LearnEnglishwithus!TeachingEnglishforover13years.LearningtospeakEnglishatourlanguageschoolinMaltaissimp
A、Tourism.B、Naturalheritage.C、Illegalwildlifeproducts.D、Slaughteroficonicanimals.A演讲中男士提到,他们这些家庭只能眼睁睁地看着周围的野生动植物消失而失去了
最新回复
(
0
)