若一棵哈夫曼树共有13个顶点，则其叶子结点的个数为(24)。

admin2015-06-03 51

问题若一棵哈夫曼树共有13个顶点，则其叶子结点的个数为(24)。

选项 A、5
B、6
C、7
D、8

答案C

解析哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下所述。
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w₁，w₂，…， w_n，则哈夫曼树的构造规则如下。
(1)将w₁，w₂，…，w_n看成是有n棵树的森林(每棵树仅有一个结点)。
(2)在森林中选出两个根结点的权值最小的树，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和。
(3)从森林中删除选取的两棵树，并将新树加入森林。
(4)重复第(2)和第(3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。
从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支结点。设二叉树的0度结点(即叶子结点)个数为n₀，2度结点个数为n₂，则树的总结点数n=n₀+n₂。
又因为二叉树有性质：对任何一棵二叉树，如果其叶子结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。所以n=n₂+1+n₂。即13=n₂+1+n₂，n₂=6，n₀=7。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

若一棵哈夫曼树共有13个顶点，则其叶子结点的个数为(24)。

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

软考中级

在缓解和解决IP地址耗尽问题的措施中，(56)上可以把大的网络分成小的子网(57)，以实现本地地址和外部地址的转换。例如把子网掩码为255.255.0.0的网络61.31.0.0分为两个子网，假设第一个子网为61.31.0.0/17，则第二个子网为(58)

DES加密算法采用的密码技术是(1)，它采用(2)位密钥对传输的数据进行加密。著名的网络安全系统Kerberos采用的是(3)加密技术。公钥密码是(4)，常用的公钥加密算法有(5)，它可以实现加密和数字签名。

数据字典是在结构化分析方法中的重要文档。数据字典的组成内容之一就是对加工的描述，常用的加工描述方法(6)。

对于易淬火钢，通过()可以减少淬硬程度，防止产生焊接裂纹。

西望夏口，东望武昌，山川相缪，郁乎苍苍，此非孟德之困于周郎者乎?

巩膜()

国际红十字会设立南丁格尔奖章，作为各国优秀护士的最高荣誉奖章，其颁发的频率是

TheB/Lcanbeissuedby()

对下列交易或事项进行会计处理时，不应调整年初未分配利润的有()。

扩张性货币政策指的是()。

Musiccomesinmanyforms;mostcountrieshaveastyleoftheirown.【C1】______theturnofthecenturywhenjazzwasborn,Americ

EconomicDeclineinEuropeDuringtheFourteenthCenturyP1:Someverynegativefactorsaccountedfortheeconomiccrisisinfou