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

admin2009-02-15 16

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

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

答案B

解析哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，根据这种方法构造出来的二叉树称为哈夫曼树。具体过程如下所述。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1，w2，…，　wn，则哈夫曼树的构造规则为:(1)　w1，w2，…，wn看成是有n棵树的森林(每棵树仅有一个结点)：(2)　在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)　从森林中删除选取的两棵树，并将新树加入森林；(4)　重复第(2)和(3)步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。从以上构造过程可知，哈夫曼树是严格的二叉树，没有度数为1的分支结点。n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点，最终求得的哈夫曼树中共有2n-1个结点。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

在某个支持SNMPv2MIB组的代理中，snmpSerialNo对象的当前值为2006。这时，该代理站同时收到两个管理站发来的set请求，这两个set请求的snmpSerialNo值都是2006，当代理站处理完这两个set请求后，其snmpSerialN

采用UML进行软件设计时，可用()关系表示两类实体之间存在的特殊／一般关系，用聚集关系表示事物之间存在的整体／部分关系。

复层扁平上皮变为单层柱状上皮的部位是

根据目前情况，采用进一步检查发现，病人患有痛风和支气管哮喘，此时应

国家推行(　　)，从而使建设工程监理在全国范围内进入全面推选阶段。

权证的理论价值包括()

根据《银行账户管理办法》的规定，存款人的工资、奖金等现金的支取，只能通过()办理。

中国建设银行在成功完成股份制改革后，又在香港证券市场成功上市。成功上市后，中国建设银行股份有限公司()。

以下各项中，属于空间技术的是()。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

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

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

软考中级

在某个支持SNMPv2MIB组的代理中，snmpSerialNo对象的当前值为2006。这时，该代理站同时收到两个管理站发来的set请求，这两个set请求的snmpSerialNo值都是2006，当代理站处理完这两个set请求后，其snmpSerialN

采用UML进行软件设计时，可用()关系表示两类实体之间存在的特殊／一般关系，用聚集关系表示事物之间存在的整体／部分关系。

复层扁平上皮变为单层柱状上皮的部位是

根据目前情况，采用进一步检查发现，病人患有痛风和支气管哮喘，此时应

国家推行( )，从而使建设工程监理在全国范围内进入全面推选阶段。

权证的理论价值包括()

根据《银行账户管理办法》的规定，存款人的工资、奖金等现金的支取，只能通过()办理。

中国建设银行在成功完成股份制改革后，又在香港证券市场成功上市。成功上市后，中国建设银行股份有限公司()。

以下各项中，属于空间技术的是()。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性。

国家推行(　　)，从而使建设工程监理在全国范围内进入全面推选阶段。