首页
登录
从业资格
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
练习题库
2022-08-02
58
问题
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含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
随机试题
[originaltext]M:Checkinhere?W:Yes.M:CanIseeyourticket,please?W:He
Peoplewithpetsfindithardtobelieve,butscientistscontinuetodebatew
[audioFiles]2017m2x/audio_ezfm_021_201702[/audioFiles]StressAsthepac
一个应用软件的各个功能模块可采用不同的编程语言来分别编写,分别编译并产生()
下列关于粉碎目的叙述哪一项不正确A.有利于药物溶解 B.有利于环境保护 C.
建筑意外伤害保险期限应()。A:从施工工程项目被批准正式开工,并且投保人已交付
保荐机构保荐股票上市(股票恢复上市除外)应当向证券交易所提交的文件包括(
投标保证金一般不得超过投标总价的( ),但最高不得超过( )。 A、5%,5
下列关于工程建设项目招标投标资格审查的说法中,错误的是()。A.资格预审一般在
我国在对资本主义工商业进行社会主义改造过程中创造的国家资本主义的低级形式有()。
最新回复
(
0
)