首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
若以{4,5,6,3,8}作为叶子结点的权值构造哈夫曼树,则带权路径长度是(33)。
admin
2013-02-02
47
问题
若以{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
程序员上午基础知识考试
软考初级
相关试题推荐
在文件系统中,用户数据的访问通常以(37)为单位。
OSI参考模型可以分为7层。数据的压缩、解压缩、加密和解密工作都是(52)负责,电子邮件和网络管理程序工作在(53)。
FTP命令集因系统、版本而异,常用的命令如下。(54)有ASCII和二进制模式。(55)改变计算机的当前目录。(56)open建立同远程计算机的连接,close关闭连接。(57)put传送一个文件到远程计算机,put传送多个文件到远程计算机。(58)get
通常计算机的存储器是一个由Cache、主存和辅存构成的3级存储系统。辅助存储器一般可由磁盘、磁带和光盘等存储设备组成。Cache和主存一般是一种(5)存储器。在各种辅存中,除了(6)外,大多是便于脱卸和携带的。Cache存储器一般采用(7)半导体芯片,主存
宽带广域网络可采用(54)技术实现,其骨干网应选用(55)作为主要通信介质,节点之间的连接不宜采用(56)结构。
当透明桥转发一帧时,需在路径选择表中查找该帧的目的地址。如果查找不到,透明桥将(59)。
按照ISO定义的网管框架,网络管理包括(48)大功能。网管协议的两大体系结构标准中受到厂商广泛支持的是(49),(49)的模型包括(50)大部分,其中的信息在(51)中存放,管理代理是运行在(52)上面的一个软件。
在层次网络体系结构中,第N层协议利用(28)提供的服务向(29)提供服务,称(29)是N服务的(30),(30)是利用(31)通过(32)调用N层协议的服务的。
计算机中存放当前指令地址的寄存器称为(7),在顺序执行程序时,若指令长度为16位,存储器按字节编址,每执行一条指令该寄存器自动加(8)。
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。[说明]链式存储的队列称为链队。根据队列的FIFO原则,为了操作上的方便,可以使用带头指针front和尾指针rear的单链表来实现链队。若链队元素的数据类型为datatype,则链队结
随机试题
蛛网膜下腔出血最常见的原因是
某软件公司规模不断发展壮大,员工人数已从原来的20多人增加到现在的400多人,但管理层却发现公司的工作效率明显地下降了,相同类型的项目,过去5个人1个月可以完成,而现在10个人1个月都完成不了。由于绩效降低,员工人心涣散。[2005年真题]如果要改变这
广州圣心大教堂,始建于清同治二年(1863年),由法国普行善会建造,属法国哥特式建筑,高()米,是国内最大的哥特式教堂之一。
试分析达.芬奇的作品《蒙娜丽莎》。
A.RPI卡环B.回力卡环C.联合卡环D.对半卡环E.杆形卡环具有应力中断作用()。
Thenewprisonisdesignedparticularlyfor______.
WhatdoesthenewsitemsayaboutChristineLagarde?
PASSAGETHREEAccordingtothepassage,whatwillforgivenessleadto?
[A]advocates[B]approaching[C]constantly[D]decrease[E]enlarge[F]financial[G]fundamental[H]gracious[I]ignored[J]intention[K]just
A.inappropriateB.attendC.slipsD.trackE.financeF.unchangeableG.organize
最新回复
(
0
)