资源简介

(共23张PPT)
第四章　树
验收卷(三)　树
(考试时间40分钟　满分50分)
一、选择题(本题共14小题，每小题2分，共28分)
1.树中所有节点的度等于(　　)
C
解析　本题主要考查的是节点的度。树中节点的度是指该节点的后继节点数，两个节点间有一条边，即节点的度是从该节点出发的边数。因此，所有节点的度等于所有节点数减1，故答案为C。
A.所有节点数 B.所有节点数加1
C.所有节点数减1 D.所有节点数加2
C
2.一棵高度为6的满二叉树中的节点数为(　　)
解析　本题主要考查的是满二叉树的特点。一棵高度为6的满二叉树中的节点数为26－1个，即63个，因此，答案为C。
A.31个 B.32个 C.63个 D.64个
B
3.某树的结构如下，下列说法正确的是(　　)
解析　本题考查树的性质。A选项数的度取决于节点的最大度数，因此该树的度为3。
A.该树的度为4
B.该树的高度为4
C.该树的叶子节点为3个
D.节点F和G是兄弟节点
A
4.一棵有n(n>0)个节点的二叉树，其节点为0度或2度，则此树的最大高度是(　　)
解析　本题考查二叉树基本性质。该二叉树的节点的度都为0或2，即除根节点外，其每个节点都有一个兄弟节点。题目要求树的最大高度，每层就只有2个节点(除了根节点)，若总节点数加上1，相当于令第1层也变成两个节点，那么总层数就是(n＋1)∥2。
A.(n＋1)∥2 B.n∥2 C.(n－1)∥2 D.int(log2n＋1)
C
5.已知一棵完全二叉树有8个叶子节点，下列说法正确的是(　　)
解析　本题考查树的性质。根据树的性质，2度节点个数为叶子节点个数减1，因此2度节点有7个。由于是完全二叉树，1度节点的个数为0或1，因此总共节点数为15或16个。A选项根据总共节点数，可知该树可能是3层，也可以是4层。B选项当总节点是3层时，是一棵满二叉树，当节点为16时，在4层下有一个节点。C选项当总节点为16时，有一个1度节点。D选项2度节点个数为7个。
A.该完全二叉树的高度可能为3
B.该完全二叉树的形态只有一种
C.该完全二叉树可能有1个度为1的节点
D.该完全二叉树有9个度为2的节点
C
6.如图所示，将二叉树A的根节点与二叉树B的根节点连接，使得二叉树A成为二叉树B的左子树，合并为一棵新的二叉树C。下列说法中正确的是 (　　)
解析　本题考查二叉树的性质和遍历。新二叉树高度为4；叶子节点数量为4，是一棵完全二叉树；中序遍历的结果为84251637，不是一个有序序列。
A.二叉树C的高度为3
B.二叉树C的叶子节点数量为3
C.二叉树C是一棵完全二叉树
D.二叉树C中序遍历的结果是一个有序序列
D
A.二叉树的数据元素之间呈非线性关系
B.二叉树的第 k 层上最多有2k－1(k≥1)个节点
C.由前序遍历和中序遍历序列能唯一确定一棵二叉树
D.具有 100 个节点的完全二叉树有 50 个度为 2 的节点
解析　本题考查树的性质。A选项树表现一种层次性的非线性关系。D选项设二叉树0度、1度和2度的节点个数分别为t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉树1度节点个数为0或1，因此t2值为49。
A
8.某二叉树如图所示，该二叉树的中序遍历序列是(　　)
解析　中序遍历的每棵子树均为左根右。
A.BIGDHAECF B.IGHDBEFCA
C.ABDGIHCEF D.BDGHIACEF
C
9.对于如图所示的二叉树，下列说法正确的是 (　　)
解析　本题考查二叉树相关知识。A选项叶子节点有7，9，15，共3个。B选项完全二叉树要求叶子节点从右开始，且最多只出现在最下面 2 层。C 正确，前序遍历时 2－5－7－8－9－10－13－15，是一个递增序列。D选项用数组表示是[2，5，10，7，8，None，13，None，None，9，None，None，None，None，15].
A.叶子节点有 4 个
B.是完全二叉树，树的高度为 4
C.前序遍历的结果是一个递增序列
D.可以使用数组[2，5，10，7，8，13，9，15]存储
B
10.某二叉树的树形结构如图所示，其后序遍历结果为“物技化数英语”，则中序遍历结果为(　　)
解析　本题考查二叉树遍历。后序遍历是“物技化数英语”可知，根节点为语，数英分别是语节点的左右孩子。物为数的左孩子，技为最高层的左孩子，化为数的右孩子。
A.语数英物化技 B.物数技化语英
C.语数物化技英 D.化物技英数语
B
11.已知一棵二叉树如图所示，下列说法正确的是(　　)
解析　A选项B和E也是叶子节点。B选项F是D的左子树，在中序、后序遍历中，F先于D，D和E分别是C的左右子树，D肯定先于E。
A.树的高度是 4，节点F 是唯一的叶子节点
B.中序、后序的遍历方式，节点 F 先于节点 D、E 访问
C.前序遍历的结果为A－B－C－D－E－F
D.使用数组可以表示为[‘A’，‘B’，‘C’，‘ ’，‘ ’，‘D’， ‘E’，‘F’]
D
A.该表达式树是一棵二叉树，树的度是2，高度是5
B.该树的叶子节点数比度为2的节点数多1个
C.若采用完全二叉树数组从 0 号位开始存储，则节点b存储在6号位
D.该表达式树的前序遍历序列是×d＋/fc－ab
解析　本题考查树与二叉树相关知识。树的度是最大的节点的度，树的高度是节点最大的层数，A选项在任意一棵二叉树中都有n0＝n2＋1的性质，即叶子节点数等于度为2的节点数多一个；非完全二叉树若用完全二叉树保存时需将树补成完全二叉树，即第3层需补全d节点的两个孩子节点，此时节点b存储在第6号位置上。D选项该表达式树的前序遍历序列是×d＋/f－cab，对节点“－”而言先于其子节点c。
C
13.二叉树的中序遍历为 BAEDFC，后序遍历为 BEFDCA，其前序遍历为(　　)
解析　本题考查二叉树的相关知识。后序遍历确定根节点，中序遍历区分左右子树。根据二叉树的中序遍历和后序遍历可知，该二叉树的形状如图所示，前序遍历为：ABCDEF。
A.ABDEFC B.ABDCEF C.ABCDEF D.ABCDFE
B
14.已知一棵二叉树的前序遍历序列为ABCDEFG，则该二叉树中序遍历序列可能为(　　)
A.CABDEFG B.ABCDEFG C.DACEFBG D.ADBCFEG
解析　本题考查二叉树的相关知识。前序遍历找出根A，中序遍历根据根的位置，区别左右子树。A选项左子树为C，但C在前序遍历中后于B访问，不正确。C选项同A选项。D选项该树没有左子树，在右子树中，B为根，D为B的左孩子，但在前序中D后于C访问，不正确。B选项前序遍历为根左右，中序遍历为左根右，当树缺失左孩子时，前中序遍历是一样的。
二、非选择题(本题共4小题，共22分)
答案　12　2011　(评分规则：写对一个得4分)
解析　总共有2011个叶子节点，所以第n层的叶子节点可能是1到2n－1，n＝12，这是完全二叉树的情况；如果二叉树的每层只有一个右子树，则到2011层共有2011个叶节点，因此答案为12或2011。
15.(6分)如果根节点的深度记为1，有一棵恰有2011个叶子节点的二叉树，则该二叉树的深度可能是____________或________。
16.(3分)设有一棵k叉树，其中只有度为0和k两种节点，设n0、nk分别表示度为0和度为k的节点个数，求出n0 和nk之间的关系(形式如n0＝数学表达式，数学表达式仅含nk 、k和数字)。关系式为________________________。
答案　n0和nk之间的关系为：n0＝(k－1) nk＋1
解析　设k叉树中共有x个节点，则有n0＋nk＝x，度为k的节点，表示每个节点均有k个子节点，即有k*nk条边，k叉树的总边数为x－1条，即k*nk＝x－1，因此可得到n0＋nk＝k*nk＋1，求得n0＝(k－1) nk＋1。
17.(7分)3个节点数的不同形态的二叉树一共有__________种；5个节点数的不同形态的二叉树一共有________种。
答案　5　42
解析　本题主要考查的是二叉树的形态。本题可以分三种情况讨论：只有左子树、左右子树均存在、只有右子树，也可以直接用catalan数的公式来计算，h(n)＝(2n)！/(n！*(n＋1)！)。3个节点数的不同形态的二叉树比较简单，可直接画树来求，共有5种，而5个节点数的不同形态的二叉树比较多，可用catalan数的公式来计算，共有42种。
18.(6分)二叉查找树。所谓的二叉查找树是指每一个树根的值大于左子树的值，但小于右子树的值，左右子树也是二叉查找树，树的每一个节点的值都不相同。
已知节点信息顺序存储在数组中，编写程序创建一棵二叉查找树，并输出该二叉树的数组表示。程序运行效果如图所示。
原始数组为：
[11，6，8，15，12，16，9，7]
二叉树内容：
[11][6][15][None][8][12][16][None][None][7][9]
实现上述功能的程序如下，请回答下列问题。
def Bt_build (btree，data，length)：
global x
x＝0
for i in range(length)：
level＝0
while btree[level]！＝None：
　　　　 if data[i]>btree[level]：
　　　　　　 ①________________
　　　　else：
　　　　　　level＝level*2＋1
②________________
if x　　　x＝level
data＝[11，6，8，15，12，16，9，7]
length＝len(data)
btree＝[None]*100
print('原始数组为：')
print(data)
print(' ')
③________________
print('二叉树内容：')
for i in range(x＋1)：
print('[{}]'.format(btree[i])，end＝' ')
print()
(1)若data列表中元素依次为“15，10，8，18，20，9，11”，则输出的二叉树内容为______________。
(2)请在程序划线处填入合适的代码。
划线①处应填入的代码：
______________；
划线②处应填入的代码：
______________；
划线③处应填入的代码：
______________。
答案　(1)[15] [10] [18] [8] [11] [None] [20] [None] [9]　(2)①level＝level*2＋2　②btree[level]＝data[i]　③Bt_build (btree，data，length)
解析　(1)本题主要考查的是二叉树的数组表示。首先构建好查找二叉树，然后将该二叉树补全为完全二叉树，最后用数组来表示。表示方法为由第1层开始，依次到下一层，在每一层中按照从左到右的顺序创建节点，补充的节点用None表示。(2)左子树的索引值是父节点的索引值×2＋1，右子树的索引值是父节点的索引值×2＋2，if 中的条件为data[i]>btree[level]，可知data[i]为btree[level]节点的右孩子节点，因此右孩子的位置为①level＝level*2＋2；确定好子节点的索引位置level后，将数据元素data[i]存储在btree[level]中，因此，划线②处代码为btree[level]＝data[i]；划线③处代码的功能是调用Bt_build函数，三个参数分别为btree(存储查找二叉树节点的数组)、data(生成二叉树的各节点列表)、length(节点个数)，因此，③处代码为Bt_build (btree，data，length)。验收卷(三)　树
(考试时间40分钟　满分50分)
一、选择题(本题共14小题，每小题2分，共28分)
1.树中所有节点的度等于(　　)
A.所有节点数 B.所有节点数加1
C.所有节点数减1 D.所有节点数加2
2.一棵高度为6的满二叉树中的节点数为(　　)
A.31个 B.32个 C.63个 D.64个
3.某树的结构如下，下列说法正确的是(　　)
A.该树的度为4
B.该树的高度为4
C.该树的叶子节点为3个
D.节点F和G是兄弟节点
4.一棵有n(n>0)个节点的二叉树，其节点为0度或2度，则此树的最大高度是(　　)
A.(n＋1)∥2 B.n∥2 C.(n－1)∥2 D.int(log2n＋1)
5.已知一棵完全二叉树有8个叶子节点，下列说法正确的是(　　)
A.该完全二叉树的高度可能为3
B.该完全二叉树的形态只有一种
C.该完全二叉树可能有1个度为1的节点
D.该完全二叉树有9个度为2的节点
6.如图所示，将二叉树A的根节点与二叉树B的根节点连接，使得二叉树A成为二叉树B的左子树，合并为一棵新的二叉树C。下列说法中正确的是 (　　)
A.二叉树C的高度为3
B.二叉树C的叶子节点数量为3
C.二叉树C是一棵完全二叉树
D.二叉树C中序遍历的结果是一个有序序列
7.下列关于二叉树的说法，不正确的是 (　　)
A.二叉树的数据元素之间呈非线性关系
B.二叉树的第 k 层上最多有2k－1(k≥1)个节点
C.由前序遍历和中序遍历序列能唯一确定一棵二叉树
D.具有 100 个节点的完全二叉树有 50 个度为 2 的节点
8.某二叉树如图所示，该二叉树的中序遍历序列是(　　)
A.BIGDHAECF B.IGHDBEFCA
C.ABDGIHCEF D.BDGHIACEF
9.对于如图所示的二叉树，下列说法正确的是 (　　)
A.叶子节点有 4 个
B.是完全二叉树，树的高度为 4
C.前序遍历的结果是一个递增序列
D.可以使用数组[2，5，10，7，8，13，9，15]存储
10.某二叉树的树形结构如图所示，其后序遍历结果为“物技化数英语”，则中序遍历结果为(　　)
A.语数英物化技 B.物数技化语英
C.语数物化技英 D.化物技英数语
11.已知一棵二叉树如图所示，下列说法正确的是(　　)
A.树的高度是 4，节点F 是唯一的叶子节点
B.中序、后序的遍历方式，节点 F 先于节点 D、E 访问
C.前序遍历的结果为A－B－C－D－E－F
D.使用数组可以表示为[‘A’，‘B’，‘C’，‘ ’，‘ ’，‘D’， ‘E’，‘F’]
12.某表达式树如下图所示，下列说法错误的是(　　)
A.该表达式树是一棵二叉树，树的度是2，高度是5
B.该树的叶子节点数比度为2的节点数多1个
C.若采用完全二叉树数组从 0 号位开始存储，则节点b存储在6号位
D.该表达式树的前序遍历序列是×d＋/fc－ab
13.二叉树的中序遍历为 BAEDFC，后序遍历为 BEFDCA，其前序遍历为(　　)
A.ABDEFC B.ABDCEF C.ABCDEF D.ABCDFE
14.已知一棵二叉树的前序遍历序列为ABCDEFG，则该二叉树中序遍历序列可能为(　　)
A.CABDEFG B.ABCDEFG C.DACEFBG D.ADBCFEG
二、非选择题(本题共4小题，共22分)
15.(6分)如果根节点的深度记为1，有一棵恰有2011个叶子节点的二叉树，则该二叉树的深度可能是____________或________。
16.(3分)设有一棵k叉树，其中只有度为0和k两种节点，设n0、nk分别表示度为0和度为k的节点个数，求出n0 和nk之间的关系(形式如n0＝数学表达式，数学表达式仅含nk 、k和数字)。关系式为________________________。
17.(7分)3个节点数的不同形态的二叉树一共有__________种；5个节点数的不同形态的二叉树一共有________种。
18.(6分)二叉查找树。所谓的二叉查找树是指每一个树根的值大于左子树的值，但小于右子树的值，左右子树也是二叉查找树，树的每一个节点的值都不相同。
已知节点信息顺序存储在数组中，编写程序创建一棵二叉查找树，并输出该二叉树的数组表示。程序运行效果如图所示。
原始数组为： [11，6，8，15，12，16，9，7] 二叉树内容： [11][6][15][None][8][12][16][None][None][7][9]
实现上述功能的程序如下，请回答下列问题。
def Bt_build (btree，data，length)：
global x
x＝0
for i in range(length)：
level＝0
while btree[level]！＝None：
　　　　 if data[i]>btree[level]：
　　　　　　 ①________________
　　　　else：
　　　　　　level＝level*2＋1
②________________
if x　　　x＝level
data＝[11，6，8，15，12，16，9，7]
length＝len(data)
btree＝[None]*100
print('原始数组为：')
print(data)
print(' ')
③________________
print('二叉树内容：')
for i in range(x＋1)：
print('[{}]'.format(btree[i])，end＝' ')
print()
(1)若data列表中元素依次为“15，10，8，18，20，9，11”，则输出的二叉树内容为______________。
(2)请在程序划线处填入合适的代码。
划线①处应填入的代码：
______________；
划线②处应填入的代码：
______________；
划线③处应填入的代码：
______________。
验收卷(三)　树
1.C　[本题主要考查的是节点的度。树中节点的度是指该节点的后继节点数，两个节点间有一条边，即节点的度是从该节点出发的边数。因此，所有节点的度等于所有节点数减1，故答案为C。]
2.C　[本题主要考查的是满二叉树的特点。一棵高度为6的满二叉树中的节点数为26－1个，即63个，因此，答案为C。]
3.B　[本题考查树的性质。A选项数的度取决于节点的最大度数，因此该树的度为3。]
4.A　[本题考查二叉树基本性质。该二叉树的节点的度都为0或2，即除根节点外，其每个节点都有一个兄弟节点。题目要求树的最大高度，每层就只有2个节点(除了根节点)，若总节点数加上1，相当于令第1层也变成两个节点，那么总层数就是(n＋1)∥2。]
5.C　[本题考查树的性质。根据树的性质，2度节点个数为叶子节点个数减1，因此2度节点有7个。由于是完全二叉树，1度节点的个数为0或1，因此总共节点数为15或16个。A选项根据总共节点数，可知该树可能是3层，也可以是4层。B选项当总节点是3层时，是一棵满二叉树，当节点为16时，在4层下有一个节点。C选项当总节点为16时，有一个1度节点。D选项2度节点个数为7个。]
6.C　[本题考查二叉树的性质和遍历。新二叉树高度为4；叶子节点数量为4，是一棵完全二叉树；中序遍历的结果为84251637，不是一个有序序列。]
7. D　[本题考查树的性质。A选项树表现一种层次性的非线性关系。D选项设二叉树0度、1度和2度的节点个数分别为t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉树1度节点个数为0或1，因此t2值为49。 ]
8.A　[中序遍历的每棵子树均为左根右。]
9.C　[本题考查二叉树相关知识。A选项叶子节点有7，9，15，共3个。B选项完全二叉树要求叶子节点从右开始，且最多只出现在最下面 2 层。C 正确，前序遍历时 2－5－7－8－9－10－13－15，是一个递增序列。D选项用数组表示是[2，5，10，7，8，None，13，None，None，9，None，None，None，None，15].]
10.B　[本题考查二叉树遍历。后序遍历是“物技化数英语”可知，根节点为语，数英分别是语节点的左右孩子。物为数的左孩子，技为最高层的左孩子，化为数的右孩子。]
11.B　[A选项B和E也是叶子节点。B选项F是D的左子树，在中序、后序遍历中，F先于D，D和E分别是C的左右子树，D肯定先于E。]
12.D　[本题考查树与二叉树相关知识。树的度是最大的节点的度，树的高度是节点最大的层数，A选项在任意一棵二叉树中都有n0＝n2＋1的性质，即叶子节点数等于度为2的节点数多一个；非完全二叉树若用完全二叉树保存时需将树补成完全二叉树，即第3层需补全d节点的两个孩子节点，此时节点b存储在第6号位置上。D选项该表达式树的前序遍历序列是×d＋/f－cab，对节点“－”而言先于其子节点c。]
13.C　[本题考查二叉树的相关知识。后序遍历确定根节点，中序遍历区分左右子树。根据二叉树的中序遍历和后序遍历可知，该二叉树的形状如图所示，前序遍历为：ABCDEF。]
14.B　[本题考查二叉树的相关知识。前序遍历找出根A，中序遍历根据根的位置，区别左右子树。A选项左子树为C，但C在前序遍历中后于B访问，不正确。C选项同A选项。D选项该树没有左子树，在右子树中，B为根，D为B的左孩子，但在前序中D后于C访问，不正确。B选项前序遍历为根左右，中序遍历为左根右，当树缺失左孩子时，前中序遍历是一样的。]
15.12　2011　(评分规则：写对一个得4分)
解析　总共有2011个叶子节点，所以第n层的叶子节点可能是1到2n－1，n＝12，这是完全二叉树的情况；如果二叉树的每层只有一个右子树，则到2011层共有2011个叶节点，因此答案为12或2011。
16.n0和nk之间的关系为：n0＝(k－1) nk＋1
解析　设k叉树中共有x个节点，则有n0＋nk＝x，度为k的节点，表示每个节点均有k个子节点，即有k*nk条边，k叉树的总边数为x－1条，即k*nk＝x－1，因此可得到n0＋nk＝k*nk＋1，求得n0＝(k－1) nk＋1。
17.5　42
解析　本题主要考查的是二叉树的形态。本题可以分三种情况讨论：只有左子树、左右子树均存在、只有右子树，也可以直接用catalan数的公式来计算，h(n)＝(2n)！/(n！*(n＋1)！)。3个节点数的不同形态的二叉树比较简单，可直接画树来求，共有5种，而5个节点数的不同形态的二叉树比较多，可用catalan数的公式来计算，共有42种。
18.(1)[15] [10] [18] [8] [11] [None] [20] [None] [9]
(2)①level＝level*2＋2　②btree[level]＝data[i]
③Bt_build (btree，data，length)
解析　(1)本题主要考查的是二叉树的数组表示。首先构建好查找二叉树，然后将该二叉树补全为完全二叉树，最后用数组来表示。表示方法为由第1层开始，依次到下一层，在每一层中按照从左到右的顺序创建节点，补充的节点用None表示。(2)左子树的索引值是父节点的索引值×2＋1，右子树的索引值是父节点的索引值×2＋2，if 中的条件为data[i]>btree[level]，可知data[i]为btree[level]节点的右孩子节点，因此右孩子的位置为①level＝level*2＋2；确定好子节点的索引位置level后，将数据元素data[i]存储在btree[level]中，因此，划线②处代码为btree[level]＝data[i]；划线③处代码的功能是调用Bt_build函数，三个参数分别为btree(存储查找二叉树节点的数组)、data(生成二叉树的各节点列表)、length(节点个数)，因此，③处代码为Bt_build (btree，data，length)。

展开更多......

收起↑