首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
admin
2013-02-02
57
问题
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
选项
A、55
B、68
C、59
D、28
答案
C
解析
本题考查带权哈夫曼树的构造及求带权路径长度。树的路径长度是从树根到树中每一结点的路径长度之和,结点到树根之间的路径长度与该结点上权的乘积,称为结点的带权路径长度。树中所有叶结点的带权路径长度之和,称为树的带权路径长度。在权为w1,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。假设有n个权值,则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,…, wn,则哈夫曼树的构造规则为:(1)将w1,w2,…,wn看成是有n棵树的森林(每棵树仅有一个结点);(2)在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;(3)从森林中删除选取的两棵树,并将新树加入森林。重复第(2)步和第(3)步,直到森林中只剩一棵树为止,该树即为所求的哈夫曼树。根据哈夫曼树的构造规则,不难得到题目中给出叶子结点对应的哈夫曼树,得到哈夫曼树后我们再计算带权路径长度=3×(3+4)+2×(5+6+8)=59。
转载请注明原文地址:https://kaotiyun.com/show/nGVZ777K
本试题收录于:
程序员上午基础知识考试题库软考初级分类
0
程序员上午基础知识考试
软考初级
相关试题推荐
下面的协议中,(49)不属于TCP/IP协议层次结构中的应用层协议。
根据红皮书的计算机安全系统评价准则,下面属于C2级安全准则的操作系统是(24)。 Ⅰ.DOS Ⅱ.WINDOWS 95 Ⅲ.WINDOWS 98 Ⅳ.Unix Ⅴ.Windows NT Ⅵ.Novell 3.
下面有关FFP的描述正确的是(20)。
IEEE802.5令牌环网中,时延是由(36)决定的。要保证环网的正常运行,整个环网的时延必须大于(37)。设有一个令牌环网,长度为400m,环上有28个站,数据速率为4Mbit/s,信号传播速度为200m/μs,每个站点引入1位时延,则环网的最大和最小时
FTP命令集因系统、版本而异,常用的命令如下。(54)有ASCII和二进制模式。(55)改变计算机的当前目录。(56)open建立同远程计算机的连接,close关闭连接。(57)put传送一个文件到远程计算机,put传送多个文件到远程计算机。(58)get
宽带广域网络可采用(54)技术实现,其骨干网应选用(55)作为主要通信介质,节点之间的连接不宜采用(56)结构。
阅读以下说明、Java代码和HTML文档,将应填入(n)处的字句写在答题纸的对应栏内。【说明】当用户启动html浏览器并首次打开下面的HTML文档时,JavaApplet小程序在显示面板上显示字符串“Welcome!”;当html页面被其他窗口
阅读以下说明和C函数,将应填入(n)处的字句写在答题纸的对应栏内。【说明】某班级有N名学生,他们可根据自己的情况选修名称和数量不尽相同的课程。设N等于6,学生信息、所选课程及成绩用链表结构存储,如图2-5所示。程序中相应的类型定义如下:
阅读以下说明和C语言函数,将应填入(n)处的字句写在对应栏内。【说明】下面的程序构造一棵以二叉链表为存储结构的二叉树算法。【函数】BTCHINALR*createbt(BTCHINALR*bt){
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。[函数2.1说明]函数strcpy的功能是将字符串str2的内容复制到字符申str1。[函数2.1](1)strcpy(char*slr1,constchar*st
随机试题
采用拼组机床加工大型零件,具有的主要特点有()。
我国安全的生产方针是:"安全第一、预防为主"。
文字起源于()
下列检查中,哪一项对鉴别单纯性与绞窄性肠梗阻最有帮助()
不属于神经反射检查的内容是()
根据《中华人民共和国水土保持法》,修建铁路、公路和水工程时必须采取的防止水土流失措施有()。
某保险公司计划推出一项医疗保险,对象是60岁以上经体检无重大疾病的老年人。投保者在有生之年如果患心血管疾病或癌症,则其医疗费用的90%将由保险公司赔付。为了吸引投保者,保险金又不能定得太高。有人估计保险金将不足以支付赔付金,因而会是个赔本生意。尽管如此,保
Ifyousmoke,nooneneedstotellyouhowbaditis.Sowhyhaven’tyouquit?Whyhasn’teveryone?Becausesmokingfeelsgo
有以下程序main(){intx=1,y=0,a=0,b=0;switch(x){case1:switch(y){case0:a++:break;case1:b++;break;}case2:a++;b++;break;case3:a++;
Franklyspeaking,I’dratheryou(make)______nocommentontheissueattheconferenceyesterday.
最新回复
(
0
)