首页
登录
从业资格
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
练习题库
2022-08-02
43
问题
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含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
随机试题
Tobelievethataculture’sachievementcanbemeasuredbythe(i)______ofits
使电流速断保护有最小保护范围的运行方式为系统的()A.最大运行方式
精液检查,精子前向运动缓慢,应按世界卫生组织分类,定为A.a级 B.b级 C
患者女性,75岁,右大腿卵圆窝反复出现圆形已多年,此次因便秘突出包块增大,用力还
说服教育法的方式有语言文字说服和()A.事实说服 B.理论说服 C.直接
下列选项中不属于美术教学设计内容的是( )。A.教学目标设计 B.教学用具设
具有一个侧枝的花鹿茸是A.单杠茸 B.三岔茸 C.四岔茸 D.大挺 E.
某技术项目预期收益高,开发成功概率低,根据项目地图法,改项目属于()类型项目A.
视近物不需眼调节或只作较小程度调节的是A.近视 B.老视 C.远视 D.散
建设单位负责采购设备时,控制质量的首要环节是( )。A、编制设备监造方案 B
最新回复
(
0
)