首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一棵二叉树的前序遍历序列为1234567,则它的中序遍历序列不可能为( )。 Ⅰ.3124567 Ⅱ.1234567 Ⅲ.4135627 Ⅳ.1436572
一棵二叉树的前序遍历序列为1234567,则它的中序遍历序列不可能为( )。 Ⅰ.3124567 Ⅱ.1234567 Ⅲ.4135627 Ⅳ.1436572
admin
2014-12-08
46
问题
一棵二叉树的前序遍历序列为1234567,则它的中序遍历序列不可能为( )。
Ⅰ.3124567 Ⅱ.1234567 Ⅲ.4135627 Ⅳ.1436572
选项
A、仅Ⅰ、Ⅱ
B、仅Ⅱ、Ⅲ
C、仅Ⅰ、Ⅲ
D、仅Ⅰ、Ⅲ、Ⅳ
答案
C
解析
由二叉树的前序遍历为1234567可知,该二叉树的根为结点1,并且2为1的孩子结点。
Ⅰ:假如3124567是该二叉树的中序遍历,那么3必然是1的左孩子,前序遍历的序列一定是13,而前序遍历并没有以13开头,所以Ⅰ不可能是中序序列。
Ⅱ:首先需要来证明一个知识点:什么情况下,前序遍历和中序遍历是一样的。前序遍历是tlr(根左右),中序遍历是ltr(左根右),下面就从tlr和ltr着手。
(1)当没有左子树时,前序遍历变成了tr,中序遍历也变成了tr,故此种情况F前序遍历和中序遍历一样。 (2)当没有右子树时,前序遍历变成tl,中序遍历却变成了lt,故此种情况下前序遍历和中序遍历不一样。
综上分析,只要该二叉树没有左子树,则都能够满足前序遍历和中序遍历是一样的,故Ⅱ是可能的。
Ⅲ:和Ⅰ的情况一样的分析,前序应该是以14开头,所以不可能是中序序列。
Ⅳ:构造的二叉树如图8-6所示。
因此,Ⅰ、Ⅲ不可能。
总结:以下3种情况可以唯一确定一棵二叉树。 ①先序序列和中序序列。 ②后序序列和中序序列。 ③层次序列和中序序列(重点,注意出题。)
转载请注明原文地址:https://kaotiyun.com/show/gdxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
义和团运动排外思想产生的根本原因是()。
试述宋代理学产业的社会背景及主要内容。
巴黎和会上,英国既与法国联合抵制美国称霸世界,又与美国联合反对法国过分削弱德国的要求,英国这样做的目的是()。
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
已知某CPU有16根地址线、8根数据线,并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片:1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干,如下图所
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:转移指令的目标地址范围是多少?
随机试题
根据《反恐怖主义法》的规定,甲县公安机关在调查恐怖活动嫌疑时,对恐怖嫌疑人员黄某采取约束措施,下列说法错误的是()。
套利的经济学基础是()。
匹夫见辱,拔剑而起,挺身而斗,此不足为勇也。
设有某Internet用户,其POP主机域名是mail.hz.zj.cn,帐户名为zhangsan,则相应的E-mail地址是_______。
影响CT图像质量的因素包括
在悬臂浇筑混凝土斜拉桥的梁施工检测中,对于斜拉索锚具轴线与孔道轴线偏位的要求是()。
以下关于上市公司分红说法正确的有()。Ⅰ.公司发展阶段属成熟期且无重大资金支出安排的,进行利润分配时,现金分红在本次利润分配中所占比例最低应达到80%Ⅱ.公司发展阶段属成熟期且有重大资金支出安排的,进行利润分配时,现金分红在本次
刑讯逼供罪只能由()构成。
窗体上有一个名称为Command1的命令按钮,单击该按钮时所实现的功能是产生10个随机整数,然后从键盘输入一个整数,查找该数在数组中的位置。若找到,输出该数的位置;若没有找到,给出相应的提示。该命令按钮的单击事件过程如下:PrivateSubCo
下列数据结构中,属于非线性结构的是
最新回复
(
0
)