计算机学科专业基础综合数据结构-非统考补充内容：串、数组和稀疏矩阵、树与二叉树(一)
(总分：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.
 B.
 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）
 A.
 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.该树一定是一棵完全二叉树

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。