首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2019-12-10
60
问题
设一棵二叉树是由森林转换而来的,若森林中有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
学硕统考专业
相关试题推荐
在相隔400KM的两地间通过电缆以4800b/s的速率传送3000比特长的数据包,从开始发送到接收完数据需要的时间是()。
下面对计算机网络体系结构中协议所做的描述,错误的是()。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类1P地址。(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所
一台主机要解析www.abc.edu.cn的IP地址,如果这台主机配置的域名服务器为202.120.66.68,因特网顶级域名服务器为11.2.8.6,而存储www.abc.edu.cn与其IP地址对应关系的域名服务器为202.113.16.10,那么这台
某一个计算机系统采用虚拟页式存储管理方式,当前在处理机上执行的某一个进程的页表如下所示,所有的数字均为十进制,每一项的起始编号是0,并且所有的地址均按字节计址,每页的大小为1024字节。(1)计算下列逻辑地址转换为物理地址,并说明为什么?07
在某计算机中采用了多级存储体系,设计有cache,主存和磁盘,假设访问cache一个字需要花费10ns,若该字不在cache中但是存在在主存中,那么需要100ns载入cache,然后重新开始定位。若该字既不在cache中,也不在主存中,那么需要10ms的时
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
计算机网络分为广域网、城域网和局域网,其划分的主要依据是()。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离1w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
若视频图像每帧的数据量为6.4MB,帧速率为30帧/秒,则显示10秒的视频信息,其原始数据量是()。
随机试题
某有限责任公司因资不抵债而打算申请破产清算,就此事咨询李律师,李律师的说法哪些是错误的?()
土地使用者应当在签订土地使用权出让合同后()内支付全部土地使用权出让金。
某市卷烟厂2006年5月发生下列业务:(1)从农民手中收购烟叶10吨,收购凭证上注明的收购额100000元,验收后送某镇烟丝加工厂加工成烟丝,向运输公司支付运费烟叶500元;(2)烟丝厂将10吨烟叶加工成10吨烟丝,收取加工费3000元,辅
鲜活商品的储藏应设法杜绝它们的呼吸,已达到减少商品损耗、延长储藏时间的目的。
为了了解孩子对老师的评价,预先设计了两个问题“你最喜欢哪位老师?你为什么喜欢他?”这是半结构式访谈。()
超额翻译
m转化为利润是由于把m看成是
阅读下列说明和图。[说明]某公司欲开发招聘系统以提高招聘效率,其主要功能如下:(1)接受申请验证应聘者所提供的自身信息是否完整,是否说明了应聘职位,受理验证合格的申请,给应聘者发送致谢信息。(2)评估应聘者根
Peoplegotoseefilmsthere.PeoplebuyMealsandeathere.
由于算盘操作方便、简单易学,因此在中国被广泛使用。
最新回复
(
0
)