首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
设一棵二叉树是由森林转换而来的,若森林中有n个非终端结点,则二叉树中无右孩子的结点个数为( )。
admin
2019-12-10
28
问题
设一棵二叉树是由森林转换而来的,若森林中有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
学硕统考专业
相关试题推荐
网络拓扑结构如下图所示,与C相连接的节点B,E,D的权值分别是6,5,3。如果C收到的三张矢量表分别为:试根据距离矢量路由算法给出C所构造的路由表,并给出计算过程,路由表结构如下表所示。
快速排序算法中,如何选取一个界值(又称为轴元素),影响着快速排序的效率,而且界值也并不一定是被排序序列中的一个元素。例如,我们可以用被排序序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速排序方法。
什么是单重分组和双重分组跳跃进位链?一个按3,5,3,5分组的双重分组跳跃进位链(最低位为第0位),试问大组中产生的是哪几位进位?与4,4,4,4分组的双重分组跳跃进位链相比,试问产生全部进位的时间是否一致?为什么?
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。结合(1)的微指令格式,计算该
某计算机系统的内存储器由(2ache和主存构成,Cache的存取周期为45纳秒,主存的存取周期为200纳秒。已知在一段给定的时间内,CPU共访问内存4500次,其中340次访问主存。问:如果Cache为8行,主存16块,分别采用三种方式映射主存的第9块
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
设一段正文由字符集{A,B,C,D,E,F}中的字母组成,这6个字母在正文中出现的次数分别为{12,18,26,6,4,34}。(1)为这6个编码设计哈夫曼编码。(2)设每个字节由8位二进制位组成,试计算按哈夫曼编码压缩存储这段正文共需多少个字节。(3)若
已知AOE网中顶点v1,v2,v3,…v7分别表示7个时间,有向线段a1,a2,a3,…a10。分别表示10个活动,线段旁的数值表示每个活动花费的天数,如图10-1所示。请填写表10-1、表10-2两个表格,并用顶点序列表示出关键路径,给出关键活动。
某请求分页系统的局部页面置换策略如下:系统从0时刻开始扫描,每隔36个时间滴答扫描一轮工作集(扫描时间忽略不计),本轮没有被访问过的页框将被系统回收,并放人到空闲页框链尾,其中内容在下一次被分配之前不被清空。当发生缺页时,如果该页曾被使
某公司网络拓扑图如下图所示,路由器R1通过接口E1、E2分别连接局域网1、局域网2,通过接口L0连接路由器R2,并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1;R2的L0接口的IP地址是202.118.2.2,L1
随机试题
按我国现行规定,商业银行不得向其董事、监事、管理人员及其亲属,以及其投资或担任高级管理职务的公司、企业等发放()。
因施工人的原因致使工程质量不符合约定的,发包人有权()
注射用油的质量要求中
下列各项中,属于应用软件的是()。
根据《行政强制法》的规定,下列关于行政强制执行的说法中,正确的是()。(2013年)
强调通过加强资产分散化、抵押、项目调查等手段来提高商业银行的安全度的风险管理阶段的是()。
以实现稳定经济波动的目的,政府有意识地从当时经济状态的反方向调节经济变动的财政政策称为()。
关于短期成本曲线的说法,正确的有()。
打开查询设计器建立查询的命令是
Inaword,combinedwithmoderateexerciseandhealthfulhabits,eatingtherightfoodscanhelpimproveyourimmunesystemand
最新回复
(
0
)