首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
admin
2014-04-17
78
问题
下列说法中,正确的是( )。
Ⅰ.具有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
学硕统考专业
相关试题推荐
简述维也纳会议的内容。
日本明治维新和中国戊戌变法一成一败的原因。
1971年9月美苏英法四国签署(),肯定了西柏林的占领制度,柏林问题得以解决。
蒙古军西征之后,罗斯处于()的控制之下。
波兰三次被瓜分的时间是()
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现
下图是某模型机CPU的组成框图。设该CPU采用同步控制逻辑,分取指周期、取第一操作数周期,取第二操作数周期、执行周期四个机器周期,每个机器周期有T0、T1、T2三个节拍。试写出如下双操作数运算指令的微操作命令及节拍安排。ADDR0,(R1)完成功
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
随机试题
国际政治
根据《劳动合同法》的规定,劳动者有下列哪些情形之一的,用人单位可以解除劳动合同()
最简单的甘油磷脂是
男,32岁。交通事故致头面部复合伤。伤后昏迷45min,造成吸人性窒息,正确的处理方法是
男,35岁。从高处跳下时,双下肢顿时感到无力。
私营企业主王某办公室的一台DVD播放机无法正常使用,遂通知工作人员刘某拿出去扔掉。刘某将该播放机修理好后拿回家使用。王某得知该播放机能够正常使用后,要求刘某返还。关于该播放机归属的说法,正确的是()。(2010年单项选择第5题)
下列不属于房地产经纪机构人力资源管理中的内部选拔的优点的是()。
在现行公开招标方式下,国债的销售价格是()。
辩证的否定观认为新事物必然取代旧事物,这是因为
若对n个元素进行直接插入排序,则进行第i趟排序过程前,有序表中的元素个数为______。
最新回复
(
0
)