首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
下列说法中，正确的是( )。 Ⅰ．具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ．设高度为5的二叉树上只有度为0和度为2的结点，则该二叉树巾所包含的结点数至少为9 Ⅲ．一棵完全二叉树上有1001个结点，则可知叶子结点的个数
admin
2019-12-10
51
问题
下列说法中，正确的是( )。
Ⅰ．具有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
学硕统考专业
相关试题推荐
已知在二叉树中，T为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。
快速排序算法中，如何选取一个界值(又称为轴元素)，影响着快速排序的效率，而且界值也并不一定是被排序序列中的一个元素。例如，我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
假设有8个记录A、B，C、D、E、F、G、H存放在磁盘里，每个磁道有8个扇区，正好可以存放8个记录。假设磁盘旋转速度为20ms／r，处理程序每读出一个记录后，用2ms的时间进行处理，请问：(1)当记录A、B、C、D、E、F、G、H按顺序放在磁
已知一个带有表头结点的单链表，结点结构为：假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题足找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路
若浮点运算结果尾数不是规格化数，将进行结果规格化。结果规格化有左规和右规之分，下列操作中，属于结果规格化的操作是()。I．尾数左移1位，阶码加1Ⅱ．尾数左移1位，阶码减1Ⅲ．尾数右移1位，阶码加1Ⅳ．尾数右移1位，阶码减1
设需在两台计算机间经两个中间节点传送100M字节的文件，假定：(1)计算机与中间节点间的通信线路以及中间节点间通信线路的通信速率皆为8Kbps；(2)数据传输的差错可以忽略不计；(3)中间节点存储转发时间可忽略不计；
若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是()。
在微指令的编码方式中，若微命令数相同，下列叙述中正确的是()。I．直接控制方式与编码控制方式的微指令长度相等Ⅱ．最短编码控制和直接控制方式不影响微指令字长Ⅲ．编码控制方式的微指令比直接控制方式的微指令短Ⅳ．
为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是____。
随机试题
Idon’tthinkitistherighttimematyou______.
若切除猴大脑皮层某个手指的感觉代表区，其结果是
属于必需脂肪酸的是
24岁妇女，孕33周，初产妇，产前检查：胎背位于母体腹部右侧，胎心位于脐右上，宫底部触及浮球感，耻骨上方先露部较软，不规则，诊断何种胎方位
项目财务评价的项目资本金财务现金流量表与项目财务现金流量表相比，现金流出所包含内容相同的有()。
在Excel中，要将有数据且带有格式的单元格恢复为普通的单元格，先要选定该单元，然后使用()。
我国证券交易所的组织形式是()。
吴光、吴明、吴亮三兄弟共同出资购买了一套三层高的临街商品房，同时约定三人分别享有一、二、三层的所有权。之后某广告公司在房屋外墙悬挂了广告条幅，三人对该栋房屋的使用也发生争执。鉴于本案的情况，下列说法正确的是()。
关于法律责任概念的理解，下列表述不正确的有()。
有如下程序：intx=3；do{x一=2；cout＜＜x，}while(!(一x))；执行这个程序的输出结果是()。
最新回复
(
0
)
