首页
登录
从业资格
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含
练习题库
2022-08-02
40
问题
设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含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
随机试题
Shouldapartyrequestcancellationofthecontractwithoutavalidreason,itsh
Historically,humansgetseriousaboutavoidingdisastersonlyafteronehas
Itdawnedonme________hardworkwouldgetpeoplesomewhere.A、whichB、whomC、wh
[originaltext]M:Hello,Miss.Whatbringsyouheretoday?W:(13)Iamnotfeel
工程开工报审表内容应符合现行国家标准《建设工程监理规范》的有关规定。
“标明风景名胜区、基本农田保护区、生态敏感区以及重要的自然和历史文化遗产位置和范
(2018年真题)看涨期权多头的行权收益可以表示为()。(不计交易费用)A
下列关于资产或负债计税基础的表述中,正确的有()。A.资产的计税基础是指账
招标文件一般包括:投标邀请书、投标人须知、投标文件格式及( )等。A.评标标准和
下列物质中,食物的特殊动力作用最强的是A.糖 B.脂肪 C.蛋白质 D.维
最新回复
(
0
)