首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
下列说法中,正确的是( )。 Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点 Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9 Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个
admin
2014-04-17
76
问题
下列说法中,正确的是( )。
Ⅰ.具有10个叶子结点的二叉树中有9个度为2的结点
Ⅱ.设高度为5的二叉树上只有度为0和度为2的结点,则该二叉树中所包含的结点数至少为9
Ⅲ.一棵完全二叉树上有1001个结点,则可知叶子结点的个数为501个
Ⅳ.高度为h的完全二叉树最少有2
h
个结点
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅲ、Ⅳ
D、仅Ⅰ、Ⅱ、Ⅲ
答案
D
解析
Ⅰ:二叉树叶子结点的个数比度为2的结点的个数多1,故Ⅰ正确。
总结:这个性质在选择题中常有体现(见下面的补充例题),并且需要灵活运用。比如题目可能问,二叉树中总的结点数为n,则树中空指针的个数是多少?可以将所有空指针看做叶子结点,则图6-6中原有的所有结点都成了双分支结点。因此,可得空指针域的个数为树中所有结点个数加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-6所示,故Ⅱ正确。
总结:设高度为h的二叉树只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为2h—1。
Ⅲ:由二叉树的性质可知: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=1 001,得到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/1Yxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述当代科技革命发生的背景条件。
唐代府兵的基本单位是()。
简述清代秘密立储制的操作并作出评价。
1901一1939年间美国历届政府在国内经济活动中职能作用的演变。
以下选项不属于希腊城邦的形成方式和途径的是()。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
1543年发表解剖学专著《人体结构论》的是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
第三次科技革命对社会经济结构的影响是()。
论述欧洲一体化进程及其影响。
随机试题
行驶中蓄电池突然损坏如何处理?
A.冰片B.芒硝C.阿魏D.滑石E.血竭易升华的饮片是
能够饱含并透过相当数量重力水的岩层或土层称为()。
依据《中华人民共和国水污染防治法》,()可以根据本行政区域水环境质量状况和水污染防治工作的需要,确定本行政区域实施总量削减和控制的重点水污染物。
销毁公文的主要方式有焚毁、重新制成纸浆、掩埋、清洗消磁。()
三年前,某咨询公司在一份报告中预测,到2030年,全自动驾驶出租车将占据全球三分之一以上的汽车出行市场。这在当时看来似乎有些______。而现在,正如这份报告所说,尽管向自动出行的转型无法______,但整个汽车行业在包括法律法规、基础设施、投资与消费
某社会学家认为:每个企业都力图降低生产成本,以便增加企业的利润,但不是所有降低生产成本的努力都对企业有利,如有的企业减少对职工社会保险的购买,暂时可以降低生产成本,但从长远看是得不偿失,这会对职工的利益造成损害,减少职工的归属感,影响企业的生产效率。以下哪
下列给定程序中,函数fun的功能是:先从键盘上输入一个3行、3列的矩阵的各个元素的值,然后输m出主对角线元素之和。请改正程序中的错误,使它能得出正确的结果。注意:部分源程序在文件MODI1.C中,不要改动main函数,不得增行或删行,也
Forthispart,youareallowed30minutestowriteashortessayentitledTheImportanceofInformationSecurity.Youshouldwri
A、ItisstillOK.B、Youmaybelaughedat.C、Youmaymakebaddecisions.D、Youcouldneverdomaths.B新闻最后提到,如果你对莎士比亚和奥斯丁不够了解的话,
最新回复
(
0
)