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

admin2015-06-03 44

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

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

软考中级

在IPv4向IPv6的过渡期间，如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信，则应该使用(58)；如果要使得纯IPv6结点可以与纯IPv4结点进行通信，则需要使用(59)。(59)

在IPv4向IPv6的过渡期间，如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信，则应该使用(58)；如果要使得纯IPv6结点可以与纯IPv4结点进行通信，则需要使用(59)。(58)

一个网络的两个工作站有问题：“它们只能轮流工作，每次只有一台可以登录入网”，这个部门的其他工作站都工作正常，可能是__________。

手握空拳以食、中、无名、小指近侧指间关节背侧突起部着力的手法是：（）

脑出血与蛛网膜下隙出血的主要区别是

下列选项中，属于世亚行贷款项目的主要采购方式的有()。

已知矩阵，则A的秩r(A)等于()。

潜在投标人名单确定后，对每一个潜在投标人提供的资料进一步评审，合格的投标人应具有圆满履行合同的能力，符合下列条件(　　)。

在质量管理体系八项原则中，体现组织进行质量管理的基本出发点与归宿点的原则是()。

属于工资核算模块初始化设置的有()。

孟子说“征于色，发于声，而后喻”，意在强调教师的()

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

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

软考中级

在IPv4向IPv6的过渡期间，如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信，则应该使用(58)；如果要使得纯IPv6结点可以与纯IPv4结点进行通信，则需要使用(59)。(59)

在IPv4向IPv6的过渡期间，如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信，则应该使用(58)；如果要使得纯IPv6结点可以与纯IPv4结点进行通信，则需要使用(59)。(58)

一个网络的两个工作站有问题：“它们只能轮流工作，每次只有一台可以登录入网”，这个部门的其他工作站都工作正常，可能是__________。

手握空拳以食、中、无名、小指近侧指间关节背侧突起部着力的手法是：（）

脑出血与蛛网膜下隙出血的主要区别是

下列选项中，属于世亚行贷款项目的主要采购方式的有()。

已知矩阵，则A的秩r(A)等于()。

潜在投标人名单确定后，对每一个潜在投标人提供的资料进一步评审，合格的投标人应具有圆满履行合同的能力，符合下列条件( )。

在质量管理体系八项原则中，体现组织进行质量管理的基本出发点与归宿点的原则是()。

属于工资核算模块初始化设置的有()。

孟子说“征于色，发于声，而后喻”，意在强调教师的()

潜在投标人名单确定后，对每一个潜在投标人提供的资料进一步评审，合格的投标人应具有圆满履行合同的能力，符合下列条件(　　)。