设有5个结点a、b、C、d、e，这些结点的权值分别为5、7、8、10、31，利用这些数据构造一棵树，要求这棵树的带权路径长度最小。

admin2013-12-15 81

问题设有5个结点a、b、C、d、e，这些结点的权值分别为5、7、8、10、31，利用这些数据构造一棵树，要求这棵树的带权路径长度最小。

选项

答案带权路径长度最小的树是赫夫曼树。构造赫夫曼树的步骤如下： (1)根据给定的n个权值{w1，w2，…，wn}构成n棵二叉树的集合F={T1，T2，…，Tn)，最初每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树为空。 (2)在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 (3)在F中删除这两棵树，同时将新得到的二叉树加入F中。 (4)重复(2)和(3)，直到F只含一棵树为止。这棵树便是赫夫曼树。本题中构造的赫夫曼树如下。 [*]

解析

转载请注明原文地址:https://kaotiyun.com/show/u0al777K

本试题收录于：计算机专业知识题库事业单位考试分类

计算机专业知识

事业单位考试

相关试题推荐

随机试题

最新回复(0)

设有5个结点a、b、C、d、e，这些结点的权值分别为5、7、8、10、31，利用这些数据构造一棵树，要求这棵树的带权路径长度最小。

计算机专业知识

事业单位考试

教师通过记录课外活动中学生的攻击行为来研究攻击和性别的关系，这种研究方法是()。

讲述是教师主要的教学手段，一般可以分()三个阶段进行。

消费者和经营者发生消费者权益争议的，可以通过以下途径解决()。

“石老人”位于青岛崂山脚下临海断崖南侧，是一座高达17米的花岗岩石柱。“石老人”地貌形成的顺序是()。

小凡知道杯子可以用来喝水，却想不到杯子也可以用来压纸张。这种现象属于功能固着。()

儿童在熟悉了“哈密瓜”“西瓜”“菠萝”等概念之后，再学习“水果”这一概念，按照奥苏伯尔的学习分类理论，这种学习属于()。

在双绞线组网方式中，()是以太网的中心连接设备。

A类地址的有效范围是()。

使用UTP双绞线和RJ-45接头连接的以太网络结构属于()。

#include#includedstdlib．h>typedefstructstudent{inthum；charname[20]；charsex；intage；}LIST；LIST*creat

下述对骨质疏松症的描述错误的是

糖尿病或慢性肾病合并高血压患者，血压控制目标值是()。

在平行结转分步法下，在完工产品与在产品之间分配费用，是指在各步骤完工产品与在产品之间分配费用。()

语言技能包括听、说、读、写四个方面的技能以及这四种技能的综合运用能力。那么，()是理解的技能，()是表达的技能。

Thenewofficeblockoccupies______.

Culturereferstothesocialheritageofapeople--thelearnedpatternforthinking,feelingandactingthatcharacterizeapopu

Forthispart,youareallowed30minutestowriteashortessaytoexplainWhyarePeoplenotWittingtoHelp.Youressayshoul