首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2019-12-10
58
问题
设一棵二叉树是由森林转换而来的,若森林中有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
学硕统考专业
相关试题推荐
设有一个含200个表项的散列表,用线性探查法解决冲突,按关键码查询时找到一个表项的平均探查次数不超过1.5,则散列表项应能够至少容纳的表项的数目是()。
地址总线A15~A0,其中A0是最低位。存储器地址空间为3000H~67FFH。其中3000H~4FFFH为RoM区,选用EPR()M芯片(4K×2);5000H~67FFH为RAM区,选用RAM芯片(2K×4)。(1)组成该存储器需用多少块EP
一个快速以太网交换机的端口速率为100Mbps,若该端口可以支持全双工传输数据,那么该端口实际的传输带宽是()。
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
某微机的寻址范围为64KB,其存储器选择器信号为M,接有8片8KB的存储器,试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片RAM的寻址范围。(3)如果运行时发现不论往哪片存储器存放8KB数据,以4000H起始地址的存
为了防止各种意外可能破坏文件,文件系统保护文件的方法可以是()。
利用逐点插入建立序列(50,72,43,85,75,20,35,45.,65,30)对应的二叉排序树以后,要查找元素30要进行元素间的比较次数是()。
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:Cache一主存系统的效率是多少?
磁盘D1每道32扇区,每扇区lK,磁盘D2每道8扇区,每扇区4K。文件F1和F2内容相同,大小为100K。F1均匀分布在D1,F2均匀分布在D2。磁盘D1、D2的平均寻道时间均为10毫秒,旋转延迟5毫秒,传输时间忽略不计。顺序读完F1、F2的时间分别为(
随机试题
某企业2008年销售收入净额为250万元,销售毛利率为20%,年末流动资产90万元,年初流动资产110万元,则该公司流动资产周转率为多少?
可摘局部义齿三种支持形式中,哪一项是错误的
债券筹资的特点不包括( )。
下列关于卖出看涨期权的损益(不计交易费用)的说法,正确的有()。
6月10日,某县国税局在对甲企业进行检查过程中发现甲企业有逃税行为,于6月15日向甲企业送达《税务处理决定书》要求甲企业补缴税款100万元,并缴纳相应的滞纳金;甲企业不服拟申请行政复议,遂于6月20日申请以自己的厂房设定抵押担保缴纳应补缴的税款和滞纳金。下
(),标志着金融期货交易的开始。
()是交易双方以当时外汇市场的价格成交,并在成交后的两个营业日内办理有关货币收付交割的外汇交易。
不动产登记的登记机构办理所在地为()。
“昼出耘田夜绩麻,村庄儿女各当家。童孙未解供耕织,也傍桑阴学种瓜。”这首古诗反映了古代中国经济的生产方式是()。
WhyhascrimeintheU.S.declinedSOdramaticallysincethe1990s?Economistsandsociologistshaveofferedabountyofreas
最新回复
(
0
)