2017年南华大学计算机科学与技术学院881数据结构考研仿真模拟题
● 摘要
一、选择题
1． 设二维数组
（即m 行n 列）按行存储在数组
【答案】A 【解析】
前
的元素个数为
所以二维数组元素
在一维数组B
中的下标为
需要注意数组B 的下标是从0开始，还是从1开始。
2． 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（ ）。
A. 必定快 B. 不一定
C. 在大部分情况下要快 D. 取决于表递增还是递减 【答案】C
【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就快的多了。这类情况外折半都高于顺序查找。
3． 设有两个串S1和S2, 求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串 B. 判断是否相等 C. 模型匹配 D. 连接 【答案】C
【解析】常用的串的基本操作有七种，INDEX （s ，t ）是其中的定位函数，这种运算就是所说的模式匹配。
4． 下列选项中，能引起外部中断的事件是（ ）。
A. 键盘输入 B. 除数为0 C. 浮点运算下溢 D. 访存缺页 【答案】A
中，
则二维数组元素
在一维数组B 中的下标为（ ）。
【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。
5． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3, 当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5 B.2和4 C.4和2 D.5和1 【答案】B
【解析】入队操作的主要步骤
：个后
，
加入一个后，
再加入一
删除一个后
，
出队操作的主要步骤
：
6． 一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶结点
D. 其中度为2的结点最多为一个 【答案】C
【解析】前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树才有可能，所以本题的A 项和B 项均对，单支树的特点是只有一个叶结点，故C 项是最合适的。A 项或B 项都不全。
7． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串 B. 树 C. 广义表 D. 栈 【答案】C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
8． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4 B.5 C.6 D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个全二叉树的高度为
或
结点的完
由完全二叉树类推到完全三叉树可知，n 个结点的完全三
叉树的高度为
或
9． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。
A.lOMB/s B.20MB/S C.40MB/S D.80MB/S 【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4=20MB/s。 字节信息, 则总线带宽是4B ÷
10．在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
【答案】B 【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
11．最大容量为n 的循环队列，队尾指针是rear ，队头：front , 则队空的条件是（ ）。
A.
B.
C.
D. 【答案】B
【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采
用
来判定队满，其中
表示队列的长度。
12．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）过程的二叉树如下图所示。