首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
admin
2019-12-10
46
问题
下列说法中，正确的是( )。
Ⅰ．具有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必须高于(
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是()。
以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条
已知有向图G=(V，A)，其中V={a，b，c，d，e)，A={，，，，，}，对该图进行拓扑排序，下面序列中不是拓扑排序的是()。
设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0
在图B-1所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是____。
下列选项中，描述浮点数操作速度指标的是____。
某32位计算机系统采用段页式虚拟存储管理，现有一个进程被分成5段，其段号和段长见下表，段内分页，页表见下，存放在内存中，每页的长度为4096B。进程运行到某一个指令，其地址为(2，3，010)，当前CPU的寄存器和地址加法器的状态如图所示，当上述指令执行时
随机试题
患者，女，26岁。停经11周。1个月前自测尿妊娠试验阳性，恶心呕吐3周，近1周加重，B型超声示宫内早孕。孕妇出现恶心、呕吐等早孕反应，与哪种激素有关
一般情况下法定传染病报告人不包括
间接信用指导是指中央银行通过()等办法来间接影响商业银行等金融机构行为的做法。
隧道通风控制系统的功能包括()。
刘某为甲期货公司从业人员，在得知乙期货公司给居间人较高的返佣后，私下将新开发的客户介绍给乙期货公司。[2012年11月真题]根据上述事实，请回答以下问题。刘某违反的期货从业人员执业行为准则是()。
下列各项中，属于营业税兼营行为的有()。
简述教育研究的意义。
学生先学习了质量与能量、热与体积、遗传结构与变异等概念之间的关系，之后又学习需求与价格之间的关系。这种学习属于()
A、 B、 C、 D、 B
Thegovernmentissaid______.(正在考虑采取紧急措施来减轻其承受的金融压力)
最新回复
(
0
)
