首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
admin
2019-12-10
38
问题
下列说法中，正确的是( )。
Ⅰ．具有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)如果设计字
CRC校验是目前常用的检错方式。如果采用的多项式为G(X)=X4+X+1，那么对于要传的信息串1101011011的CRC校验码是()。
某主机的MAC地址为00．15．C5．C1．5E．28，IP地址为10．2．128．100(私有地址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。请参考图中的数据回答以下问题。
某机器有一个标志寄存器，其中有进位／借位标志CF、零标志ZF、符号标志sF和溢出标志OF，条件转移指令bgt(无符号整数比较大于时转移)的转移条件是____。
已知一个带有表头结点的单链表，结点结构为：假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
以下关于查找方法的说法正确的是()。I顺序查找法只能在顺序存储结构上进行Ⅱ折半查找法可以在有序的双向链表上进行Ⅲ分块查找的效率与线性表被分为多少块有关
某模型机的通路结构如下图所示，用寄存器传送语句(如PC→MAR)，拟出下列指令从读取到执行的完整流程。(1)数据传送指令MOVX(R0)，Y(R1)，源和目的操作数地址均采用变址寻址，第1个参数X为源操作数的形式地址，第2个参数为目的操作数的形式地址，
下列关于RISC的叙述中，错误的是()。
下列说法正确的是()。Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量Ⅲ．广度优先遍历算法类似于树中的后序遍历算法
随机试题
当供气间发生大量泄漏时，操作人员应该马上()。
计算机的特点是处理速度特别快、计算精度高、存储容量大、可靠性高、工作自动化以及()
马睛俞穴的正确针刺手法为
小强成长在父母溺爱的家庭里，从小养成了“以我为中心”、娇蛮、放纵、说谎等坏毛病。这说明()是影响品德形成和发展的外部因素之一。
()是教师职业道德最基本也是最重要的作用。
下列选项与我国古代帝王相关，按时间先后排序正确的是：①车同轨，书同文，统一度量衡②修运河，创科举，三征高丽③休养生息④杯酒释兵权⑤以人为镜，可以明得失
下列关于机关事业单位基本养老金的叙述，错误的是：
司法权和行政权在真正意义上分离，实行独立审判的制度始于()。
艾滋病艾滋病是一种威胁生命的疾病，它侵袭人体内的自然免疫系统，破坏人体的自卫能力。艾滋病本身并不致命，但是，由于人体的免疫系统遭到破坏，病人几乎没有能力来抵御其他许多疾病的侵袭，例如，肺炎、癌症、致盲性疾病和精神错乱。艾滋病病
Standardsforcommercialeggproductionvarygreatlyaroundthecountry.Inmoststates,theegg-layinghensare【S1】______togeth
最新回复
(
0
)
