首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
admin
2014-04-17
48
问题
下列说法中,正确的是( )。
Ⅰ.具有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
学硕统考专业
相关试题推荐
分析辛酉政变后清政府内外政策的变化。(陕西师范大学2015年中国史真题)
外国侵略者火烧圆明园事件是发生在()中。
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
下列有关俄国农奴制改革的表达,不正确的是()。
唐代府兵的基本单位是()。
根据地理大发现、文艺复兴和宗教改革等重大事件,阐述西欧地区在15—16世纪发生的历史性转变。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
洋务派创办军事工业的方式是()。
现有一个长度为3000B的IP数据报,其IP头部的长度为20B,该IP数据报如在最大帧长度为1518B的以太网中进行传输,那么为了正确传输,需要将其拆分的数据报个数是()。
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:求图G的关键路径,并计算该关键路径的长度。
随机试题
隋唐时期,州的长官仍称()
Itwasverykindofyoutodothewashing-up,butyou______it.
急性髓性白血病(急性早幼粒细胞白血病除外)的一线治疗方案为
扩张型心肌病与心包积液鉴别,哪一项检查最有帮助
在________的日子,那些________的书店,如同一抹朝霞,给人带来光明和希望。一代代的人,在书店里遇到了光亮,遇到了精神偶像,获得知识、力量和勇气。填入划横线部分最恰当的一项是:
A.黄色黏稠脓液B.淡黄稀薄脓液C.翠绿色、稍黏稠、有酸臭味的脓液D.灰白或灰褐色、有明显腐败坏死臭味的脓液E.稀薄污浊、暗灰色米汤样、夹杂干酪样坏死物的脓液混合细菌感染的脓液为()。
Youknowyouhavetoread"betweenthelines"togetthemostoutofanything.Iwanttopersuadeyoutodosomethingequallyim
CPU主要技术性能指标有()。
FaceuptoitOnegreatobstacle(障碍)ontheroadtohealthafterasignificantlossisdenial.Insteadoffacing______【51】has
A、 B、 C、 B
最新回复
(
0
)