资源简介

专题四　检测卷
一、选择题(本大题共12小题,每小题2分,共24分。每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)
1.有如图所示的树。下列说法正确的是(　　)
A.该树中共有3个叶子节点
B.该树的度和深度均为3
C.该树中度为2的子节点有1个,度为1的子节点有2个
D.节点e是节点f的兄弟节点
2.如图所示,一个数学表达式可以用一棵表达式树来表示。关于该表达式树,下列描述正确的是(　　)
A.该表达式树不是一棵满二叉树
B.该表达式树中度为2的节点比叶子节点多一个
C.该表达式树的中序遍历序列为1 + 6 - 2 * 3
D.该表达式树的后序遍历序列为1 6 + - 2 3 *
3.一棵二叉树的高度为h,所有节点的度为0或2,则此二叉树的节点数最少为(　　)
A.2h-1 B.2h+1
C.h+1 D.2h-1
4.表达式(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 / -
5.包含5个节点的二叉树,其根节点的左右子树高度相同,且中序遍历结果是“甲乙丙丁戊”,那么其前序遍历结果不可能是(　　)
A.丙乙甲戊丁 B.丙乙甲丁戊
C.丙甲乙戊丁 D.丙乙丁甲戊
6.满二叉树的叶子节点个数为N,则它的节点总数为(　　)
A.N B.2N
C.2N-1 D.2N-1
7.完全二叉树的节点个数为13,则它的叶子节点个数为(　　)
A.9 B.8
C.7 D.6
8.完全二叉树的节点个数为4*N+3,则它的叶子节点个数为(　　)
A.2*N B.2*N-1
C.2*N+1 D.2*N+2
9.已知6个节点的二叉树的先序遍历是abdcef,中序遍历是dbaecf,则该二叉树的后序遍历为(　　)
A.dbaefc B.dbacef
C.dbefca D.bdefca
10.一棵二叉树的数组形式存储如下表所示。
数组下标 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
11.某非完全二叉树包含5个节点,中序遍历为ABCDE。该二叉树添加1个节点F后变成完全二叉树,以下对于该完全二叉树的说法正确的是(　　)
A.该二叉树的根节点可能为D
B.该二叉树的后序遍历可能为AFBEDC
C.节点B的父节点一定是A
D.该二叉树的深度为3,节点E在第二层
12.某最优二叉树如下图所示。
则该二叉树的带权路径长度WPL为(　　)
A.74 B.104
C.126 D.178
二、非选择题(本大题共4小题,其中第13小题12分,第14小题4分,第15小题5分,第16小题5分,共26分)
13.某二叉树如下图所示,请回答下列问题。
(1)该二叉树的深度为　　 　。(3分)
(2)写出该二叉树的前序遍历、中序遍历和后序遍历。
前序遍历序列为:　　　　　　　　　　　　;(3分)
中序遍历序列为:　　　　　　　　　　　　;(3分)
后序遍历序列为:　　　　　　　　　　　　。(3分)
14.请用数组来表示如下图所示的完全二叉树。(4分)
数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
数组元素
15.由a,b,c 3个不同的数字组成一个N位数,要求不出现两个a相邻,也不出现两个b相邻,这样的N位数的个数为AN,用AN-1和AN-2表示AN的关系式为:AN= 　　　　　　　　　　　　　　　　。
(5分)
16.设树T有17条边,12片树叶,4个4度内部节点,1个3度内部节点。则T的树根的度数为　　　　。(5分)
专题四　检测卷
一、选择题
1.C　解析:该树中共有4个叶子节点,分别是h、e、f、g,因此A选项错误;该树的度为3,深度为4,因此B选项错误;由于节点e和节点f的父节点不是同一个,因此它们不是兄弟节点,因此D选项错误;该树中度为2的子节点有1个(b节点),度为1的子节点有2个(d节点和c节点),因此答案为C。
2.C　解析:该表达式树是一棵满二叉树,因此A选项错误;该表达式树中度为2的节点比叶子节点少一个,因此B选项错误;该表达式树的后序遍历序列为1 6 + 2 3 * -,因此D选项错误;该表达式树的中序遍历序列为1 + 6 - 2 * 3,因此答案为C。
3.A　
4.D　解析:将原式按二叉树展开如下图所示:
然后后序遍历可得后缀表达式,因此后缀表达式为“3 5 + 4 * 8 2 / -”,故答案为D。
5.D　解析:本题主要考查二叉树相关概念与遍历。在二叉树中,三个节点的树高度至少是2,因此在5个节点的二叉树中,左右子树高度相同,只能是左右子树节点个数相同。即使不知道此性质也能根据“左右子树高度相同”的特点绘制出如图所示的二叉树。因此丙只能是根节点,左子树序列只能是“甲乙”或“乙甲”,右子树序列也只能是“丁戊”或“戊丁”。因此答案为D。
6.C　解析:根据二叉树的性质,叶子节点比度为2的节点多1个,即n0=n2+1。满二叉树中,只有度为0或度为2的节点,而该满二叉树共有叶子节点数为N,则度为2的节点数n2=N-1,因此节点总数为2N-1,答案为C。
7.C　解析:完全二叉树的节点个数为13,则该二叉树的高度为4,最下面一层有6个节点,因此叶子节点个数为7个,答案为C。
8.D　解析:完全二叉树的节点个数为4*N+3,则最后一个叶子节点的编号为4*N+3,其父节点的编号为2*N+1,即度为2的节点数为2*N+1,因此它的叶子节点个数为4*N+3-(2*N+1)=2*N+2,故答案为D。
9.C　解析:根据二叉树的先序遍历“abdcef”,可知树根是a,中序遍历“dbaecf”中db为左子树序列,ecf为右子树序列,节点b又是节点d父节点,同理可得,e是c节点的左孩子节点,f是c节点的右孩子节点,画出二叉树如下图所示:
该二叉树的后序遍历为dbefca,因此答案为C。
10.C　解析:该二叉树如下图所示:
该二叉树的前序遍历序列为abdcegf,因此C选项错误,故答案为C。
11.D　解析:
本题主要考查二叉树的相关知识。根据题目的描述可画出如图所示的二叉树。若要添加一个节点成为完全二叉树,该节点添加在节点B的右子树上即符合题意。根节点是C,因此A选项错误;该二叉树的后序遍历为AFBDEC,因此B选项错误;节点 B 的父节点为节点 C,因此C选项错误;该二叉树的深度为3,节点E在第二层,因此D选项正确,故答案为D。
12.C　解析:叶子节点带权路径长度的计算方法为:路径长度(根节点到叶子节点的边数)*叶子节点的权值。该二叉树的带权路径长度WPL=(3+4)*4+8*3+(15+9+13)*2=126,因此答案为C。
二、非选择题
13.(1)5　(2)abdhecfijkg　hdbeaifjkcg　hdebikjfgca
解析:本题主要考查的是二叉树的深度和遍历。(1)该二叉树共有5层,根节点的深度为1,因此该二叉树的深度为5。(2)二叉树的前序遍历的规则是先访问根节点,然后访问左子树,最后访问右子树,对左子树和右子树仍按上述规则访问,因此前序遍历序列为“abdhecfijkg”;中序遍历的规则是先访问左子树,然后访问根节点,最后访问右子树,因此中序遍历序列为“hdbeaifjkcg”;后序遍历的规则是先访问左子树,然后访问右子树,最后访问根节点,因此后序遍历序列为“hdebikjfgca”。
14.
数组下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
数组元素 a b c d e f g h i j
解析:本题主要考查的是二叉树的数组表示。图中的二叉树为非完全二叉树,先将它补全为一棵完全二叉树,即补全d节点的左孩子节点、e节点的左右孩子节点、f节点和g节点的左孩子节点,然后按照完全二叉树的方法来表示,补全后的完全二叉树如下图所示:
然后二叉树从上到下从左到右的顺序在相应的位置上填入节点名称即可。
15.AN=2AN-1+AN-2(N>=2),且A0=1,A1=3
解析:本题由简单的问题入手,将满足条件的3个数组成的所有可能的N位数,以树结构的形式表示出来,从中发现问题的规律。
设N=1时,这时a,b,c 3个数组成的一位数有3个。
设N=2时,树结构如下图所示:
共能组成7个两位数。
N=3时,树结构如下图所示:
共能组成17个三位数。
因此,可得到AN=2AN-1+AN-2(N>=2),且A0=1,A1=3。
16.3
解析:已知17条边,可知节点为18个,设根的度为x,则所有节点的度之和为:x+4*4+3*1+12,总度数应是边的两倍,则有x+4*4+3*1+12=17*2,求得x=3,因此T的树根的度数为3。

展开更多......

收起↑