资源简介

浙教版（2019）选修一4.2二叉数的基本操作同步练习
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．某二叉树的中序遍历序列为DEBAFCGH，后序遍历序列为EDBFHGCA，则该二叉树的前序遍历序列为（ ）
A．ABDECGHF B．ABCDEFGH C．ABCDFGEH D．ABDECFGH
2．有一棵8个节点的二叉树，下列说法正确的是（ ）
A．叶子节点可能为4个 B．第3层最多6个节点 C．度为1的节点最多4个 D．该树的层数可能为3层
3．若一棵二叉树的中序遍历序列为ABCDE，则该二叉树不可能是（ ）
A． B．
C． D．
4．一个数学表达式可以用一棵表达式树来表示，而一棵二叉树可以用一维数组表示。有一棵表达式树用一维数组表示如下。下列有关该表达式树的说法正确的是（ ）
0 1 2 3 4 5 6 7 8
'/' '_' '4' '*' '8' '4' '6'
A．该表达式树是一棵完全二叉树 B．该表达式树的左右子树深度相差为1
C．该表达式树的叶子结点有4 D．该表达式树中序遍历的结果为4*6/8-4
5．某二叉树如图所示，下列说法正确的是（ ）
A．若补全成高度为5的满二叉树则需增加24个节点
B．该树的度和深度分别为2和3
C．该二叉树中序遍历的结果为DBEAGCF
D．节点D、F都是节点B的孩子节点
6．某完全二叉树的后序遍历为EBAGDC，则下列说法正确的是（ ）
A．该树的深度为4 B．该树有2个叶子节点
C．该树的节点B、G是兄弟节点 D．删除节点E后，该树的前序遍历为CABDG
7．有如下Python程序段:
def search(x):
ans=""
if a[2 *x]!="":
ans= ans+search(2 *x)
if a[2*x+1]!="":
ans= ans+search(2*x+1)
ans= ans+a[x]
return ans
a=["" for i in range(32)]
a[1]="A";a[2]="B";a[3]="C";a[4]="D";a[7]="E";a[9]="F"
print(search(1))
运行该程序段后，输出的结果是（ ）
A．FDBECA B．ACEBDF C．ABCDEF D．FEDCBA
8．某最优二叉树如下图所示。
则该二叉树的带权路径长度之和为（ ）
A．74 B．104 C．126 D．178
9．一棵二叉树的数组形式存储如下表所示。
数组下标 0 1 2 3 4 5 6 7 8 9 10 11
数组元素 a b c d e f g
关于该二叉树，下列说法错误的是（ ）
A．该二叉树的深度为4 B．该二叉树中共有3个叶节点
C．该二叉树的前序遍历序列为abdcefg D．g节点的父节点是e
10．已知6个节点的二叉树的先序遍历是abdcef，中序遍历是dbaecf，则该二叉树的后序遍历为（ ）
A．dbaefc B．dbacef C．dbefca D．bdefca
11．完全二叉树的节点个数为4*N+3，则它的叶子节点个数为（ ）
A．2*N B．2*N-1 C．2*N+1 D．2*N+2
12．完全二叉树的节点个数为13，则它的叶子节点个数为（ ）
A．9 B．8 C．7 D．6
13．满二叉树的叶子节点个数为N，则它的节点总数为（ ）
A．N B．2N C．2N-1 D．2N-1
14．一个高度为h的二叉树最少节点数为（ ）
A．2h+1 B．2h-1 C．h D．2h-1
15．表达式(3+5)*4-8/2的后缀表达式为（ ）
A．3 5 + 4 * - 8 2 / B．3 5 + 4 * 8 - 2 / C．3 5 + 4 * 8 2 - / D．3 5 + 4 * 8 2 / -
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．D
【详解】本题考查二叉树遍历。中序遍历序列为DEBAFCGH，后序遍历序列为EDBFHGCA，可还原二叉树的形状。
最终二叉树的前序遍历为ABDECFGH，选项D为正确答案。
2．A
【详解】本题考查数据结构二叉树相关内容。A选项，叶子节点可能为4个，选项说法正确。B选项，依据二叉树性质，第三层节点数最多为：23-1=4，选项说法错误。C选项，度为1的节点最多7个（该二叉树共8层，每层1个节点，度为1的有7个），选项说法错误。D选项，该树的层数不可能为3层（3层二叉树最多有7个节点），选项说法错误。
3．B
【详解】本题考查二叉树的遍历。选项B对应的中序遍历是ABCED。故选B。
4．C
【详解】本题考查二叉树相关内容。由该二叉树的一维数组表示可知，该二叉树结构如图所示：。A选项，该二叉树不是完全二叉树，选项错误。B选项，该表达式树的左右子树深度相差为2，选项错误。C选项，该表达式树的叶子结点有4个，选项正确。D选项，该表达式树中序遍历的结果为4*6-8/4，选项错误。故本题答案是C选项。
5．A
【详解】本题考查二叉树相关内容。A选项，依据二叉树性质，高度为5的满二叉树有25-1=31个节点，现有7个节点，需要增加24个节点，选项正确。B选项，该二叉树的度为2，深度为4，选项错误。C选项，二叉树中序遍历规则是：若二叉树非空，则先遍历二叉树的左子树，再遍历根节点，最后遍历右子树，该二叉树的中序遍历序列是：DBEGACF，选项错误。D选项，D是B的孩子节点，F是C的孩子节点，选项错误。故本题答案是A选项。
6．D
【详解】本题考查二叉树相关内容。由于是完全二叉树，该树的模型已经确定，根据后序遍历可知该二叉树为
，该树深度为3，有3个叶子节点，节点B、G是堂兄弟节点，不是兄弟节点，ABC选项说法错误。删除节点E后，该树的前序遍历为CABDG，D选项说法正确。故本题答案是D选项。
7．A
【详解】本题考查的是递归及树的遍历。本题是将递归算法和树的遍历进行了结合，search(1)就是从根节点出发， 首先查看有无左子树，若有继续查看还有没有左子树，若有则继续，直到无左子树的时候再查看右子树的情况....故此判断该算法说的是树的遍历，而且是后序遍历的情况，由此画出该二叉树如下：
故选A。
8．C
【详解】本题考查二叉树相关内容。叶子节点带权路径长度的计算方法为：路径长度(根节点到叶子节点的边数)*叶子节点的权值。该二叉树的带权路径长度之和=WPL=(3+4)*4+8*3+(15+9+13)*2=126，故本题答案为C选项。
9．C
【详解】本题考查二叉树相关内容。该二叉树如下图所示：
该二叉树的前序遍历序列为abdcegf，因此C选项错误，故本题答案为C选项。
10．C
【详解】本题考查二叉树相关内容。根据二叉树的先序遍历“abdcef”，可知树根是a，中序遍历“dbaecf”中db为左子树序列，ecf为右子树序列，节点b又是节点d父节点，同理可得，e是c节点的左孩子节点，f是c节点的右孩子节点，画出二叉树如下图所示：
该二叉树的后序遍历为dbefca，故本题答案为C选项。
11．D
【详解】本题考查二叉树相关内容。完全二叉树的节点个数为4*N+3，则最后一个叶子节点的编号为4*N+3，其父节点的编号为2*N+1，即度为2的节点数为2*N+1，因此它的叶子节点个数为4*N+3-(2*N+1)=2*N+2，故本题答案为D选项。
12．B
【详解】本题考查二叉树相关内容。完全二叉树的节点个数为13，则该二叉树的高度为4，最下面一层有6个节点，因此叶子节点个数为8个，故本题答案为B选项。
13．C
【详解】本题考查二叉树相关内容。根据二叉树的性质，叶子节点比度为2的节点多1个，即n0=n2+1。满二叉树中，只有度为0或度为2的节点，而该满二叉树共有叶子数为N，则度为2的节点数n2=N-1，因此节点总数为2N-1，故本题答案为C选项。
14．C
【详解】本题考查二叉树相关内容。高度为h的最少节点数的二叉树如下图所示。
它共有h个节点，故本题答案为C选项。
15．D
【详解】本题考查二叉树相关内容。将原式按二叉树展开如下图所示:
然后后序遍历可得后缀表达式，因此后缀表达式为“3 5 + 4 * 8 2 / -”，故本题答案为D选项。
答案第1页，共2页
答案第1页，共2页

展开更多......

收起↑