资源简介

浙教版（2019）选修一4.1数与二叉数同步练习
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．某完全二叉树共有300个节点，该二叉树的高度是（ ）
A．8 B．9 C．10 D．11
2．某二叉树的前序遍历结果为ABC，若该二叉树不是满二叉树，则其后序遍历结果为（ ）
A．ABC B．BCA C．CBA D．CAB
3．某二叉树用一维数组存储结构如下表所示：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H
下列有关该二叉树的说法正确的是（ ）
A．该二叉树是完全二叉树 B．度为2的节点有3个
C．前序遍历为A-B-D-F-G-C-H-E D．节点C是节点E的父节点
4．某数学表达式可以表示成二叉树，如图所示。则下列说法正确的是（ ）
A．该二叉树根节点的左子树高度为 4
B．该表达式树中存在度为 1 的节点
C．任意表达式树中叶节点的数量比内部节点多一个
D．通过后序遍历可求该表达式的逆波兰式为 63-2/572+8/*+
5．某完全二叉树，中序遍历结果为“甲乙丙丁”，则后序遍历结果是（ ）
A．甲乙丁丙 B．丙乙甲丁 C．甲丁丙乙 D．乙丁丙甲
6．某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是（ ）
A．前序遍历序列为DBACGFE B．节点G为节点E的父节点 C．该二叉树有两个叶子节点 D．节点A与节点F为同一层
7．已知一棵二叉树的后序遍历为CDAFEBG，中序遍历为CADGFBE，则该二叉树的前序遍历序列为（ ）
A．GACBDFE B．GACDBFE C．GACDBEF D．GCADBEF
8．如图所示的二叉树，下列说法正确的是（ ）
A．该二叉树是一个完全二叉树 B．该二叉树的深度为4，节点D的度为2
C．该二叉树的叶子节点数比非叶子节点数少一个 D．该二叉树中A是D和E的父节点
9．有如图所示的树。下列说法正确的是（ ）
A．该树中共有3个叶子节点 B．该树的度和深度均为3
C．该树中度为2的子节点有1个，度为1的子节点有2个 D．节点e是节点f的兄弟节点
10．一棵二叉树的高度为h，所有节点的度为0或2，则此二叉树的节点数最少为（ ）
A．2h-1 B．2h+1 C．h+1 D．2h-1
11．对于四则运算表达式，可以用二叉树来表示，比如a+b，可以以运算符为父节点,操作数为孩子节点建立相应的二叉树，如图所示。对于表达式（a+b）*c-（d+e）/f-g,下列说法正确的是（ ）
A．该表达式对应二叉树的前序遍历序列为-*+abc-/+defg
B．该表达式对应二叉树的后序遍历序列为ab+c*de+f/-g-
C．该表达式对应二叉树的深度为4
D．该表达式对应的二叉树为完全二叉树
12．有一棵完全二叉树具有100个结点，下列说法正确的是（ ）
A．树的深度为8 B．有1个节点只有非空左子树
C．此完全二叉树有49个叶子结点 D．有50个度为2的节点
13．已知一棵二叉树的中序遍历序列为9–4+2*3/1+4，后序遍历序列为94–23*+14+/，以下说法正确的是（ ）
A．这棵树叶子结点比非叶子结点数多1 B．这是一棵满二叉树
C．其前序遍历序列为/+-94*231+4 D．这棵树有5层
14．一棵有n(n>0）个结点的二叉树，其结点为0度或2度，则此树的最大高度是（ ）
A．（n+1）//2 B．n//2 C．（n-1）//2 D． log2n+1
15．现有一棵二叉树，度为2的节点有10个，度为1的节点有5个，则这棵二叉树共有节点数为（ ）
A．25 B．26 C．27 D．不确定
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．B
【详解】本题主要考查二叉树的描述。完全二叉树，高度是[log2N]+1，以2为底的对数取整后+1。故该完全二叉树的高度为h=log2300 + 1=9。故本题应选B。
2．C
【详解】本题考查的是二叉树。前序遍历结果为ABC，不是满二叉树，故其树可能为：
其后序遍历结果都为：CBA。故本题应选C。
3．D
【详解】本题考查二叉树相关内容。由数组可知二叉树如图：
该二叉树不是完全二叉树；度为2的节点有2个；前序遍历为：ABDFGCEH；节点C是节点E的父节点。故本题应选D。
4．D
【详解】本题考查二叉树相关内容。A选项，该二叉树根节点的左子树高度为3，选项错误。B选项，该表达式树不中存在度为1的节点，选项错误。C选项，内部节点是除叶子节点和根节点之外的所有节点，如图所示，该表达式树中叶节点的数量为7，内部节点个数为5，选项错误。D选项，一个二叉树后序遍历的结果就是后缀表达式（逆波兰式），通过后序遍历可求该表达式的逆波兰式为 63-2/572+8/*+，选项正确。故本题答案是D选项。
5．A
【详解】本题考查的是二叉树的遍历。依据题意可知二叉树如下：
故后序遍历结果是：甲乙丁丙。本题应选A。
6．B
【详解】本题考查的是二叉树。依据题意可画出如下的数：
由图可知，前序遍历序列为DBACGEF，节点G为节点E的父节点，该二叉树有3个叶子节点，节点A与节点F不在同一层。故本题应选B。
7．B
【详解】本题考查的是二叉树的遍历。依据题意可知该二叉树如下：
故该二叉树的前序遍历序列为：GACDBFE。选项B正确。
8．C
【详解】本题考查的是二叉树。完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1)) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉数。图中所示的二叉树不是一个完全二叉树；该二叉树的深度为4，节点D的度为1；该二叉树的叶子节点数（3）比非叶子节点数（4）少一个；A是B和C的父节点。故本题应选C。
9．C
【详解】本题考查树。该树中共有4个叶子节点，分别是h、e、f、g，因此A选项错误；该树的度为3，深度为4，因此B选项错误；由于节点e和节点f的父节点不是同一个，因此它们不是兄弟节点，因此D选项错误；该树中度为2的子节点有1个(b节点)，度为1的子节点有2个(d节点和c节点)，C选项正确。故答案为：C。
10．A
【详解】本题考查二叉树。符合题意的最少节点的二叉树如下图所示:
除根节点所在层节点数为1外，其他每层均为2个节点，因此节点数为2h-1个，故答案为A。
11．B
【详解】本题考查二叉树。A选项错误。该表达式对应二叉树的前序遍历序列应为--*+abc/+defg，前序遍历是先访问父节点，再访问左子树，最后访问右子树。B选项正确。该表达式对应二叉树的后序遍历序列为ab+cde+f/-g-。C选项错误。该表达式对应的二叉树的深度为5，不是4。根节点到叶子节点的最长路径为5。D选项错误。该表达式对应的二叉树不是完全二叉树。完全二叉树是指除了最后一层外，其他各层的节点数都达到最大值，并且最后一层的节点都靠左对齐。故答案为：B。
12．B
【详解】本题考查二叉树。A选项错误，树的深度为7时，27-1就有127个节点，树的深度为7的话，就有127个节点了，深度不可能为8。B选项正确，(100-n1-1)/2,n1要么是0要么是1，总结点数为100，n1有1个，所以正确。C选项错误，叶子节点有 (100-n1-1)/2，n1的个数为1，所以叶子节点为50个。D选项错误，根据以上总结n0=50，n1=1，n2=49个。故答案为：B。
13．A
【详解】
本题考查二叉树。以二叉树中序、后序遍历序列构建二叉树，如下图所示，A选项，叶子结点5，非叶子结点4，选项正确。B选项，该二叉树为完全二叉树，不是满二叉树，选项错误。C选项，前序遍历结果为/+94*23+14，选项错误。D选项，该二叉树有4层，选项错误。故本题答案是A选项。
14．A
【详解】本题考查二叉树相关内容。二叉树由根节点和其子节点组成，每个节点的度有如下可能：0，1，2，根据题干，该二叉树的节点的都为0度或2度，即除根节点外，其每个节点都有一个兄弟节点。由于题目求的为该树的最大高度，即考虑极端情况下，每一层都只有一对兄弟节点，此时除根节点外，每一层都有两个节点，则除第一层外，节点数除2为除第一层外的层数。则假设根节点有一个兄弟节点后，则对2整除，则为层数。即(n+1)//2。故本题答案是A选项。
15．B
【详解】本题考查二叉树相关内容。二叉树中，总的节点个数=度为0的节点个数+度为1的节点个数+度为2的节点个数；其中，度为0的节点个数=度为2的节点个数+1；故总的节点个数=度为1的节点个数+度为2的节点个数*2+1=5+10*2+1=26，故本题答案是B选项。
答案第1页，共2页
答案第1页，共2页

展开更多......

收起↑