首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2019-12-10
59
问题
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
选项
A、n—1
B、n
C、n+1
D、n+2
答案
C
解析
首先,对于一棵树来讲,每个非终端结点(除了树的根结点)转换成二叉树后都对应一个无右孩子的结点,因为一个非终端结点至少有一个孩子结点,其最右边的孩子结点转换成二叉树后一定没有右孩子。为什么要除去根结点?因为根结点比较特殊,树转换成二叉树之后,根结点本身也将会没有右孩子。所以对于一棵具有n个非终端结点的树来讲,将其转换成二叉树之后,二叉树中无右孩子的结点个数为n+1个。其实,此时已经可以选出答案了,因为一棵树也可以算是一个森林。
如果一个森林有多棵树(假设有x棵),我们先把所有树的根结点拿出来。除根结点之外的非终端结点(n—x个)转换成二叉树之后都是对应一个无右孩子的结点,可得到n—x个无右孩子的结点。但是,x个根结点是不是就对应2x个无右孩子的结点?显然不是,因为下一棵数将会成为上一棵树根结点的右孩子(见图5—3),所以只有森林的最后一棵树的根结点才会变成无右孩子的结点,故x个根结点将会得到x+1个无右孩子的根结点,所以一共可以得到n—x+(x+1)=n+1个无右孩子的根结点。
从图5—3可以看出,三棵树的根结点A、E、G转换成二叉树之后,只有最后一棵树的根结点G是没有右孩子的。
综上分析,二叉树中无右孩子的结点个数为n+1个,故选C选项。
解题技巧:使用特殊值代入法,如图5—4所示。
可以从图5—4中很直观地看出无右孩子结点比非终端结点多1。
补充例题:设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是( )。
A.m—n
B.m—n—1
C. n+1
D.条件不足,无法确定
解析:由转换规则可知,二叉树中除了左子树和根结点来源于原森林中第一棵树,其余结点来源于森林中的其他树,其他树的结点总数为n,则第一棵树的结点个数为m—n,故选A选项。
转载请注明原文地址:https://kaotiyun.com/show/uG3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下面对计算机网络体系结构中协议所做的描述,错误的是()。
若已知一个栈的入栈序列是1,2,3…….n,其输出序列为p1,p2,p3…….pn,若p1=n,则pi是()。
如果下表是路由器R1的路由表,仔细分析各个表项的特点,并回答如下问题。(1)给出m0和m1所在的网络号,以及可连接的最大主机数目。(2)给出接口m0,m1和m2的合理的IP地址。(3)试给出网络的拓扑。
段页式存储管理中,某个进程的段表和页表如下图所示,页的大小为4096B,现有逻辑地址(1,8228),其对应的物理地址是()。
某计算机采用Cache一主存一磁盘三级存储系统。Cache的访问时间为t1ns,命中率为p1;若Cache未命中,CPU需直接访问主存,访问时间为t2ns,主存命中率为p2;若所需数据字不在主存中,则访问主存未命中、将包含所需数据字的磁盘数据块装入主存共需
已知一个带有表头结点的单链表,结点结构为:假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。要求:根据设
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:如果Cache为8行,主存16块,分别采用三种方式映射主存的第9块
写出单总线结构计算机中指令M()VER1,R2(含义是将寄存器R1中内容写入寄存器R2中)的操作步骤。
主机H通过快速以太网连接到某网络中,H与服务器S使用TCP通信时,在H上捕获的其中2个IP分组如表7—3(a)所列: 请回答下列问题。 (1)表7—3(a)中的IP分组中,是应用层哪种协议?主机H和服务器的IP地址分别是多少? (2)假如
随机试题
患者女,32岁,剖宫产后,出现右小腿腓肠肌疼痛,小腿肿胀,腓肠肌压痛明显。
义齿就位困难的原因不可能是
贾思勰撰写的()是我国古代农业科学技术的总结性成果,也是现存最早、最完整的中国古代农学著作。
公安派出所民警小王、老陈接到钱某报警,到现场经过调查,了解到因钱某长期拖欠房租,房主叶某让钱某搬离,双方有一些口角,之后发生拉扯,钱某手臂上有一小处淤青,叶某出示了租房合同,钱某无异议,但提出有些条款不合理,双方请民警主持公道。下列关于民警处理警情正确的说
下列各项不属于刑事侦查工作的主要任务的是()
登门槛效应,是指一个人一旦接受了他人的一个微不足道的要求,为了避免认知上的不协调,或想给他人以前后一致的印象,就有可能接受更大的要求。根据上述定义,下列能够体现登门槛效应的是()。
简述直面现实的经济学分析方法。
“政府的隐含担保”是引发下列哪一种类型的货币危机的真正原因?()
[*]
ThepeoplewhorunFacebookarefuriousaboutanewmoviethatdepictstheexistenceofFace-book.They’reupsetbecausemuchof
最新回复
(
0
)