一棵二叉树的前序遍历序列为1234567，则它的中序遍历序列不可能为( )。 Ⅰ．3124567 Ⅱ．1234567 Ⅲ．4135627 Ⅳ．1436572

admin2014-12-08 42

问题一棵二叉树的前序遍历序列为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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

一棵二叉树的前序遍历序列为1234567，则它的中序遍历序列不可能为( )。 Ⅰ．3124567 Ⅱ．1234567 Ⅲ．4135627 Ⅳ．1436572

计算机408

学硕统考专业

“时方镇缺守帅，稍命文臣权之……又置转运使、通判，为之条禁，文薄渐为精密，由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。

下列不属于凯末尔主义内容的是()。

人类历史上第一次完成从西欧绕非洲到东方航行的航海家是()。

下列不是苏俄实行战时共产主义政策原因的是()。

列宁在()中系统地阐明了马克思主义的国家学说。

关于大陆人民大规模达到台湾的第一次明确的记录出现在()。

清朝，各地督抚将重大问题径寄军机处交皇帝审批，称为()。

下列各种情况中，应采用异步通信方式的是()。

在TELNET协议中，用户发送的命令采用TCP传输到服务器，在TCP的数据包中，需要把()符号位置移位，从而使服务器尽快响应命令。

下列所示不是信号量能实现的功能是()。

男性，45岁。间断腹泻5年，加重3个月。大便每日4～5次，脓血便，纳差，体重减轻6kg。口服左氧氟沙星治疗2周后复查粪便常规：白细胞、红细胞满视野，隐血(+)。血常规：Hb100g／L，WBC4．5×109／L，PLT215×109／L。最有可能的诊

王某与李某合著一部小说《难忘××》，该作品于1988年3月出版。王某于2000年5月15日去世，李某于2015年4月30日去世。该作品的财产权保护期截至()。

关于女用避孕药的描述正确的是

关于难免流产哪项是错误的

(2009年)数字信号B=1时，图8—72所示的两种基本门的输出分别为()。

单式记账法是指对每一项经济业务的发生只在一个账户中进行记录的记账方法。()(3．1)

中国园林发展中的成熟阶段是()。

根据《税收征收管理法》的规定，税务机关不可采取的税款征收措施是()。

"Deadpool",whichsofarhastakenmorethan$500mincinemasworldwide,isanatypicalblockbuster,afoul-mouthedanti-herofi