首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树巾所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树巾所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数
admin
2019-12-10
32
问题
下列说法中,正确的是( )。
Ⅰ.具有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
学硕统考专业
相关试题推荐
一个磁盘有N个磁道,寻道时每移过一个磁道耗时T秒,文件相邻的数据块在磁盘上存放的位置平均相隔13个磁道,磁盘旋转延时平均R秒,每个存储块的传输时间为P秒,在这种情况下,传输100个数据块需要的时间是()。
对汇编语言程序员来说,以下部件中不透明的是()。I.指令缓冲器;Ⅱ.移位器;Ⅲ.通用寄存器;Ⅳ.中断字寄存器;V.乘法器;Ⅵ.先行进位链;
在采用线性探测法处理冲突所构成的散列表上进行查找,可能要探测多个位置,在查找成功的情况下,所探测的这些位置的键值()。
在不同网络节点的对等层之间通信需要的是()。
当系统发生抖动(thrashing)时,可以采取的有效措施是____。I.撤销部分进程Ⅱ.增加磁盘交换区的容量Ⅲ.提高用户进程的优先级
为提高散列(Hash)表的查找效率,可以采取的正确措施是____。I.增大装填(载)因子Ⅱ.设计冲突(碰撞)少的散列函数Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题足找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
设有带头结点的循环双链表表示的线性表L===(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a3,……,an……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,采用
CPU内部一般包括PC、MAR、MDR、IR等几个寄存器及若干通用寄存器。下图是指令LADRO,(X)的指令流程图,其功能是将主存X号单元的数据取到RO寄存器中,图中M表示主存。(1)请完成该指令流程图中未完成的部分。(2)重新画出当源操作数为间接寻
下列叙述正确的个数是()。1)向二排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B一树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右子树的高度差的绝对值
随机试题
此患者的诊断是诊断的主要依据是
上述各项中属于医生违背不伤害原则的是上述各项中属于医生违背尊重原则的是
建设项目的()必须对建设项目产生的污染和对环境的影响作出评价,规定防治措施,经项目主管部门预审并依照规定的程序报环境保护行政主管部门批准。
已达到预定可使用状态尚未办理竣工决算的固定资产,应当按照估计价值确定其成本。并计提折旧;待办理竣工决算后,再按实际成本调整原来的暂估价值,同时需要调整原已计提的折旧额。()
企业采用股票期权方式激励职工,在等待期内每个资产负债表日对取得职工提供的服务进行计量的基础是()。
杠杆租赁涉及到出租人、承租人和借款人,而不涉及出售人。()
一般资料:求助者,女性,18岁,大专学生。下面是心理咨询师与求助者的一段咨询谈话:心理咨询师:你好,请坐。你有什么问题,咱们谈谈吧!求助者:我心情很不好,总是烦躁,老感到有什么事情要发生,你能帮帮我吗?心理咨询师:你能谈谈心情怎么了吗?什么让你烦躁
近年,研究人员研发出了一种“人造皮肤”,能够模仿健康年轻皮肤的特点,有望成为人类的“第二层皮肤”。“人造皮肤”交叉融合了医学、生物、化学、材料、工程等多个学科,通过对材料的不断筛选、优化及临床测试,最终才取得这样的成果。现实中,类似的成果还有很多,比如通过
“法治”是
下列有关信息和数据的说法中,错误的是()。
最新回复
(
0
)