首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树巾所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树巾所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数
admin
2019-12-10
49
问题
下列说法中,正确的是( )。
Ⅰ.具有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
学硕统考专业
相关试题推荐
主机A向主机B连续发送了两个TCP报文段,其序号分别为70和100。试问:(1)第一个报文段携带了多少个字节的数据?(2)主机B收到第一个报文段后发回的确认中的确认号应当是多少?(3)如果主机B收到第二个报文段后发回的确认中的
(将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(keyx3)MOD7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。分别计算等概率情况下查找成功
下列选项中,不属于网络体系结构所描述的内容是____。
单级中断系统中,中断服务程序内的执行顺序是____。I.保护现场Ⅱ.开中断Ⅲ.关中断Ⅳ.保存断点V.中断事件处理Ⅵ.恢复现场Ⅶ.中断返回
假定在~个8位字长的计算机中运行如下c程序段:unsignedintx=134;unsignedinty=246;intm=x;intn=y;unsignedintz1=x—y;
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[O]=true;While(flag[1]);Cri
描述滑动窗口机制及其作用。比较停止一等待协议,多帧滑动窗口和后退N帧协议,多帧滑动窗口与选择重传协议的区别。
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50ms,输
下列关于虚拟存储的叙述中,正确的是
以下说法正确的是()。Ⅰ.带头结点的循环双链表L为空的条件是:L->prior=L&&L->next==LⅡ.线性表的插入和删除总是伴随着大量数据的移动Ⅲ.只有删除静态链表的尾结点才不需要移动元素Ⅳ.若线性
随机试题
行车中发现右侧轮胎漏气时怎样处置?
女性,37岁,行锁骨下静脉穿刺置管后2小时,无明显诱因突然出现呼吸困难,血压85/70mmHg,心率124/min,脉搏细弱,听诊心音遥远,检查口唇有发绀、颈静脉怒张。预防该项并发症的措施不包括以下哪~项
位于澳门特区的天迪有限责任公司与福州市得力有限责任公司就一项机械购销合同产生纠纷,并在内地人民法院进行诉讼。关于审理此案过程中文书的送达和相关证据的调查,下列说法错误的是()。
绩效评价指标体系确立的原则有()。
保险合同成立后,保险公司不得解除旅行社责任保险。()
下面对社会工作者一般特征的描述错误的是( )。
根据以下资料,回答下列问题。在粮食中哪一类产品哪一年增长幅度最大?()
搜索考生文件夹下的WAB.xls文件,然后将其复制到考生文件夹下的JIAN文件夹中。
To:ReikoOnoFrom:JunkoLeeRe:TransferHiReiko,Iheardthenewsthismorningaboutyourtransfer.Iwas
DavidHumewasbominEdinburghon26thApril1711toJosephandKatherineHume.Bothparentswereofagood,【C1】al__________no
最新回复
(
0
)