2017年山东财经大学计算机科学与技术学院809计算机专业基础综合之数据结构考研冲刺密押题
● 摘要
一、填空题
1． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
2． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。
【答案】顺序
【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。
3． 模式串的next 函数值序列为_____。
【答案】01122312
4． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
5． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
6． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
7． 完善算法：求KMP 算法.next 数组。
END ； 【答案】
8． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
9． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
10．VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
二、选择题
11．程序段
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行
12．在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘I/O次数 B. 减少平均寻道时间 C. 提高磁盘数据可靠性 D. 实现设备无关性 【答案】A
【解析】访问磁盘的开销远远大于访问内存的开销。磁盘缓冲区便是利用主存中的存储空间，来暂存从磁盘中读出（或写入）的信息，频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。
次交换，即时间复杂度是