首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
admin
2019-12-10
34
问题
下列说法中，正确的是( )。
Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点
Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9
Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数为501个
Ⅳ．高度为h的完全二叉树最少有2h个结点
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅲ、Ⅳ
D、仅Ⅰ、Ⅱ、Ⅲ
答案
D
解析
Ⅰ：二叉树叶子结点的个数比度为2的结点的个数多1，故I正确。
总结：这个性质在选择题中常有体现，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为n，则树中空指针的个数是多少?我们可以将所有的空指针看作叶子结点，则图中原有的所有结点都成了双分支结点。因此可得空指针域的个数为树中所有结点个数加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-4所示，故Ⅱ正确。
Ⅲ：由二叉树的性质可知：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=1001，得到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/wm3i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
某计算机采用页式存储管理，内存中现有1000个页表项，CPU的cache中可以存放N个页表项，该系统中，CPU内存访问的时间为lOOns，对cache访问的时间是5ns，如果希望页表映射的平均时间降到20ns以下，那么cache中的N必须高于(
CSMA／CD以太网中，发生冲突后，重发前的退避时间最大是()。
在CSMA／CD协议中，下列指标与冲突时间没有关系的是()。
在操作系统的以下功能中，不需要硬件支持的是()。
假设有k个关键字互为同义词，若用线性探查法把这k个关键字存入，至少要进行的探查次数是()。
下列选项中，能缩短程序执行时间的措施是____。I．提高CPU时钟频率Ⅱ．优化数据通路结构Ⅲ．对程序进行编译优化
若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。
在图B-1所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是____。
已知一个带有表头结点的单链表，结点结构为：假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是_______。
随机试题
A．氟尿嘧啶B．噻嗪类药C．局麻药D．环孢素E．胰岛素抑制Na+，阻断神经冲动传导的药物是
在Word2010中，可以对选定的文本进行移动的方法有________。
要求组装精度高的构件，以及角钢、型钢的翼缘板内缘、曲线部分等都可以作装配定位的基准面。()
帕累托的社会分层理论被称为【】
元杂剧中的“末”是指男角。()
二尖瓣狭窄的病理生理正确的是()。
幼儿园课程的实施要通过拟定各层次的教育教学计划，并通过幼儿在园的_______以及一系列具体的教育活动来进行。
在基础训练阶段，儿童少年的训练负荷有很大的提高空间，因此要尽可能加大训练负荷，促进其竞技能力的快速提高。()
《民法典》第419条规定：“抵押权人应当在主债权诉讼时效期间行使抵押权；未行使的，人民法院不予保护”。请对该条规定的民法理论基础，尤其是诉讼时效与债权和抵押权的关系加以评析。[中财2009年研改编]
Whowasthemostimportantpersoninthespeaker’schildhood?Thespeaker’s______.
最新回复
(
0
)
