1、计算机学科专业基础综合数据结构-非统考补充内容：串、数组和稀疏矩阵、树与二叉树(一)及答案解析(总分：103.00，做题时间：90 分钟)一、B单项选择题/B(总题数：45，分数：103.00)1.一棵有 n 个结点的树的所有结点的度数之和为_。 A.n-1 B.n C.n+1 D.2n（分数：2.00）A.B.C.D.2.在二叉树中某一结点的深度为 3，高度为 4，该树的高度至少为_。 A.5 B.6 C.7 D.8（分数：2.00）A.B.C.D.3.在一棵满二叉树中，某结点的深度为 4，高度为 4，则可推知该满二叉树的高度为_。 A.4 B.5 C.6 D.7（分数：2.00）A.B.C
2、.D.4.一个深度为 k 且只有 k 个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组 Rn中，则 n 应至少是_。 A.2k B.2k+1 C.2k-1 D.2k（分数：2.00）A.B.C.D.5.后序序列与层次序列相同的非空二叉树是_。 A.满二叉树 B.完全二叉树 C.单支树 D.只有根结点的树（分数：2.00）A.B.C.D.6.对二叉树的结点从 1 开始连续编号，要求每个结点的编号大于其左、右子女的编号，同一结点的左、右子女中，其左子女编号小于其右子女编号，则可采用_遍历实现二叉树的结点编号。 A.先序 B.中序 C.后序 D.层次序（分数：2.00）A.B.C.D.7
3、.在一个非空二叉树的中序序列中，根结点的右边_。 A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点（分数：2.00）A.B.C.D.8.在下列各种次序的线索二叉树中，_对查找指定结点在该次序下的后序效率较差。 A.前序线索二叉树 B.中序线索二叉树 C.后序线索二叉树 D.层次序线索二叉树（分数：2.00）A.B.C.D.9.线索二叉树是一种_结构。 A.逻辑 B.逻辑和存储 C.物理 D.线性（分数：2.00）A.B.C.D.10.在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。 A.左指针一定为空 B.右指针一定为空
4、C.左右指针均为空 D.左右指针均不为空（分数：2.00）A.B.C.D.11.折半查找和二叉排序树的时间性能_。 A.相同 B.有时不相同 C.完全不同 D.随机分布（分数：2.00）A.B.C.D.12.在关键字值随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与_量级相同。 A.顺序查找 B.折半查找 C.前两者都不正确（分数：2.00）A.B.C.D.13.用 n 个权值构造出来的哈夫曼树共有_个结点。 A.2n-1 B.2n C.2n+1 D.n+1（分数：2.00）A.B.C.D.14.对于 n(n2)个权值不同的字符构造的哈夫曼树，下面关于该哈夫曼树的叙述中错误的是_。
5、A.该树一定是一棵完全二叉树 B.树中一定没有度为 1 的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任何一个非叶结点的权值一定不小于下一层任意一个结点的权值（分数：2.00）A.B.C.D.15.如果 T2是由有序树 T 转换成的二叉树，那么 T 中结点的先根遍历序列对应 T2中结点的_遍历序列。 A.前序 B.中序 C.后序 D.层次序（分数：2.00）A.B.C.D.16.如果 T2是由有序树 T 转换成的二叉树，那么 T 中结点的后根遍历序列对应 T2中结点的_遍历序列。 A.前序 B.中序 C.后序 D.层次序（分数：2.00）A.B.C.D.17.设高度为 h 的二叉树
6、中只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为_，至多为 2h-1。 A.2h B.2h-1 C.2h+1 D.h+1 E.2h-1-1 F.2h-1 G.2h+1+1 H.2h+1（分数：2.00）A.B.C.D.18.一棵有 124 个叶结点的完全二叉树最多有_个结点。 A.247 B.248 C.249 D.250（分数：2.00）A.B.C.D.19.设完全二叉树的第 6 层有 24 个叶结点，则此树最多有_个结点。 A.78 B.79 C.80 D.81（分数：2.00）A.B.C.D.20.具有 1000 个结点的完全二叉树的次底层的叶结点个数为_。 A.1
7、1 B.12 C.24 D.36（分数：2.00）A.B.C.D.21.若在一棵完全二叉树中对所有结点按层次自上向下，同一层次自左向右进行编号，根结点的编号为0，现有两个不同的结点，它们的编号是 p 和 q，那么判断它们在同一层的条件应是_。 A B C （分数：2.00）A.B.C.D.22.在二叉树的二叉链表中，空指针数有_个，等于非空指针数加 2。选项中 n 为二叉树结点数，n 1是单分支结点数，n 2是双分支结点数。 A.n+1 B.n1 C.n2 D.n1+1（分数：2.00）A.B.C.D.23.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子女结点的位置都存在一个简单的
8、映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，则在采用三叉链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节。若采用顺序存储，则最后一个结点下标为 k(起始下标为 1)，那么_时采用顺序存储更节省空间。 A.d12n/(k-n) B.d12n/(k-n) C.d12n/(k+n) D.d12n/(k+n)（分数：2.00）A.B.C.D.24.二又树的叶结点在前序、中序和后序遍历过程中的相对顺序_。 A.发生改变 B.不发生改变 C.无法确定 D.以上均不正确（分数：2.00）A.B.C.D.25.在下列关于二叉树遍历的说法中，错误的是_。 A.在一棵二叉树
9、中，假定每个结点最多只有左子女、没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果 B.在一棵二叉树中，假定每个结点最多只有左子女、没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果 C.在一棵二叉树中，假定每个结点最多只有左子女、没有右子女，对它分别进行前序遍历和按层次遍历，则具有相同的遍历结果 D.在一棵二叉树中，假定每个结点最多只有右子女、没有左子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果（分数：2.00）A.B.C.D.26.在下列关于二叉树遍历的说法中，正确的是_。 A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定
10、是该子树的前序遍历结果序列的最后一个结点 B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点 C.若有一个叶结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点 D.若有一个叶结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点（分数：2.00）A.B.C.D.27.设一棵二叉树的中序序列为 badce，后序遍历为 bdeca，则该二叉树前序遍历的顺序是_。 A.adbec B.decab C.debac D.abcde（分数
11、：2.00）A.B.C.D.28.设一棵二叉树的前序序列为 abdecf，后序序列为 debfca，则该二叉树中序遍历的顺序是_。 A.adbecf B.dfecab C.dbeacf D.abcdef（分数：2.00）A.B.C.D.29.前序为 ABC，后序为 CBA 的二叉树共有_棵。 A.1 B.2 C.3 D.4（分数：2.00）A.B.C.D.30.在 n 个结点的线索二叉树中，线索的数目是_。 A.n-1 B.n+1 C.2n D.2n-1（分数：2.00）A.B.C.D.31.将下图中的二叉树按中序线索化，结点 e 的右指针和结点 g 的左指针分别指向_。（分数：2.00）A.
12、B.C.D.32.一棵高度为 h 的 AVL 树，若其每个非叶结点的平衡因子都是 0，则该树共有_个结点。 A.2h-1-1 B.2h-1 C.2h-1+1 D.2h-1（分数：2.00）A.B.C.D.33.高度为 7 的 AVL 树最少有_个结点，最多有 127 结点。 A.12 B.21 C.33 D.54（分数：3.00）A.B.C.D.34.以下有关平衡二叉树的说法中正确的是_。 A.平衡二叉树是高度最小的二叉排序树 B.平衡二叉树一定是丰满树 C.平衡二叉树上任一结点的平衡因子不能超过 1 D.有 n 个结点的平衡二叉树的高度为 O(log2n)（分数：3.00）A.B.C.D.3
13、5.包含有 4 个结点的元素值互不相同的二叉排序树有_种。 A.4 B.6 C.10 D.14（分数：3.00）A.B.C.D.36.如下图所示的一棵二叉排序树，其查找成功的平均查找长度是_，查找不成功的平均查找长度是21/7。（分数：3.00）A.B.C.D.37.若一棵度为 m 的哈夫曼树有 n 个叶结点，则非叶结点的个数为_。 An-1 B C D （分数：3.00）A.B.C.D.38.由权值为 8，4，5，7 的 4 个叶结点构造一棵哈夫曼树，该树的带权路径长度为_。 A.24 B.36 C.48 D.72（分数：3.00）A.B.C.D.39.设 T 是哈夫曼二叉树，具有 5 个叶
14、结点，树 T 的高度最高可以是_。 A.3 B.4 C.5 D.6（分数：3.00）A.B.C.D.40.在哈夫曼编码中，若编码长度只允许小于或等于 4，则除了已知两个字符编码为 0 和 10 外，还可以最多对_个字符编码。 A.3 B.4 C.5 D.6（分数：3.00）A.B.C.D.41.在具有 n(n1)个结点的 k 叉树中，有_个空指针。 A.kn+1 B.(k-1)n+1 C.kn-1 D.kn（分数：3.00）A.B.C.D.42.一棵含有 n 个结点的 k 叉树，可能达到的最大深度为_，最小深度为 logk(n(k-1)+1)。 A.logk(n(k-1)+1) B.logk(
15、nk-1)+1 C.k D.n（分数：3.00）A.B.C.D.43.设森林 F 对应的二叉树为 B，它有 m 个结点。B 的根为 p，p 的右子树中结点个数为 n，则森林 F 中第一棵树的结点个数是_。 A.m-n B.m-n-1 C.n+1 D.无法确定（分数：3.00）A.B.C.D.44.设森林中有 3 棵树，第一、第二和第三棵树中的结点个数分别为 m1、m 2和 m3。那么在由该森林转化成的二叉树中根结点的右子树上有_个结点。 A.m1+m2 B.m2+m3 C.m1+m3 D.m1+m2+m3（分数：3.00）A.B.C.D.45.一棵 124 个叶结点的完全二叉树，最多有_个结点
16、。 A.247 B.248 C.249 D.250 E.251（分数：3.00）A.B.C.D.计算机学科专业基础综合数据结构-非统考补充内容：串、数组和稀疏矩阵、树与二叉树(一)答案解析(总分：103.00，做题时间：90 分钟)一、B单项选择题/B(总题数：45，分数：103.00)1.一棵有 n 个结点的树的所有结点的度数之和为_。 A.n-1 B.n C.n+1 D.2n（分数：2.00）A. B.C.D.解析：解析 对于一棵树，所有结点的度之和等于分支总数，总分支数比总结点数少 1，因此有 n 个结点的树度之和等于 n-1。2.在二叉树中某一结点的深度为 3，高度为 4，该树的高度至
17、少为_。 A.5 B.6 C.7 D.8（分数：2.00）A.B. C.D.解析：解析 该结点处于第 3 层，从叶结点向上处于第 4 层。由根结点开始从上至下到该结点所在的层一共 3 层，而从该结点所在层开始，不包括该结点所在层到某一叶子结点一共 3 层，因此，至少有 6 层。3.在一棵满二叉树中，某结点的深度为 4，高度为 4，则可推知该满二叉树的高度为_。 A.4 B.5 C.6 D.7（分数：2.00）A.B.C.D. 解析：解析 对于二叉树中的某个结点，其深度是从根算起的，而高度是从叶结点算起的。一个叶结点的高度为 1，其他任意一个结点的高度等于其左、右子树高度中的大值再加 1。此结点
18、从上向下算是第 4层，从下向上算也是第 4 层，由此可知高度为 7。4.一个深度为 k 且只有 k 个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组 Rn中，则 n 应至少是_。 A.2k B.2k+1 C.2k-1 D.2k（分数：2.00）A.B.C. D.解析：解析 深度为 k 且只有 k 个结点的二叉树是一棵单支树。本题需要计算可以保证存储这样一棵二叉树的最小空间，因此要找到所有这种单支二叉树中占用存储空间最大的那一棵，正好对应一棵所有结点的左子树均为空的单枝树，此时的二叉树所需要的存储空间恰恰和与其高度相同的满二叉树相同，需要2k-1 个结点单元。5.后序序列与层次序列相
19、同的非空二叉树是_。 A.满二叉树 B.完全二叉树 C.单支树 D.只有根结点的树（分数：2.00）A.B.C.D. 解析：解析 对二叉树进行后序遍历的规则是 LRV(左、右、根)，在多数情况下遍历结果显然与层次遍历的结果不同，只有当树中仅含有一个结点的情形下，两者才有相同的遍历结果。6.对二叉树的结点从 1 开始连续编号，要求每个结点的编号大于其左、右子女的编号，同一结点的左、右子女中，其左子女编号小于其右子女编号，则可采用_遍历实现二叉树的结点编号。 A.先序 B.中序 C.后序 D.层次序（分数：2.00）A.B.C. D.解析：解析 由于后序遍历的规则是 LRV(左、右、根)，因此按照
20、后序遍历框架设置计数器对结点进行编号即可得到根大于右大于左的编号结果。7.在一个非空二叉树的中序序列中，根结点的右边_。 A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点（分数：2.00）A. B.C.D.解析：解析 由二叉树的中序遍历规则可以知道，在中序遍历序列中，根结点右边只含有右子树上的结点。8.在下列各种次序的线索二叉树中，_对查找指定结点在该次序下的后序效率较差。 A.前序线索二叉树 B.中序线索二叉树 C.后序线索二叉树 D.层次序线索二叉树（分数：2.00）A.B.C. D.解析：解析 对二叉树进行后序线索化后，寻找指
21、定结点的后序下的后序结点比较麻烦。因为它首先要找到这个结点的父结点，再到其父结点的右子树中找后序下的第一个结点。9.线索二叉树是一种_结构。 A.逻辑 B.逻辑和存储 C.物理 D.线性（分数：2.00）A.B.C. D.解析：解析 线索二叉树属于一种存储结构，与链表的表示有直接关系。10.在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。 A.左指针一定为空 B.右指针一定为空 C.左右指针均为空 D.左右指针均不为空（分数：2.00）A.B. C.D.解析：解析 排序二叉树的结点结构由 3 部分构成，其中左指针指向比该结点值小的结点，右指针指向比该结点值大的结点。整棵树中关键字最大
22、的结点位于二叉排序树的最右下的位置上(注意此结点有可能不是叶子结点)。11.折半查找和二叉排序树的时间性能_。 A.相同 B.有时不相同 C.完全不同 D.随机分布（分数：2.00）A.B. C.D.解析：解析 可以利用判定树来对折半查找进行性能分析，其平均情况和最坏情况下的时间复杂度都是O(log2n)。对于二叉排序树，由于输入数据顺序的不同可能导致构造的树形不同，因此其查找性能与数据的输入顺序有关，最好情况下的时间复杂度与折半查找相同；但最坏情况下，即形成了单支树，其时间复杂度为 O(n)。12.在关键字值随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与_量级相同。 A.顺序查找
23、 B.折半查找 C.前两者都不正确（分数：2.00）A.B. C.D.解析：解析 采用随机顺序进行数据输入来构造二叉排序树，可能减少数据的有序性，减少单支树的形成，查找性能可接近折半查找，时间复杂度的量级不变。13.用 n 个权值构造出来的哈夫曼树共有_个结点。 A.2n-1 B.2n C.2n+1 D.n+1（分数：2.00）A. B.C.D.解析：解析 用 n 个输入数据构造出来的哈夫曼树共有 2n-1 个结点，其中叶结点有 n 个，度为 2 的非叶结点有 n-1 个，不存在度为 1 的结点。14.对于 n(n2)个权值不同的字符构造的哈夫曼树，下面关于该哈夫曼树的叙述中错误的是_。 A.
24、该树一定是一棵完全二叉树 B.树中一定没有度为 1 的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任何一个非叶结点的权值一定不小于下一层任意一个结点的权值（分数：2.00）A. B.C.D.解析：解析 根据哈夫曼树的构造过程可以知道，哈夫曼树不一定是完全二叉树。15.如果 T2是由有序树 T 转换成的二叉树，那么 T 中结点的先根遍历序列对应 T2中结点的_遍历序列。 A.前序 B.中序 C.后序 D.层次序（分数：2.00）A. B.C.D.解析：解析 对树进行先根遍历，得到的遍历结果序列与对应二叉树的前序遍历的结果序列相等。16.如果 T2是由有序树 T 转换成的二叉树，那么
25、T 中结点的后根遍历序列对应 T2中结点的_遍历序列。 A.前序 B.中序 C.后序 D.层次序（分数：2.00）A.B. C.D.解析：解析 对树进行后根遍历，得到的遍历结果序列与对应二叉树的中序遍历的结果序列相等。17.设高度为 h 的二叉树中只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为_，至多为 2h-1。 A.2h B.2h-1 C.2h+1 D.h+1 E.2h-1-1 F.2h-1 G.2h+1+1 H.2h+1（分数：2.00）A.B. C.D.解析：解析 对于一棵除了叶子结点外，其余结点都有两个孩子结点的二叉树，在高度 h 固定时，让每一层的结点数达到最
26、少，就可使二叉树的结点总数达到最少。此时，除第 1 层有 1 个结点外，其他 h-1 层各有 2 个结点，所以二叉树至少有 2(h-1)+1=2h-1 个结点。反之，在高度 h 固定时，让每一层的结点数达到最多，就可使二叉树的结点总数达到最多，这就是满二叉树情形，结点个数可达 2h-1。18.一棵有 124 个叶结点的完全二叉树最多有_个结点。 A.247 B.248 C.249 D.250（分数：2.00）A.B. C.D.解析：解析 根据二又树的性质，叶子结点数目为双分支结点数加 1。当叶子结点数 n0=124 时，双分支结点数 n2=123，因此，此完全二叉树最多可有 124+123+1
27、=248 个结点。19.设完全二叉树的第 6 层有 24 个叶结点，则此树最多有_个结点。 A.78 B.79 C.80 D.81（分数：2.00）A.B. C.D.解析：解析 根据完全二又树每层结点总数最大值的计算公式可以算出第 6 层最多有 26-1=25=32 个结点。其中有 24 个叶结点，假设它们全部在该层靠右排列，那么在这一层还有 32-24=8 个非叶结点，由此，可推知第 7 层还有 28=16 个叶结点，因为上一层靠左的那 8 个结点都有两个孩子，综上所述可得，该完全二叉树最多有 1+2+4+8+16+32+16=79 个结点。20.具有 1000 个结点的完全二叉树的次底层的
28、叶结点个数为_。 A.11 B.12 C.24 D.36（分数：2.00）A. B.C.D.解析：解析 由完全二叉树层数计算公式*可以计算出具有 1000 个结点的完全二叉树有 10 层。该树上面 9 层是满的，有 29-1=511 个结点。再结合叶结点与双分支结点数关系式 n0=n2+1(n0是叶子结点数，n 2是双分支结点数)，n 0+n2为奇数，当 n 为偶数时，n 1=1。因为结点总数已求得，所以可得等式n=n0+n1+n2=2n0-1+n1=1000。由此可知，n 0=500，它们中有 1000-511=489 个分布在第 10 层，11 个分布在第 9 层，所以次底层(第 9 层)
29、的叶结点有 11 个。21.若在一棵完全二叉树中对所有结点按层次自上向下，同一层次自左向右进行编号，根结点的编号为0，现有两个不同的结点，它们的编号是 p 和 q，那么判断它们在同一层的条件应是_。 A B C （分数：2.00）A. B.C.D.解析：解析 由结点层号计算公式可得编号为 i(假设结点编号从 0 开始)的结点所在层号为*+1。当两个结点位于同一层时，有*，即*。注意，如果结点编号从 1 开始，则*。22.在二叉树的二叉链表中，空指针数有_个，等于非空指针数加 2。选项中 n 为二叉树结点数，n 1是单分支结点数，n 2是双分支结点数。 A.n+1 B.n1 C.n2 D.n1+
30、1（分数：2.00）A. B.C.D.解析：解析 对于有 n 个结点的二叉树，用二叉链表存储，其二叉链表中有 2n 个指针，其中有 n-1 个指针指向二叉树结点，剩下 n+1 个指针为空，所以空指针数等于非空指针数加 2。23.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子女结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，则在采用三叉链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节。若采用顺序存储，则最后一个结点下标为 k(起始下标为 1)，那么_时采用顺序存储更节省空间。 A.d12n/(k-n) B.d12n/(k-
31、n) C.d12n/(k+n) D.d12n/(k+n)（分数：2.00）A. B.C.D.解析：解析 在三叉链表中，每个结点占用的字节数是 d+43=d+12。若二叉树有 n 个结点，总共三叉链表需要(d+12)n 个字节。相应的顺序存储情形下，若最后一个结点下标为 k(起始下标为 1)，则需要dk 个字节，只有当 dk(d+12)n，即 d12n/(k-n)时使用顺序存储才更节省空间。24.二又树的叶结点在前序、中序和后序遍历过程中的相对顺序_。 A.发生改变 B.不发生改变 C.无法确定 D.以上均不正确（分数：2.00）A.B. C.D.解析：解析 为了解释这个问题，这里规定对于任意一
32、棵二叉树，标记访问根结点为 V，标记遍历根的左子树为 L，标记遍历根的右子树为 R，由此可得前序遍历顺序为 VLR，中序遍历顺序为 LVR，后序遍历顺序为 LRV，可以看出，对于 3 种遍历方式，遍历指针在二叉树中走过的左、右子树的次序都相同，都是先左后右，由此可知所有叶结点在遍历时访问的先后次序都相同。就是说，它们在各种遍历算法结果序列中的相对次序都相同。25.在下列关于二叉树遍历的说法中，错误的是_。 A.在一棵二叉树中，假定每个结点最多只有左子女、没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的遍历结果 B.在一棵二叉树中，假定每个结点最多只有左子女、没有右子女，对它分别进行中序
33、遍历和后序遍历，则具有相同的遍历结果 C.在一棵二叉树中，假定每个结点最多只有左子女、没有右子女，对它分别进行前序遍历和按层次遍历，则具有相同的遍历结果 D.在一棵二叉树中，假定每个结点最多只有右子女、没有左子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果（分数：2.00）A. B.C.D.解析：解析 除叶结点外，所有结点都只有左孩子、没有右孩子的二叉树是一棵左斜单支树，遍历过程中少了对右子树的遍历。在这种情况下，前序遍历结果和后序遍历结果正好相反，所以 A 错。中序遍历结果与后序遍历结果相同，前序遍历结果与层次遍历结果相同。选项 D 是右斜单支树，遍历过程少了对左子树的遍历，前序遍
34、历结果与中序遍历结果相同。26.在下列关于二叉树遍历的说法中，正确的是_。 A.若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点 B.若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点 C.若有一个叶结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点 D.若有一个叶结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点（分数：2.00）A.B.C. D.解析：解析 对
35、于二叉树的中序遍历，其遍历序列中的最后一个结点一定是从根开始沿右指针走到底的结点，如下图图 a 中的 c，设用指针 p 指向此中序遍历最后结点。若结点 p 不是叶结点(其左子树非空)，则前序遍历的最后一个结点必在它的左子树中，如图 a 中的 f，所以选项 A 和 B 错。若结点 p 是叶结点，如图 b 中的 f，则前序与中序遍历的最后一个结点都是它，选项 C 对。如果中序遍历的最后一个结点不是叶结点，它有一个左孩子且是叶子结点，如图 a 中的 c，假设其左孩子由 q 指向，则 q 是前序遍历的最后一个结点，但不是中序遍历中的最后一个结点，如图 a 中的 f，因此选项 D 错。*27.设一棵二叉
36、树的中序序列为 badce，后序遍历为 bdeca，则该二叉树前序遍历的顺序是_。 A.adbec B.decab C.debac D.abcde（分数：2.00）A.B.C.D. 解析：解析 由二叉树的后序遍历序列和中序遍历序列即可唯一地确定这棵二叉树。做法如下：首先用后序遍历序列确定根结点，利用得到的根结点对中序遍历序列分割根以及其左、右子树得到左右子树的中序遍历子序列。按照同样的方法递归处理每一个子序列即可还原出这棵二叉树。确定原二叉树后即可得到前序遍历序列为 abcde。28.设一棵二叉树的前序序列为 abdecf，后序序列为 debfca，则该二叉树中序遍历的顺序是_。 A.adbe
37、cf B.dfecab C.dbeacf D.abcdef（分数：2.00）A.B.C. D.解析：解析 由二叉树的前序遍历序列和后序遍历序列不能唯一地确定这棵二叉树。但是利用二叉树前序遍历序列的第一个结点和后序遍历序列的最后一个结点为二叉树的根结点的特性，可以确定一棵二叉树，它的中序遍历序列为 dbeacf。29.前序为 ABC，后序为 CBA 的二叉树共有_棵。 A.1 B.2 C.3 D.4（分数：2.00）A.B.C.D. 解析：解析 含有 3 个结点且前序遍历序列为 ABC 的二叉树一共有 5 种不同形态，其中后序为 CBA 的有4 种，都是单支树，如下图左边所示的 4 棵二叉树。*
38、30.在 n 个结点的线索二叉树中，线索的数目是_。 A.n-1 B.n+1 C.2n D.2n-1（分数：2.00）A.B. C.D.解析：解析 线索二叉树中共有 2n 个指针，子女指针有 n-1 个，其余的 n+1 个指针为线索。31.将下图中的二叉树按中序线索化，结点 e 的右指针和结点 g 的左指针分别指向_。（分数：2.00）A.B.C.D. 解析：解析 进行中序线索化后得到下图所示的结果。在这棵线索二叉树中结点 e 的右指针是中序后继线索，它指向结点 c；结点 g 的左指针是中序前驱线索，它指向结点 a。*32.一棵高度为 h 的 AVL 树，若其每个非叶结点的平衡因子都是 0，则
39、该树共有_个结点。 A.2h-1-1 B.2h-1 C.2h-1+1 D.2h-1（分数：2.00）A.B.C.D. 解析：解析 当一棵 AVL 树中的所有非叶结点的平衡因子都是 0 的时候，说明它每个非叶子结点的左、右子树都是一样高，则整棵树是一棵满二叉树。高度为 h 的满二叉树的结点个数等于 2h-1。33.高度为 7 的 AVL 树最少有_个结点，最多有 127 结点。 A.12 B.21 C.33 D.54（分数：3.00）A.B.C. D.解析：解析 AVL 树的最少结点数与树的高度 h 有如下关系式：设 Nh是高度为 h 的 AVL 树的最少结点数，则有 N0=0，N 1=1，N
40、h=Nh-1+Nh-2+1(h2)。如此可得N2=N1+N0+1=2，N 3=N2+N1+1=4，N 4=N3+N2+1=7，N 5=N4+N3+1=12，N 6=20，N 7=33。高度为 h 的 AVL 的最多结点数为 2h-1，为满二叉树情形。当 h=7 时，有 27-1=127。34.以下有关平衡二叉树的说法中正确的是_。 A.平衡二叉树是高度最小的二叉排序树 B.平衡二叉树一定是丰满树 C.平衡二叉树上任一结点的平衡因子不能超过 1 D.有 n 个结点的平衡二叉树的高度为 O(log2n)（分数：3.00）A.B.C.D. 解析：解析 有 n 个结点的平衡二叉树的最小高度 hmin=
41、rlog2(n+1)l，最大高度 hmax1.44log 2(n+1)，因此选项 D 是正确的。由于平衡二叉树的中低层有可能没有填满，存在度为 1 的结点，只要每个结点的两棵子树的高度差的绝对值不超过 1 即可，所以其高度有可能不是最小，因此选项 A 不对。丰满树即理想平衡树，要求除最底层外其他层都是满的，平衡二叉树没有这样高的要求，因此选项 B 不对。对于 C 选项，应该是平衡二叉树上任一结点的平衡因子的绝对值不能超过 1。35.包含有 4 个结点的元素值互不相同的二叉排序树有_种。 A.4 B.6 C.10 D.14（分数：3.00）A.B.C.D. 解析：解析 含有 n 个结点的二叉排序
42、树，其中序遍历序列都是一样的，前序遍历序列不同则对应了不同形状的二叉排序树，不同形态的个数可以用 catalan 函数计算： catalan 函数为*(n 为结点数)。 当 n=4 时，有*。36.如下图所示的一棵二叉排序树，其查找成功的平均查找长度是_，查找不成功的平均查找长度是21/7。（分数：3.00）A.B.C. D.解析：解析 该二叉排序树的查找成功的平均查找长度为 ASL=(11+22+32+41)/6=15/6。为了计算查找不成功的平均查找长度需要构造判定树，如下图所示。每次查找不成功，一定是从根结点走到了一个空指针位置，等于从根到空指针的路径长度，因此查找不成功的平均查找长度为
43、 ASL=(22+33+42)/7=21/7。*37.若一棵度为 m 的哈夫曼树有 n 个叶结点，则非叶结点的个数为_。 An-1 B C D （分数：3.00）A.B.C. D.解析：解析 类比度为 2 的哈夫曼树，一棵度为 m 的哈夫曼树应只有度为 m 和度为 0 的结点，设度为 m的结点有 nm个，度为 0 的结点有 n 个，总结点数为 N，N=n m+n0。因有 N 个结点的哈夫曼树有 N-1 条分支，则 mnm=N-1=nm+n-1，整理得(m-1)n m=n-1，n m=(n-1)/(m-1)。38.由权值为 8，4，5，7 的 4 个叶结点构造一棵哈夫曼树，该树的带权路径长度为_
44、。 A.24 B.36 C.48 D.72（分数：3.00）A.B.C. D.解析：解析 由权值为 8，4，5，7 的 4 个叶结点构造出的一棵哈夫曼树如下图所示。它的带权路径长度WPL 的计算有两种方法：一是先求每一个叶结点的带权路径长度，加起来得到WPL=42+52+72+82=48；另一种方法是把所有非叶结点的权值加起得到 WPL=24+9+15=48。*39.设 T 是哈夫曼二叉树，具有 5 个叶结点，树 T 的高度最高可以是_。 A.3 B.4 C.5 D.6（分数：3.00）A.B.C. D.解析：解析 哈夫曼二叉树是只有度为 2 和度为 0 的结点的二叉树，有 n 个叶结点，就有
45、 n-1 个非叶结点，其最大高度是 n，即从第 1 层起到次底层止，每层有一个非叶结点，最底层有两个叶结点。例如，下图所示的哈夫曼树，n=5，叶结点的权值为1 2，2 2，3 2，4 2，5 2，该哈夫曼树的高度是 5，所以具有 5 个叶结点的哈夫曼树的高度最高可以是 5。*40.在哈夫曼编码中，若编码长度只允许小于或等于 4，则除了已知两个字符编码为 0 和 10 外，还可以最多对_个字符编码。 A.3 B.4 C.5 D.6（分数：3.00）A.B. C.D.解析：解析 根据哈夫曼树生成哈夫曼编码的规则可知，若哈夫曼编码的长度只允许小于或等于 4，则哈夫曼树的高度为 5。已知一个字符编码为 0，另一个字符编码为 10，这说明第 2 层和第 3 层各有一个叶结点，为使得该树从第 3 层起能够对尽可能多的字符编码，余下的二叉树应是满二叉树，如下图所示。最底层可以有 4 个叶结点，最多可以再对 4 个字符编码。*41.在具有 n(n1)个结点的 k 叉树中，有_个空指针。 A.kn+1 B.(k-1)n+1 C.kn-1 D.kn（分数：3.00）A.B. C.D.解析：解析 有 n 个结点
