首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
admin
2014-04-17
52
问题
下列说法中,正确的是( )。
Ⅰ.具有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
学硕统考专业
相关试题推荐
简述旧金山体制的内容及其实质。
下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
戊戌政变发生的时间是()。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
对三国鼎立局面的形成起到关键性作用的战役是()。
简述清代秘密立储制的操作并作出评价。
1916年研究短波无线电通信,为现代远距离无线电通信奠定了基础的发明家是()。
隋朝建立了三省六部制,其中负责审议的部门是()。
关于美国内战,不正确的说法是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
随机试题
某小型露天采石场,采用自上而下的分层方式开采,层高12m,采用挖掘机铲装,自卸卡车运输,年采剥量约5×104t。2016年8月10日,调度李某安排人员在第三层台阶上方12m处进行打爆破孔作业,至12日共完成31个爆破孔,其中25个孔用于此次爆破作业,爆破
电路如图7-4所示,已知I=1A,US为()V。
甲、乙、丙三个股东组建了A有限责任公司。后甲因为欠债,自身财产不足清偿其债务,在其债权人的请求下,法院决定依据法院判决强制执行甲在A公司的股权。下列说法不正确的是()。
幼儿园对幼儿进行体、智、德、美教育的主要手段是()。
简政放权改革成效不断显现,但改革进展与人民群众的期待还有较大差距。改革中,上级部门“咬咬牙”放掉的权力,又被下级部门攥在了手中;权力下放了,然而企业审批要准备的材料依然名目繁多……不驱除这些“拦路虎”,简政放权的威力就会被侵蚀、被消解,事倍功半。这说明(
生育率是指一定年龄内每千名育龄妇女所生孩子数。右图是我国各省不同年代生育率分布的盒形图,盒内的分割线为中位数,线段向上至最大值,向下至最小值;影响我国生育率变化特点的主要原因是()。
苏联在哪次会议上通过了社会主义工业化方针,并在此之后开始了大规模的工业化建设?()。
划分经济社会形态的根本标准是()。
TheUnitedStatestakesabiggershareoftheinternationalstudentmarketthananyothercountry.However,with22%ofthetota
WhendidthefamilyCarbecomecommoninAmerica?Intheearly______.
最新回复
(
0
)