高效作业14 第14课 二叉树的基本操作与抽象数据类型-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参(浙教版2019)

| 11页
| 135人阅读
| 2人下载
浙江良品图书有限公司
进店逛逛

新版页眉

学科网 zxxk.com学科网 zxxk.com

高效作业14[第14课 二叉树的基本操作与抽象数据类型](见学生用书P223)

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

【A级 新教材落实与巩固】

1.若一棵二叉树的中序遍历序列为BIGDHAECF,后序遍历序列为IGHDBEFCA,则该二叉树的前序遍历序列为( D )

A.ABCDEFGHI     B.ABDGHICEF

C.ABDHGICEF    D.ABDGIHCEF

【解析】 “A”是根节点,那么“ECF”在右子树,选项A错误;B、C、D 三个选项中,只有“GHI”的位置是不一样的。左子树的根节是“B”,那么再根据中序的“IGDH”,后序的“IGHD”,“D”是这个子树的根节点。“H”在右子树,前序遍历一定在最后。选项D正确。

2. 已知二叉树中序遍历序列为BEDAFHCIG,前序遍历序列为ABDECFHGI,它的后序遍历序列为( D )

A.BDEFHCIGA    B.IGHFEDCBA

C.EDBFHIGCA    D.EDBHFIGCA

【解析】 根据二叉树的前序与中序遍历序列,可画出二叉树如下图,再写出后序遍历序列是EDBHFIGCA。选项D正确。

3. 某二叉树的后序遍历序列为F??CAD,中序遍历序列为FBDEAC,则其前序遍历序列为( B )

A. DBAFEC

B. DBFAEC

C. DEFABC

D.DEAFBC

【解析】 通过后序遍历序列可知此二叉树的根节点为D,再通过中序遍历序列可知,F、B为左子树的节点,A、C、E为右子树的节点;再结合后序遍历序列可知, 左子树中,F 为左或右节点,B为根节点; 右子树中,A为根节点,E为左节点,C为右节点。由此可知,前序遍历序列为DBFAEC。选项B正确。

4.现有一棵二叉树的前序遍历序列为CBADE、中序遍历序列为BACED,则该二叉树的后序遍历序列为( A )

A.ABEDC    B.CBEDA

C.ABDEC    D.CBDEA

【解析】 通过前序遍历序列为CBADE、中序遍历序列为BACED,可以确定二叉树的根为C,左子树为BA,右子树为ED。研究其左子树BA,前序遍历序列为BA、中序遍历序page number 0

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

列为BA;研究其右子树ED,前序遍历序列为DE、中序遍历序列为ED。确定二叉树的形态如图所示,故该二叉树的后序遍历序列为ABEDC,选项A正确。

5.已知一棵二叉树的后序遍历序列为IHDBEFCA,中序遍历序列是DIHBAECF,则该二叉树的前序遍历序列为( C )

A. ABDIHCFE    B. ABDIHCEF

C. ABDHICEF    D.ABDHICFE

【解析】 后序遍历是先遍历左、右节点再遍历根节点,中序遍历是先遍历左节点再遍历根节点最后遍历右节点,结合后序遍历序列与中序遍历序列,可画出二叉树如图所示:

所以前序遍历序列为ABDHICEF,选项C正确。

6.现有一棵二叉树的前序遍历序列为ABCDEF,中序遍历序列为BCADFE,则该二叉树的后序遍历序列为( A )

A.CBFEDA    B.BCFEDA

C.CBDFEA    D.BCEFDA

【解析】 根据前序遍历和中序遍历的规则画出二叉树,过程如下:前序遍历的第一个元素“A”为根节点,根据节点“A”在中序遍历的位置确定:“BC”是节点“A”的左子树,“DEF”为节点“A”的右子树。“BC”中,根据前序遍历确定节点“B”为根节点,继而根据中序遍历确定节点“C”是节点“B”的右子树。“DEF”中,根据前序遍历确定节点“D”为根节点,继而根据中序遍历确定“EF”是节点“D”的右子树。“DEF”中,根据前序遍历确定节点“E”为根节点,继而根据中序遍历确定节点“F”是节点“D”的右子树。根据画出的二叉树可以得到后续遍历结果为CBFEDA。选项A正确。

7.2023·诸暨中学检测某二叉树的结构如下, 下列说法正确的是( D )

page number 1

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

A. 该二叉树是一棵完全二叉树

B. 该二叉树有3个叶子节点

C. 该二叉树的后序遍历结果是DBEFCA

D.该二叉树的建立可以使用数组也可以用链表数据结构

【解析】 选项A,完全二叉树指的是:从根节点开始,按自上而下、从左往右的顺序生成节点的二叉树, 而题中所给的二叉树不符合完全二叉树的生成规律, 选项错误。选项B,叶子节点指的是树中度为0的节点, 该二叉树中, 只有两个叶子节点D和F, 选项错误。选项C,后序遍历是指在遍历二叉树的过程中,按“ 左右根”的顺序对树中节点进行访问,故该二叉树的后序遍历序列为:DBFECA, 选项错误。选项D,二叉树的建立既可以使用数组也可以使用链表实现, 选项正确。

8.已知一棵二叉树的前序遍历序列为:ABDCE,后序遍历序列为:DBECA,则下列关于该二叉树的中序遍历序列说法中,正确的是( B )

A. 能唯一确定,中序遍历序列为:BDAEC

B. 不能唯一确定,中序遍历序列可能为:BDAEC

C. 能唯一确定,中序遍历序列为:DCBAE

D.不能唯一确定,中序遍历序列可能为:DCBAE

【解析】 二叉树遍历中只有前序和后续不能唯一确定一棵二叉树, 故排除选项A、C。选项B,根据前序和中序遍历可以画出二叉树如图,其后序遍历序列为DBECA,满足条件,选项正确。

9. 2023·柯桥中学检测已知一棵二叉树的前序遍历序列为FGDAETMH,中序遍历序列为DGEAFTHM,则该二叉树的后序遍历序列为( B )

A.DAEGHMTF    B.DEAGHMTF

C.DEAGHMFT    D.DAEGHMFT

【解析】 前序遍历的遍历次序为“根左右”,中序遍历的遍历次序为“左根右”,由此可得出二叉树如下图所示:

结合二叉树后序遍历的次序为“左右根”,故该二叉树后序遍历的结果为: DEAGHMTF。选项B正确。

10.对于如图所示的二叉树,下列说法正确的是( D )

page number 2

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。