2016年杭州电子科技大学通信工程学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 下列调整中，不可能导致饥饿现象的是（ ）
A. 时间片转移
B. 静态优先及调度
C. 非抢占式作业优先
D. 抢占式短作业优先
答:A
【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。
2． 对同一待排序列分别进行折半插入排序和直接插入排序， 两者之间可能的不同之处是（ ）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
答:D 。
【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，
而记录的移动次数不变。折半插入排序的时间复杂度仍为
所以两者之间的不同只可能是元素之间的比较次数。
3． 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。
A. 程序计数器
B. 程序状态字寄存器
C. 通用数据寄存器
D. 通用地址寄存器
答:B 。
【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关，而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序，并要求其去处理某一事件的一种常用手段。因此，除了要保护当前程序的地址，计数器（指针）和数据寄存器以外，还需要保存程序状态字。子程序调用是与当前进程有关，是正在运行的程序有意安排执行的，这一类调用发生的时间以及位置具有确定性，处于同一个进程内，因此不需要保存程序状态字。所
以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。
4． 若系统S1采用死锁避免方法，S2采用死锁检测方法，下列叙述中正确的是（ ）。
I . S1会限制用户申请资源的顺序
II. S1需要进行所需资源总量信息，而S2不需要
III. S1不会给可能导致死锁的进程分配资源，S2会
A. 仅
B. 仅
C. 仅
D.
答:
【解析】死锁避免的策略是：必须知道将来的资源需求，以寻找可能的安全允许顺序，如果不存在安全序列就阻塞；死锁检测的策略是：只要允许就分配资源，它指定期检查死锁是否已经发生，如果发生就通过剥夺解除死锁。两种方式都需要所需资源的总量信息，但S1是用于在分配资源时判断是否会导致死锁，而S2是用于检测是否出现死锁。
5． 某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）
A.9
B.10
C.11
D.12
答:B
【解析】2+3+4+1 = 10
6． 引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便地进行插入与删除
C. 为了能方便地找到双亲
D. 使二叉树的遍历结果唯一
答:A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
7． 当系统发生抖动（thrashing ）时，可以采取的有效措施是（ ）。
I. 撤销部分进程
II. 增加磁盘交换区的容量
III. 提高用户进程的优先级
A. 仅I
B. 仅 II
C. 仅III
D. 仅 I 、II
答:A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页
必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，
引起系统性能下降甚至崩溃。 引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交 换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统 来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情 况下增加物理内存
，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的 问条）
题，提高用户进程的优先级会使系统的状态更加恶化。
8． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ）型调整以使其平衡
答:C
【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2，则需要进行两次旋转（先右旋后左旋）。
9． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现找满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
答:A
10．对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：
第一趟：2，12，16, 5，10，88
第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88
则采用的排序方法可能是（ ）。
A. 起泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
答:A
【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次