2017年浙江工业大学教育科学与技术学院885数据结构(C语言版)之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 完善算法：求KMP 算法.next 数组。
END ； 【答案】
2． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行
排序，以达到整个序列有序。
3． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
4． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
5． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
6． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
7． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
【答案】（1）（2）
链表未到尾就一直进行
将当前结点作为头结点后的第一元素结点插入
在B
其中
队头和队尾指针分别为front 和rear , 则此循
8． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵，将代入得93。
9． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
10．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
二、选择题
11．以下说法错误的是（ ）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n 下，复杂度
的算法在时间上总是优于复杂度
的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A. （1） B. （1）, （2） C. （1）, （4） D. （3） 【答案】A
【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
12．，
用直接插入排序方法对下面4个序列进行排序（由小到大）元素比较次数最少的是（ ）。
【答案】C
13．某以太网拓扑及交换机当前转发表如下图所示，主机向主机发送1个数据帧，主机
A. B. C. D.
收到该帧后，向主机
发送一个确认帧，
交换机对这两个帧的转发端口分别是（ ）