计算机学科专业基础综合数据结构-非统考补充内容：串、数组和稀疏矩阵、树与二叉树(一)

计算机学科专业基础综合数据结构-非统考补充内容：串、数组和稀疏矩阵、树与二叉树(一)(总分：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，该树的高度至少为______。

∙ 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.C.D. √解析：[解析] 对于二叉树中的某个结点，其深度是从根算起的，而高度是从叶结点算起的。

一个叶结点的高度为1，其他任意一个结点的高度等于其左、右子树高度中的大值再加1。

此结点从上向下算是第4层，从下向上算也是第4层，由此可知高度为7。

4.一个深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组R[n]中，则n应至少是______。

∙ A.2k∙ B.2k+1∙ C.2k-1∙ D.2k（分数：2.00）A.B.C. √D.解析：[解析] 深度为k且只有k个结点的二叉树是一棵单支树。

本题需要计算可以保证存储这样一棵二叉树的最小空间，因此要找到所有这种单支二叉树中占用存储空间最大的那一棵，正好对应一棵所有结点的左子树均为空的单枝树，此时的二叉树所需要的存储空间恰恰和与其高度相同的满二叉树相同，需要2k-1个结点单元。

5.后序序列与层次序列相同的非空二叉树是______。

∙ A.满二叉树∙ B.完全二叉树∙ C.单支树∙ D.只有根结点的树（分数：2.00）A.B.C.D. √解析：[解析] 对二叉树进行后序遍历的规则是LRV(左、右、根)，在多数情况下遍历结果显然与层次遍历的结果不同，只有当树中仅含有一个结点的情形下，两者才有相同的遍历结果。

6.对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右子女的编号，同一结点的左、右子女中，其左子女编号小于其右子女编号，则可采用______遍历实现二叉树的结点编号。

∙ A.先序∙ B.中序∙ C.后序∙ D.层次序（分数：2.00）B.C. √D.解析：[解析] 由于后序遍历的规则是LRV(左、右、根)，因此按照后序遍历框架设置计数器对结点进行编号即可得到根大于右大于左的编号结果。

7.在一个非空二叉树的中序序列中，根结点的右边______。

∙ 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.右指针一定为空∙ C.左右指针均为空∙ D.左右指针均不为空（分数：2.00）A.B. √C.D.解析：[解析] 排序二叉树的结点结构由3部分构成，其中左指针指向比该结点值小的结点，右指针指向比该结点值大的结点。

整棵树中关键字最大的结点位于二叉排序树的最右下的位置上(注意此结点有可能不是叶子结点)。

11.折半查找和二叉排序树的时间性能______。

∙ A.相同∙ B.有时不相同∙ C.完全不同∙ D.随机分布（分数：2.00）A.B. √C.D.解析：[解析] 可以利用判定树来对折半查找进行性能分析，其平均情况和最坏情况下的时间复杂度都是O(log2n)。

对于二叉排序树，由于输入数据顺序的不同可能导致构造的树形不同，因此其查找性能与数据的输入顺序有关，最好情况下的时间复杂度与折半查找相同；但最坏情况下，即形成了单支树，其时间复杂度为O(n)。

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.解析：[解析] 用n个输入数据构造出来的哈夫曼树共有2n-1个结点，其中叶结点有n个，度为2的非叶结点有n-1个，不存在度为1的结点。

14.对于n(n≥2)个权值不同的字符构造的哈夫曼树，下面关于该哈夫曼树的叙述中错误的是______。

∙ 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的二叉树中只有度为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固定时，让每一层的结点数达到最少，就可使二叉树的结点总数达到最少。

此时，除第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=248个结点。

19.设完全二叉树的第6层有24个叶结点，则此树最多有______个结点。

∙ A.78∙ B.79∙ D.81（分数：2.00）A.B. √C.D.解析：[解析] 根据完全二又树每层结点总数最大值的计算公式可以算出第6层最多有26-1=25=32个结点。

其中有24个叶结点，假设它们全部在该层靠右排列，那么在这一层还有32-24=8个非叶结点，由此，可推知第7层还有2×8=16个叶结点，因为上一层靠左的那8个结点都有两个孩子，综上所述可得，该完全二叉树最多有1+2+4+8+16+32+16=79个结点。

20.具有1000个结点的完全二叉树的次底层的叶结点个数为______。

∙ A.11∙ B.12∙ C.24∙ D.36（分数：2.00）A. √B.C.D.解析：[解析] 由完全二叉树层数计算公式[*]可以计算出具有1000个结点的完全二叉树有10层。

该树上面9层是满的，有29-1=511个结点。

再结合叶结点与双分支结点数关系式n0=n2+1(n0是叶子结点数，n2是双分支结点数)，n0+n2为奇数，当n为偶数时，n1=1。

因为结点总数已求得，所以可得等式n=n0+n1+n2=2n0-1+n1=1000。

由此可知，n0=500，它们中有1000-511=489个分布在第10层，11个分布在第9层，所以次底层(第9层)的叶结点有11个。

21.若在一棵完全二叉树中对所有结点按层次自上向下，同一层次自左向右进行编号，根结点的编号为0，现有两个不同的结点，它们的编号是p和q，那么判断它们在同一层的条件应是______。

A． B．C D．p/2==q/2（分数：2.00）A. √B.C.D.解析：[解析] 由结点层号计算公式可得编号为i(假设结点编号从0开始)的结点所在层号为[*]+1。

当两个结点位于同一层时，有[*]，即[*]。

注意，如果结点编号从1开始，则[*]。

22.在二叉树的二叉链表中，空指针数有______个，等于非空指针数加2。

选项中n为二叉树结点数，n1是单分支结点数，n2是双分支结点数。

∙ A.n+1∙ B.n1∙ C.n2（分数：2.00）A. √B.C.D.解析：[解析] 对于有n个结点的二叉树，用二叉链表存储，其二叉链表中有2n个指针，其中有n-1个指针指向二叉树结点，剩下n+1个指针为空，所以空指针数等于非空指针数加2。

23.在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子女结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。