关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法： ①最优二叉树的形态不唯一，但是其WPL值是唯一确定的。 ②哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。则______。

admin2009-09-04 48

问题关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法：
①最优二叉树的形态不唯一，但是其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)

关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法： ①最优二叉树的形态不唯一，但是其WPL值是唯一确定的。 ②哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。则______。

软件设计师上午基础知识考试

软考中级

有一脉冲信号周期为20ms，信号有效值状态个数为8。用四进制代码表示上述信号，其数据传输速率是(23)。

两个码子之间的海明距为(22)。码是由码子组成的集合，一个码的海明距离指的是(23)。若一个码要求检测3位错，则该码的海明距离应为，(24)。

SNMPc是一个通用的多用户分布式网络管理平台，采用(21)轮询机制，具有高度的可伸缩性。假设有一个局域网，管理站每15分钟轮询被管理设备一次，一次查询访问需要的时间是200ms，则管理站最多可以支持(22)台网络设备。

用户A与用户B通过卫星链路通信时，传播延迟为540ms，假设数据速率是64Kbit/s，帧长4000bit，若采用停等控制协议通信，则最大链路利用率为(22)；若采用后退N帧ARQ协议通信，发送窗口为8，则最大链路利用率可以达到(23)。

两个公司希望通过Internet传输大量敏感数据，从信息源到目的地之间的传输数据以密文形式出现，而且不希望由于在传输结点使用特殊的安全单元而增加开支，最合适的加密方式是()，使用会话密钥算法效率最高的是()。

Junglecountryisnotfriendlytoman,butitispossibletosurvivethere.Youmusthavetheright【21】andyoumustknowafewi

患者，男，16岁。左下后牙龋洞，无明显自发痛，食物嵌入时痛。检查：左下6面龋坏，软化牙本质较多，叩(－)，冷试敏感，电活力正常，去除无基釉后去腐敏感，不能全部去净。该牙的初诊治疗是

治疗贫血，口服铁剂的最佳时间是

下列属于衡量一国通货膨胀程度的重要指标的是()。

某商品流通企业2010年度有关财务报表主要资料整理如下表所示：该公司2010年的净资产收益率为()。

抽象艺术的创始人是()

小数法则是一种心理偏差，是指人们将小样本中某事件的概率分布看成是总体分布，抓住问题的某个特征直接推断结果，而不考虑这种特征出现的真实概率及与特征有关的其他原因。根据上述定义，下列属于小数法则的是：

归纳推理属于()。

A、SheisagainstteachingEnglish.B、Englishshouldn’tbethegloballanguage.C、TranslationshouldreplaceteachingEnglish.D、

关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法： ①最优二叉树的形态不唯一，但是其WPL值是唯一确定的。 ②哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。 则______。

软件设计师上午基础知识考试

软考中级

有一脉冲信号周期为20ms，信号有效值状态个数为8。用四进制代码表示上述信号，其数据传输速率是(23)。

两个码子之间的海明距为(22)。码是由码子组成的集合，一个码的海明距离指的是(23)。若一个码要求检测3位错，则该码的海明距离应为，(24)。

SNMPc是一个通用的多用户分布式网络管理平台，采用(21)轮询机制，具有高度的可伸缩性。假设有一个局域网，管理站每15分钟轮询被管理设备一次，一次查询访问需要的时间是200ms，则管理站最多可以支持(22)台网络设备。

用户A与用户B通过卫星链路通信时，传播延迟为540ms，假设数据速率是64Kbit/s，帧长4000bit，若采用停等控制协议通信，则最大链路利用率为(22)；若采用后退N帧ARQ协议通信，发送窗口为8，则最大链路利用率可以达到(23)。

两个公司希望通过Internet传输大量敏感数据，从信息源到目的地之间的传输数据以密文形式出现，而且不希望由于在传输结点使用特殊的安全单元而增加开支，最合适的加密方式是()，使用会话密钥算法效率最高的是()。

Junglecountryisnotfriendlytoman,butitispossibletosurvivethere.Youmusthavetheright【21】andyoumustknowafewi

患者，男，16岁。左下后牙龋洞，无明显自发痛，食物嵌入时痛。检查：左下6面龋坏，软化牙本质较多，叩(－)，冷试敏感，电活力正常，去除无基釉后去腐敏感，不能全部去净。该牙的初诊治疗是

治疗贫血，口服铁剂的最佳时间是

下列属于衡量一国通货膨胀程度的重要指标的是()。

某商品流通企业2010年度有关财务报表主要资料整理如下表所示：该公司2010年的净资产收益率为()。

抽象艺术的创始人是()

小数法则是一种心理偏差，是指人们将小样本中某事件的概率分布看成是总体分布，抓住问题的某个特征直接推断结果，而不考虑这种特征出现的真实概率及与特征有关的其他原因。根据上述定义，下列属于小数法则的是：

归纳推理属于()。

A、SheisagainstteachingEnglish.B、Englishshouldn’tbethegloballanguage.C、TranslationshouldreplaceteachingEnglish.D、

关于哈夫曼树、最优二叉树、哈夫曼算法，有以下说法： ①最优二叉树的形态不唯一，但是其WPL值是唯一确定的。 ②哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。则______。