首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个
admin
2014-04-17
99
问题
下列说法中，正确的是( )。
Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点
Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树中所包含的结点数至少为9
Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数为501个
Ⅳ．高度为h的完全二叉树最少有2
h
个结点
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅲ、Ⅳ
D、仅Ⅰ、Ⅱ、Ⅲ
答案
D
解析
Ⅰ：二叉树叶子结点的个数比度为2的结点的个数多1，故Ⅰ正确。
总结：这个性质在选择题中常有体现(见下面的补充例题)，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为n，则树中空指针的个数是多少?可以将所有空指针看做叶子结点，则图6-6中原有的所有结点都成了双分支结点。因此，可得空指针域的个数为树中所有结点个数加1，即n+1个。
这个性质还可以扩展，即在一棵度为m的树中，度为1的结点数为n
1
，度为2的结点数为n
2
，…，度为m的结点数为n
m
，则叶子结点数n
0
=1+n
2
+2n
3
+…+(m一1)n
m
。推导过程如下：
总结点=n
0
+n
1
+n
2
+n
3
+…+n
m
……………………………① 总分支数=1×n
1
+2×n
2
+…+m×n
m
(度为m的结点引出m条分支)………………………② 总分支数=总结点数一1………………………………………………………………………③ 将式①和式②代入式③并化简得 n
0
=1+n
2
+2n
3
+…+(m一1)n
m
Ⅱ：最少结点的情况应该是除根结点层只有1个结点外，其余4层都有2个结点，因此结点总数为2×(5—1)+1=9，如图6-6所示，故Ⅱ正确。
总结：设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为2h—1。
Ⅲ：由二叉树的性质可知：n
0
=n
2
+1，且完全二叉树度为1的结点个数要么为0，要么为1。又因为二叉树的总结点个数n=n
0
+n
1
+n
2
。将n
0
=n
2
+1代入，可得n=2n
0
+n
1
-1：由n=1 001，得到2n
0
=1002+n
1
。 ①当n
1
=1时，无解。 ②当n
1
=0时，可解得n
0
=501。 故Ⅲ正确。
Ⅳ：高度为h的完全二叉树中，第1层～第h一1层构成一个高度为h—1的满二叉树，结点个数为2
h-1
-1。第h层至少有一个结点，所以最少的结点个数=(2
h-1
-1)+1=2
h-1
，故Ⅳ错误。
转载请注明原文地址:https://www.kaotiyun.com/show/1Yxi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
下列关于胡司战争的叙述错误的一项是()。
古希腊是西方文明的发源地，古希腊雅典的民主政治则开启了西方民主制度的先河。下列关于雅典民主政治的说法，符合史实的有()。①民主政治时期的雅典没有国王②公民大会是雅典国家的最高决策机构③伯里克利时期，雅典民主政治达到了顶峰④包
(北魏孝文帝)“初谋南迁，恐众心恋旧，乃示为大举，因以胁定群情，外谋南伐，其实迁也。1日人怀土，多不所愿，内惮南征，无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。
明治维新时期的土地改革，说法不正确的是()。
规定了电流、电动势、电阻等概念的物理学家是()。
阅读材料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为仁，以神
阅读史料回答以下问题：天既哀大地生人之多艰，黑帝乃降精而救民患，为神明，为圣王，为万世作师，为万民作保，为大地教主。生于乱世，乃据乱世而立三世之法，而垂精太平。乃因其所生之国，而立三世之义，而注意于大地远近、大小若一之大一统。乃立元以统天，以天为
以数组Data[m+1]作为循环队列SQ的存储空间，front为头指针，rear为队尾指针，则执行出队操作的语句是()。
对于下图G，按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示；(2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
随机试题
男性，60岁，干部。突然右侧肢体活动不灵，历时10分钟缓解。次日晨起出现右侧偏瘫。病后3日来诊。BP：20/12kPa(150/90mmHg)，为确诊首选的检查是
犬，由于纤维环破裂、髓核突出，压迫脊髓，临床上主要表现以疼痛、共济失调、肢体麻木，运动障碍为特征的疾病。本病X线检查显示
A．单纯疱疹病毒B．人乳头瘤病毒C．淋病双球菌D．衣原体E．人免疫缺陷病毒
关于犯罪主观方面的说法，下列哪些选项是正确的?()
(2006)如图3．1—1所示，容重为10000N／m3的理想流体在直管内从1断面流到2断面，若1断面的压强p1=300kPa，则2断面压强p2等于()kPa。
为了排除燃气管道中的冷凝水和石油伴生气管道中的轻质油，管道敷设时应有一定坡度，以便在低处设()，将汇集的水或油排出。
总承包单位甲公司经建设单位同意，将幕墙工程分包给乙公司施工。后该分包工程出现了施工质量问题，建设单位要求乙赔偿，下列责任赔偿的说法中，能够成立的是()。
下列关于在资产负债表日劳务收入确认和计量的表述中，正确的有()。
设f(x)具有连续导数，且F(x)＝(x2－t2)f’(t)dt，若当x→0时F’(x)与x2为等价无穷小，则f’(0)＝______．
CertainpracticescommonintheearlyUnitedStatesmakeiteasyforhistorianstounderestimatetheextentofAmericanwomen’s
最新回复
(
0
)
