2016年沈阳师范大学软件学院数据结构(同等学力加试)复试笔试最后押题五套卷
● 摘要
目录
2016年沈阳师范大学软件学院数据结构（同等学力加试）复试笔试最后押题五套卷（一） . .... 2 2016年沈阳师范大学软件学院数据结构（同等学力加试）复试笔试最后押题五套卷（二） . .. 10 2016年沈阳师范大学软件学院数据结构（同等学力加试）复试笔试最后押题五套卷（三） . .. 18 2016年沈阳师范大学软件学院数据结构（同等学力加试）复试笔试最后押题五套卷（四） . .. 26 2016年沈阳师范大学软件学院数据结构（同等学力加试）复试笔试最后押题五套卷（五） . .. 34
一、选择题
1．
某系统正在执行三个进程
例如下表所示。
和
各进程的计算（CPUCPUCPU ）时间和
时间比
为提高系统资源利用率，合理的进程优先级设置应（ ） A. B. C. D. 答:B
【解析】为了合理地设置进程优先级，应该将进程的CPU 利用时间和
时间做综合考虑，
故答案选B 。
2． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）
A. B. C. D. 答:D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
3． 从堆中删除一个元素的时间复杂度为（ ）。
答:B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
4． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表 B. 双链表
C. 带头结点的双循环链表 D. 单循环链表 答:A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进 行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
5． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。
A. 对称矩阵 B. 稀疏矩阵 C. 三角矩阵 D. —般矩阵 答:C
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序：①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在 图中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
6． 链表不具有的特点是（ ）。
A. 插入、删除不需要移动元素 B. 可随机访问任一元素 C. 不必事先估计存储空间 D. 所需空间与线性长度成正比 答:B
【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。
7． 设哈希表
长
哈希函
数表中已有4个结点
：其余地址为空，如用二次探测
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
答:D
【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
不再发生冲突。
8． 某机器有一个标志寄存器，其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF ，条件转移指令bgt （无符号整数比较大于时转移）的转移条件是（ ）。
A.CF+OF=0 B.SF+ZF=0 C.CF+ZF=0 D.CF+SF=0
计算后得地址：4，5，6，7。49计算后
答:C
【解析】判断无符号整数A>B成立，满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位，即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。
9． 连续存储设计时，存储单元的地址（ ）。
A. 一定连续 B. 一定不连续 C. 不一定连续
D. 部分连续，部分不连续 答:A
【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。
10．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。
A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法 答:A
【解析】选择排序的基本思想是：
第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和
分别变为新的有序区和新的无序区。
和
该趟排序
交换，使
将它与无序区的第1个记录
二、填空题
11．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
答:满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
12．数组的存储结构采用_____存储方式。
答:顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
13．有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
答:50; 4