首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树巾所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树巾所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数
admin
2019-12-10
27
问题
下列说法中,正确的是( )。
Ⅰ.具有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://jikaoti.com/ti/PgDjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
下面是给出的一段IP数据包头所包含的数据,0000305252400080062C23C0A80101D803E215,请根据IPv4头部格式回答如下问题:(1)该IP包的发送主机和接收主机的地址分别是什么?
在下列事件中,哪个不是设备分配中应该考虑的问题()。
已知加权有向图G如下,回答下列问题:(1)画出该有向图G的邻接矩阵;(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
下图所示的CPU逻辑框图中,有两条独立的总线和两个独立的存储器。已知指令存储器IM最大容量为16384字(字长18位),数据存储器DM最大容量是65536字(字长16位)。各寄存器均有“打入”(Rin)“送出”(Rout/)控制命令,但图中未标出。
某时刻进程的资源使用情况如下表所示。此时的安全序列是____。
某计算机处理器主频为50MHz,采用定时查询方式控制设备A的I/O,查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间,为保证数据不丢失,每秒需对其查询至少200次,则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是____。
下列关于RISC的叙述中,错误的是____。
CPU内部一般包括PC、MAR、MDR、IR等几个寄存器及若干通用寄存器。下图是指令LADRO,(X)的指令流程图,其功能是将主存X号单元的数据取到RO寄存器中,图中M表示主存。(1)请完成该指令流程图中未完成的部分。(2)重新画出当源操作数为间接寻
下面关于进程的叙述中,正确的是()。
随机试题
治疗小儿胆道蛔虫症,应首选的方剂是
(2010)气体和蒸汽在管内稳态流动中面积f与c关系式为df/f=(Ma2—1)dc/c,该式适用的条件为()。
下列各项中,可以作为商标的是()。
工业安装工程质量检验评定中最基本、最基础的项目是( )。
资产管理公司的注册资本应在()亿元以上。
所谓技能,一般认为是通过练习而形成的合乎法则的______。
我国古代所称“五谷”之一的“菽”是指()。
1968年建成的南京长江大桥,丰水期的净空高度是24米,理论上最多能通过3000吨的船舶,在经济高速发展的今天已经成为“腰斩”长江水道、阻碍巨轮畅行的建筑。一位桥梁专家断言:要想彻底疏通长江黄金水道,必须拆除、重建南京长江大桥。以下哪项如果为真,能对这位专
设A为三阶矩阵,α1,α2为A的分别属于特征值一1,1的特征向量,向量α3满足Aα3=α2+α3。证明α1,α2,α3线性无关;
DealingwithDepression(51)Contrarytowhatmanypeoplethinkdepressionisnotanormalpartofgrowingolder.Norisit
最新回复
(
0
)