2017年华北水利水电大学信息工程学院980计算机学科专业综合之数据结构考研强化模拟题
● 摘要
一、选择题
1． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B. C. D.
【答案】C
【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。
2． 若需在0（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
【答案】C
【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为
速排序。
3． 下列选项中，在
I.
A. 仅 I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 、III
【答案】D 。
【解析】
在
总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。
的有：归并排序、堆排序、shell 排序、快总线的数据线上传输的信息包括（ ）。
接口中的状态字III. 中断类型号 接口中的命令字
II.
4． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题题目的实际问题是，具有6层结点的平衡二叉树含有最少的结点数是多少。表示深度为h 的平衡二叉树中含有的最少结点数，有
由此可得对应的平衡二叉树如下图所示。
5． 已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。
A.39
B.52
C.111
D.119
【答案】C
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是-1=63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是=32个结点，已知有8个叶子结点，那么其余32-8=24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达-1+（-8）×2=lll。
6． 知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。
A.CBEFDA
B.FEDCBA
C.CBEDFA
D. 不定
【答案】A
【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B
的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。
7． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
【答案】C
【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组（行标，列标，值）。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。
8． 数组
A.55
B.45
C.36
D.16
【答案】B 中含有元素的个数（ ）。
【解析】该数组为三维数组。其个数为
9． 对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ） A.
B.
C.
D.
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小进行排序的，故答案是C 选项。
10．若将关键字1，2, 3, 4, 5, 6, 7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）
A.0
B.1
C.2
D.3
【答案】D
【解析】将图中给定的关键字序列依次插入到平衡树中，构成的平衡树如下图所示，由图可
相关内容
相关标签