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

admin2015-06-03 32

问题若一棵哈夫曼树共有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)。

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

软考中级

在ISDN网络中，与ISDN交换机直接相连的是(1)设备，它们通过(2)实现互联。NT1到用户设备之间的连接点是(3)。非ISDN设备要通过(4)设备接入ISDN网络，该设备的主要作用是(5)。

ISO9000系列标准和软件成熟度模型CMM都着眼于质量和过程管理。ISO9000系列标准的主导思想如下：(1)强调质量(4)；(2)使影响产品质量的全部因素始终处于(5)状态；(3)要求证实企业具有持续提供符合要求产品的(6)：

图6—9表示了某个数据的两种编码，这两种编码分别是()。

A．脾胃虚寒，胃中无火B．脾胃虚寒，胃气上逆C．邪气干扰，胃虚失和D．胃气上逆，失于和降E．饮食停滞，浊气上逆呕吐的病机主要是

下列对影像增强器电子透镜的解释，错误的是

慢性肾衰竭水负荷过重所致心力衰竭，最佳治疗措施是

19世纪中叶起,沿海一带的上海、广州等城市近代房地产业产生并迅速发展,但这些都是以()的私有制为基础。

建设工程质量是指建设工程满足相关标准规定和()的过程。

高等级路面一般由（）构成。

计算机种类繁多，按照“传统的分类”，可以将计算机分为()。

Seldom______hiswifepunishesherchildrenforspeakingouttheirownideasfreely.

Despitethebrouhaha(骚动)overstolene-mailsfromtheUniversityofEastAnglia,thescienceofclimatechangeiswellenoughest