资源简介

第四章　树
课时1　树与二叉树
一、基础巩固
1.树最适合用来表示下面哪种类型的数据(　　)
A.有序数据元素
B.无序数据元素
C.元素之间无联系的数据
D.元素之间具有分支层次关系的数据
2.在一棵树中，没有子节点的节点是(　　)
A.父节点 B.叶节点 C.根节点 D.空节点
3.具有3个节点的二叉树形态有5种，可推测出具有4个节点的二叉树形态共有(　　)
A.13种 B.14种 C.15种 D.16种
4.下列有关二叉树的说法，正确的是(　　)
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.至少有一个节点的度为2
D.任一节点的度均为2
5.一棵度为3，深度为4的树的节点个数至多为(　　)
A.31 B.32 C.40 D.42
6.在一棵度为2的树中，度为2的节点数为15，度为1的节点数为30，则叶子节点(度为0的节点)的个数为(　　)
A.15 B.16 C.17 D.47
7.一棵高度为h的满二叉树，从上到下，同层从左到右的次序从1开始连续编号，若某子节点的右孩子的编号为x(x>1)，则该子节点的编号为(　　)
A.2*x＋1 B.2*x－1 C.x/2 D.x∥2
8.已知一棵二叉树有13个节点，树中度为1的节点数为2，则该树度为2的节点数为(　　)
A.4 B.5 C.6 D.11
9.下列关于二叉树的说法中，正确的是(　　)
A.完全二叉树一定是满二叉树
B.二叉树的深度是指二叉树中最大节点的度
C.二叉树的子树没有左右之分，左右子树的次序可以交换
D.二叉树中所有节点的度都小于或等于2
10.有一棵树如图所示，回答下面的问题：
这棵树的根节点是①________，叶子节点个数是②________；节点E的度是③________，节点E的孩子节点是④________；节点E的父节点是⑤________；这颗树的度为⑥________；这棵树的深度是⑦______。
二、能力提升
11.根节点的深度为1，则深度为5的完全二叉树中节点数最少为(　　)
A.9 B.15 C.16 D.31
12.在一棵满二叉树中，若有N个叶节点，则该满二叉树的节点总数为(　　)
A.N个 B.2N个 C.2N－1个 D.2N＋1个
13.完全二叉树共有2*n－1个节点，则它的叶节点数为(　　)
A.n－1 B.n C.2*n D.2*n－1
14.假设完全二叉树的树根为第1层，树中第10层有5个叶子节点，则完全二叉树最多节点个数是(　　)
A.2047 B.2048 C.2037 D.2038
课时1　树与二叉树
1.D　[树能很好地描述有分支和层次特性的数据集合。]
2.B　[在树中，没有子节点的节点称为叶节点，也称终端节点，因此答案为B。]
3.B　[可先画出3个节点的二叉树形态，然后求得二叉树的形态总数，具有4个节点的二叉树形态共有14种，因此，答案为B。]
4.B　[本题主要考查的是二叉树的度。二叉树的度为最大节点的度，二叉树中的节点的度最大为2，最小为0(叶节点)，因此正确答案为B。]
5.C　[度为3的树，即每个分支节点最多有3个孩子节点，按照每个分支节点均有3个孩子节点，即每一层都是上一层节点数的3倍，则前4层的节点数应分别为1，3，9，27，共40个节点，答案为C。]
6.B　[设度为0的节点数为n0，总节点数为n，则由树中总结点数、不同度数的节点个数及总边数之间的关系可以列出以下两个等式：(1)n＝n0＋n1＋n2＝n0＋30＋15；(2)n－1＝1*n1＋2*n2＝30＋30，可得n＝61，n0＝16，答案为B。]
7.D　[在一棵满二叉树中，若父节点的编号为x，则它的左孩子的节点编号为2*x，右孩子的节点编号为2*x＋1，同理，若某子节点的右孩子的编号为x，则该子节点的编号为x∥2，因此答案为D。]
8.B　[本题考查二叉树性质。根据二叉树的性质，n0＝n2＋1，n＝n0＋n1＋n2，可以推出n2＝5。]
9.D　[满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树，因此A选项错误；二叉树的度是指二叉树中最大节点的度，而二叉树的深度是指二叉树中节点的最大层数，因此B选项错误；二叉树的子树有左右之分，且左右子树的次序不能颠倒，因此C选项错误；二叉树中所有节点的度都小于或等于2，因此答案为D。]
10.①A　②9　③2　④IJ　⑤A　⑥5　⑦4
解析　参照树的概念和特性解答。
11.C　[本题主要考查的是完全二叉树的深度。它是由一个深度为4的满二叉树的基础上得到的，要节点数最少，则第5层上只有一个节点，因此最少为16个节点，答案为C。]
12.C　[满二叉树除了叶节点外，其他节点均有2个节点，在二叉树中，叶子节点比度为2的节点多1个，因此，当叶节点个数为N时，它的节点总数为N＋N－1＝2N－1个，因此答案为C。]
13.B　[完全二叉树共有2*n－1个节点，该完全二叉树可能就是一棵满二叉树，或者是将满二叉树的最下面一层中的偶数个叶节点删除得到的，因此它的叶节点数为n，答案为B。]
14.C　[根据完全二叉树的性质可知，叶子节点最多只出现在最下面2层，此题考查的是最多节点数，那么该二又树应有11层。前10层节点：210－1＝1023第11层满节点数为：20－1＝1024。因为第10层有S个叶子节点，所以第11层少10个节点，故总结点数为，1023＋1024－10＝2037。]课时2　二叉树的基本操作
一、基础巩固
1.如图所示的二叉树，若要得到一个递增序列，可以采用的遍历方式是(　　)
A.前序遍历 B.中序遍历 C.后序遍历 D.逐层遍历
2.某二叉树如图所示，下列说法正确的是(　　)
A.该二叉树共有5个叶子节点
B.该二叉树是一棵完全二叉树
C.对该二叉树进行中序遍历后的计算结果是32
D.该二叉树的后序遍历序列为731＋*426＋/－
3.某二叉树的结构如图所示，下列说法不正确的是(　　)
A.该二叉树是一棵完全二叉树
B.该二叉树的叶子节点数是3个
C.该二叉树的中序遍历结果是DCBEAF
D.该二叉树的度为2
4.数学表达式3/(5*2)可用二叉树表示，如图所示。
下列关于该二叉树的说法，正确的是(　　)
A.是完全二叉树
B.叶子节点数为2
C.前序遍历结果为352*/
5.某二叉树的树形结构如图所示，其后序遍历结果为FBCEAD，则前序遍历结果为(　　)
A.ABCDEF B.FEDCBA C.DFACBE D.FDBCAE
6.已知某二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBDAEF，则下列说法正确的是 (　　)
A.其后序遍历结果为DCBFEA
B.该二叉树为完全二叉树
C.该二叉树深度为3，叶子节点数为3
D.该二叉树用一维数组实现需要6个节点的存储空间才能表示
7.有一棵二叉树，如图所示，下列说法正确的是(　　)
A.此二叉树是完全二叉树
B.此二叉树的深度是 3
C.此二叉树的中序遍历为 H－D－B－E－A－C－F
D.此二叉树用一维数组表示为['A'，'B'，″，'C'，'D'，'E'，″，'F'，″，'H']
8.对于右图所示的二叉树，下列说法正确的是(　　)
A.树的高度是4，是一棵完全二叉树
B.度为2的节点数比叶子节点数多1
C.若采用数组存储法，需要6个存储空间
D.该二叉树的后序遍历序列是fdebca
9.用一维数组表示二叉树，如下表所示：
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有关该二叉树的说法正确的是(　　)
A.该树中共有4个叶子节点，度为2的节点有2个
B.该树的中序遍历为B－F－D－G－A－C－E
C.该树是完全二叉树，其深度为 4
D.该树有7条边
10.某二叉树用一维数组实现的示意图如下所示。
0 1 2 3 4 5 6 7 8
A B C D E F
下列关于该二叉树的说法，正确的是(　　)
A.是完全二叉树
B.叶子节点数为3
C.前序遍历结果为ABDFCE
D.深度为3
11.二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为(　　)
A.abcde B.abdec C.debac D.adbce
二、能力提升
12.有二叉树的前序遍历序列为A－B－C－E－F－G－D，中序遍历序列为A－E－C－F－G－B－D，则关于该二叉树的说法正确的是(　　)
A.该二叉树根节点的度为1
B.该二叉树的高度为4
C.该二叉树中节点G是节点C的左孩子
D.该二叉树中叶子节点的个数为4
13.某二叉树前序遍历为ABDCE，后序遍历为DBECA，则该二叉树可能情况数量是(　　)
A.1 B.2 C.4 D.6
14.如图所示的二叉树，根节点为0，每个节点的左子节点为0，右子节点为1，每一条从根到叶子的路径都组成一个二进制数。例如：从根到叶子 a 的路径组成二进制数 011，转换为十进制数是 3。若某完全二叉树共有 13 个节点，则它能表示的最大十进制数是(　　)
A.3 B.4 C.5 D.6
15.某二叉树前序遍历的结果为“大好河山”，则中序遍历的结果不可能是(　　)
A.大好河山 B.河好山大 C.好山大河 D.山河好大
课时2　二叉树的基本操作
1.B　[中序遍历的结果为3，5，7，8，10，12，17。]
2.D　[A选项共有6个叶子节点。B选项该树倒数第2层不是满二叉树，因此不是完全二叉树。C选项中序遍历的结果为7*3＋1－4/2＋6，计算结果为26。]
3.A　[本题考查二叉树的性质。该树不是完全二叉树。叶子节点有DEF，节点中最大的度为2。]
4.D　[本题考查二叉树的遍历。A选项完全二叉树是指一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同。3所在节点缺少叶子节点，故该二叉树不是完全二叉树。B选项3、5、2所在节点为叶子节点，数量为3。C选项前序遍历结果为/3*52。]
5.C　[根据树的形态，画出后序遍历的路径，从而确定每个节点的值。]
6.C　[本题
考查树的性质和遍历。根据前序遍历确定根节点，中序遍历区分左右子树，画出二叉树。其后序遍历结果为CDBFEA，该二叉树最后一层叶子节点不是从左向右分布。该二叉树深度为 3，叶子节点数为 3，该二叉树补全为完全二叉树，用一维数组实现需要 7 个节点的存储空间才能表示。]
7.C　[本题考查二叉树的相关知识。A选项节点 C 缺少左子树，不是完全二叉树。B选项该二叉树的深度是 4。D选项节点C前没有空节点。]
8.D　[本题考查树与二叉树相关知识。A 选项树的高度是4，但不是完全二叉树。完全二叉树是除最后一层外节点都满节点，且最后一层节点都集中左边位置上，而该二叉树倒数第二层也没有满节点(c 没有子节点)。B选项度为2的节点有2个，而叶子节点有3个。实际上，任意二叉树的都满足叶子节点数比度为2的节点数多一个。C选项若有数组存储二叉树时，c节点虽然没有子节点，但是也要在数组中占据额外的两个空元素位置，因此总容量应该是8个存储空间。D选项后序遍历为fdebca。]
9.B　[本题考查树的性质。根据存储结构画出的二叉树如图所示。A选项3个叶子节点。 ]
10.C　[本题考查二叉树的知识。根据题意画出二叉树如图所示：
该树不是一颗完全二叉树，叶子节点个数2，深度为4。前序遍历时A－B－D－F－C－E。]
11.A　[本题考查树的性质。从后序遍历来看，a是根节点，b是左子树，dce是右子树；c是右子树的根节点，d和e分别是左右子树。因此前序遍历为abcde。]
12.A　[本题考查二叉树的性质和遍历。根据二叉树的前序遍历和中序遍历画出二叉树。该二叉树的根节点A的度为1，高度为5，节点G是节点F的右孩子。该二叉树的叶子节点是E、G、D。]
13.C　[本题考查二叉树遍历的相关知识。左右子树的根节点都只有一个子节点，以下四种情况的前序和后序遍历都符合题目要求：]
14.C　[本题考查二叉树的性质。根据完全二叉树的性质可知，该二叉树共计13个节点。那么深度为4，前3层有7个节点，第4层有6个叶子节点，最大十进制数是0101B。]
15.C　[本题考查树的遍历。前序遍历为根左右，A选项任一节点没有左节点，则前中序均为根右。B选项好是第1个左节点，则好是大的左节点，是河的根，山为河的兄弟。D选项任一节点没有右节点。C选项好是大的左节点，山是右节点，或山是大的左节点，是好的父节点，则前序遍历不对了。]课时3　抽象数据类型
一、基础巩固
1.下列有关Python抽象数据类型(ADT)的说法中，不正确的是(　　)
A.抽象数据是指一个数学模型及定义在该模型上的一组操作
B.Python的一个内置类型不是一个抽象数据类型
C.抽象数据类型是一种思想，也是一种技术
D.定义一个抽象数据类型(ADT)，目的是要定义一类计算对象，使它们具有某些特定的功能
2.下列选项中属于Python抽象数据类型(ADT)优点的是(　　)
A.使用抽象数据类型编写的程序结构不清晰、层次不分明
B.抽象数据类型的模块化特点，在程序设计中容易纠正，但不易维护
C.由于抽象数据类型的表示和实现都可以封装起来，便于移植和重用
D.使用抽象数据类型编写程序，增加了算法复杂度，降低了程序运行的效率
3.下列是一个简单的ADT：
class Sstring：
def _ _init _ _(self，str1)：
self.ss＝str1
def substr(self，a，b)：
return self.ss[a－1：b]
def concat(self，str2)：
return self.ss＋str2
sstr1＝Sstring(″Python″)　　　　
print(sstr1.substr(2，4))
print(sstr1.concat(″ is so easy！″))
下列有关该抽象数据类型(ADT)实例的说法中，不正确的是(　　)
A.Sstring为抽象数据类型名
B.sstr1为Sstring类的一个对象
C.执行代码“print(sstr1.substr(2，4))”，输出结果为“yth”
D.执行代码“print(sstr1.concat(″is so easy！″))”，输出结果为“yth is so easy！”
4.下列是一个简单的ADT：
class xcal：
def _ _init _ _(self，numx，numy)：
self.numx＝numx
self.numy＝numy
def xadd(self，another)：
numx＝self.numx*another.numx
numy＝self.numy*another.numy
return xcal(numx，numy)
def print(self)：
print(str(self.numx)＋'/'＋str(self.numy))
x＝xcal(2，3)
y＝x.xadd(xcal(4，5))
y.print()程序运行后，输出的结果为(　　)
A.6/20 B.15/8 C.10/12 D.8/15
二、能力提升
5.用抽象数据类型实现队列操作的代码如下，请回答下列问题：
class Queue：
def _ _init _ _(self)：
self.queue＝[]
def isEmpty(self)：
return self.queue＝＝[]
def enqueue(self，data)：　#入队操作
　　　　①________________
def dequeue(self)：　 #出队操作
if len(self.queue)：
　　　__②________________
def size(self)：　　 #测试队列长度
return len(self.queue)
q＝Queue()
q.enqueue(8)
q.enqueue(9)
q.enqueue(10)
while not q.isEmpty()：
print(q.dequeue()，end＝″″)
(1)程序运行后，输出的结果是__________________________________________。
(2)请在程序划线处填入合适的代码。
6.创建一个ADT，实现如下功能：输入一个18位的身份证号码，输出该身份证的人的性别。
判断方法：根据身份证号的第17位上的数字来判断，若是奇数，则表示是位男士；若是偶数，则表示是位女士。
程序运行示例如图所示：
请输入身份证号：330425198202261156 身份证号为：330425198202261156是位男士。
实现上述功能的代码如下，请回答下列问题：
class sexpd：
def _ _init _ _(self，sfzcode)：
　　　self.code＝sfzcode
def isxb(self)：
　　xbcode＝int(self.code[16])
sfzcode＝input(″请输入身份证号：″)
sfz1＝sexpd(sfzcode)
sfz1.isxb()
(1)程序运行时，若输入的18位身份证号为“330425198002251269”，则输出结果为____________________________。
(2)完善isxb(self)操作中的程序代码。
课时3　抽象数据类型
1.B　[Python的一个内置类型也可以看作是一个抽象数据类型，因此不正确的是B。]
2.C　[使用抽象数据类型编写的程序结构清晰、层次分明，因此A选项错误；抽象数据类型的模块化特点，在程序设计中容易纠正，具有良好的维护性，因此B选项错误；使用抽象数据类型编写程序时，因为算法设计与数据结构设计的隔开，降低了算法复杂度，同时允许数据结构的自由选择，给了算法的优化空间，提高了程序运行的效率，因此D选项错误；由于抽象数据类型的表示和实现都可以封装起来，便于移植和重用，是正确的。因此，答案为C。]
3.D　[执行代码“print(sstr1.concat(″is so easy！″))”，输出结果为“Python is so easy！”，因此，答案为D。]
4.D　[根据xadd操作中的语句可知，程序运行后的结果为8/15，因此，答案为D。]
5.(1)8 9 10　(2)①self.queue.insert(0，data)　②return self.queue.pop()
解析　本题主要考查的是用抽象数据类型表示队列操作。队列的特点是先进先出，元素入队时是从队列的首部插入，因此代码为self.queue.insert(0，data)；②处代码为出队操作，通过pop()方法实现，将元素从队尾取出，因此代码为return self.queue.pop()。
6.(1)身份证号为：330425198002251269 是位女士
(2)isxb(self)操作中的程序代码如下：
if xbcode % 2＝＝1：
print(″身份证号为：″，self.code，″是位男士。″)
else：
print(″身份证号为：″，self.code，″是位女士。″)
解析　本题主要考查的是ADT的实际应用。(1)身份证号330425198002251269的第17位上的数字是6，是偶数，因此该身份证号的人的性别是位女士，参考输出示例可知，输出结果为“身份证号为：330425198002251269 是位女士。”。(2)isxb(self)操作中的代码的功能是：根据身份证号的第17位上(索引位置为16)的数字的奇偶性来判断性别，因此使用if语句来实现，方法不唯一，只要输出结果正确即可。

展开更多......

收起↑