早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
若一棵哈夫曼(Huffman)树共有9个顶点,则其叶子节点的个数为(15)。A.4B.5C.6D.7
题目
若一棵哈夫曼(Huffman)树共有9个顶点,则其叶子节点的个数为(15)。
A.4
B.5
C.6
D.7
参考答案
正确答案:B
解析:哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法,根据这种方法构造出来的二叉树称为哈夫曼树。假设有n个权值,则构造出的哈夫曼树有n个叶子节点。N个权值分别设为w1,w2,…,wn,则哈夫曼树的构造规则如下。第一步:将w1,w2,…,wn看成是有n棵树的森林;第二步:在森林中选出两个根节点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根节点权值为其左右子树根节点权值之和;第三步:从森林中删除选取的两棵树,并将新树加入森林:第四步:重复第二步和第三步,直到森林中只剩一棵树为止,该树即为所求的哈夫曼树。从以上构造过程可知,哈夫曼树是严格的二叉树,没有度数为1的分支节点。n个叶子的哈夫曼树要经过n-1次合并,产生n-1个新节点,最后求得的哈夫曼树中共有2n-1个节点。
解析:哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法,根据这种方法构造出来的二叉树称为哈夫曼树。假设有n个权值,则构造出的哈夫曼树有n个叶子节点。N个权值分别设为w1,w2,…,wn,则哈夫曼树的构造规则如下。第一步:将w1,w2,…,wn看成是有n棵树的森林;第二步:在森林中选出两个根节点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根节点权值为其左右子树根节点权值之和;第三步:从森林中删除选取的两棵树,并将新树加入森林:第四步:重复第二步和第三步,直到森林中只剩一棵树为止,该树即为所求的哈夫曼树。从以上构造过程可知,哈夫曼树是严格的二叉树,没有度数为1的分支节点。n个叶子的哈夫曼树要经过n-1次合并,产生n-1个新节点,最后求得的哈夫曼树中共有2n-1个节点。
看了若一棵哈夫曼(Huffman)...的网友还看了以下:
已知fx是定义在R上的奇函数,当x≥0时,fx=3^x+m(m为常数),则f(-log35)的值为 其他 2020-05-21 …
某有机化合物仅由碳、氢、氧三种元素组成,其相对分子质量小于150,若已知其中氧的质量分数为50%, 化学 2020-05-22 …
一组数据的离散系数为0.6,平均数为10,则方差为( )。A.0.4B.4C.6D.36 财会类考试 2020-05-30 …
有一个两位数,它的十位数字与个位数字之和为5,则符合条件的数有()个.A.4B.5C.6D.无数 数学 2020-06-03 …
某有机化合物仅由碳、氢、氧三种元素组成,其相对分子质量小于150,若已知其中氧的质量分数为50%, 化学 2020-06-16 …
在14与78之间插入n个数组成等比数列,若各项总和为778,则此数列的项数()A.4B.5C.6D 数学 2020-07-16 …
数列{an}是首项为2,公差为3的等差数列,数列{bn}是首项为-2,公差为4的等差数列.若an= 数学 2020-07-30 …
若定义字符数组并初始化:charstr[]="ab\n\012\\";则str数组的元素个数至少为个 其他 2020-11-07 …
已知MOD函数是一个求余函数,其格式为MOD(n,m),其结果为n除以m的余数,例如MOD(8,3) 数学 2020-11-07 …
(2007•牡丹江)一组数据由五个正整数组成,中位数是3,且唯一众数是7,则这五个正整数的平均数是( 数学 2020-11-18 …