首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有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
)