首页
登录
从业资格
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
练习题库
2022-08-02
77
问题
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含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
随机试题
Whatdidthemanagersendinresponsetotheenquiryof6thNovember?______for
Allofthefollowingwerereasonsfortheproposaloftheamendmenttotheconst
Youdon’tfindmanypeoplethesedayswhowouldkeepabeeintheirpurse.B
意识障碍伴瞳孔缩小,可见于A.阿托品中毒 B.酒精中毒 C.有机磷农药中毒
按噪声来源属于建筑施工噪声的有( )A.高音喇叭 B.打桩机 C
妊娠8~9个月时,或腹中痛,痛定仍然如常者,称为A.试胎 B.弄胎 C.垢胎
政府举办的基层医疗卫生机构要全部配备、使用并按零差率销售的是A.非处方药B.传统
关于个人借款合同的格式条款与非格式条款,下列表述错误的是()。A.对格式条款有
柏拉图的教育思想集中体现在其代表作()中A.《理想国》 B.《教育漫话》
根据合同法律制度的规定,下列关于运输合同的表述中,正确的是( )。A.运输中的
最新回复
(
0
)