首页
登录
从业资格
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
练习题库
2022-08-02
62
问题
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含k个结点时,其二叉链表结点中必有( )个空的孩子指针。A.k-1B.kC.k+1D.2k
选项
A.k-1
B.k
C.k+1
D.2k
答案
C
解析
二叉树的二叉链表存储结构中每个结点有2个指针。每个结点有0个、1个或者2个空指针对应有2个、1个、0个非空指针。
二叉树中边的个数等于非空指针的个数。
假设二叉树中节点的总个数为N
假设二叉树中边的个数为M
假设二叉树中度为0的结点的个数为n0
假设二叉树中度为1的结点的个数为n1
假设二叉树中度为2的结点的个数为n2
所以有n0+n1+n2=N-------------(1)
二叉树中除了根结点之外,其他的结点都有一条便进入该结点,所以二叉树中边的总个数为M=N-1;-------(2)
又M=n1+2×n2;-------------------------(3)
所以由(1)(2)(3)可得n0=n2+1;--------------------(4)
设空节点的个数为K,则K=2×n0+n1-------------------(5)
结合(1)(4)(5)可以得到K=N+1(空指针的个数比结点总个数多1)
由(2)可以知道边数M=N-1;(二叉树的边数为结点个数减1)
由(4)可以知道度为0的结点的个数(叶子结点个数)=度为2的结点个数+1(n0=n2+1;)。
转载请注明原文地址:https://tihaiku.com/congyezige/2410505.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
完整的软件测试需要经过()。A.白盒测试、黑盒测试两个步骤 B.人工测试、机
信息资源规划可以概括为“建立两个模型和一套标准”,其中“两个模型”是指信息系统的
如下表所示,有两个关系E和F,若它们经过某一关系运算后的结果为{计算机学院},这
一颗5层的二叉树,其最多有()个结点,第5层最多有()个结点。
( )是构成我国保护计算机软件著作权的两个基本法律文件。单个自然人的软件著作权
关于查找运算及查找表的说法,错误的是( )。A.哈希表可以动态创建 B.二叉
将一个关系r分解成两个关系r1和r2,再将分解之后的两个关系r1和r2进行自然连
以下关于单链表存储结构特征的叙述中,不正确的是( )。A.表中结点所占用存储空
假定用户A、B分别从I1、I2两个CA取得了各自的证书,下面( )是A、B互信
下表中两个事务的调度带来的问题是( )。 A.丢失修改 B.读脏数据 C
随机试题
Ourcorporation’sobligationunderthis______islimitedtorepairorreplaceme
ThroughouttheU.S.studentsaregettingouttheirNo.2pencils,readyendu
OnMother’Day,it’scustomarytospeakaboutthesacrificesourmothersmad
[originaltext]TheAmericanPetProductsAssociationcarriesoutaNationalP
老师要求学生在学期结束时必须演唱一段京剧唱腔。这一教育属于《义务教育音乐课程标准
下列镇痛药属于阿片受体部分激动剂的是A.纳洛酮 B.芬太尼 C.安那度 D
詹森指数衡量的是基金组合的实际收益率与证券市场线上具有相同风险水平组合的期望收益
保荐机构和保荐代表人的注册登记事项发生变化的,保荐机构应当自变化之日起()个工作
(2021年真题)圆融公司经过多年的发展,一直占据行业第一的位置。但是2018年
下列有关职业怀疑的说法中,错误的是()。A.职业怀疑要求主观地评价管理层和治理
最新回复
(
0
)