首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
admin
2014-04-17
103
问题
下列说法中,正确的是( )。
Ⅰ.具有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://kaotiyun.com/show/1Yxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述战后西欧经济的变化过程。
日本明治维新和中国戊戌变法一成一败的原因。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
下列不属于维也纳会议召开的目的的是()。
西汉时期,张骞第一次出使西域的主要目的是()
1901一1939年间美国历届政府在国内经济活动中职能作用的演变。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
1543年发表解剖学专著《人体结构论》的是()。
将两个长度为N的有序表归并到一个长度为2N的有序表,最少需要比较的次数是(),最多需要比较的次数是()。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
随机试题
A.包埋前染色B.包埋后染色C.包埋中染色D.超薄切片免疫染色E.石蜡切片免疫染色超微结构保存较好,方法简单但抗原活性可能减弱
热邪导致月经病下列哪项是错误的:
某企业拟新建一条生产线,通过对该产品的敏感性分析,影响产品未来现金流量的主要不确定因素是项目投资额、产品市场前景和原材料价格水平。该项目的投资额有两种可能,分别是3000万元和2000万元。项目面临两种可能的产品市场状态:畅销和滞销,所对应的年收入分别为1
大型机械设备和多班作业的机械必须建立()。
业务(1)中销售白酒从价计征应缴纳的消费税为( )万元。业务(3)中外购白酒勾兑成低度酒销售,共应纳消费税( )万元。
在Photoshop中,在运用颜色加深着一混合模式时,与白色混合时改变基色。
2019年,全年全国居民人均可支配收入30733元,比上年增长8.9%。接常住地分,城镇居民人均可支配收入42359元,比上年增长7.9%。城镇居民人均可支配收入中位数39244元,比上年增长7.8%。农村居民人均可支配收入16021
在探讨情绪(积极情绪、中性情绪、消极情绪)、活动性质(丰富、单调)、估计方式(对正在发生的事件的评估、事后回忆)对时间估计的影响的一项研究中,其实验处理有
下列各句,没有语病的一句是:
______指只有满足连接条件的记录才包含在查询结果中。
最新回复
(
0
)