2017年齐鲁工业大学计算机应用技术研究所872数据结构考研题库
● 摘要
一、选择题
1． 下列选项中，不可能是快速排序第2趟排序结果的是（ ）
A.2, 3, 5, 4, 6, 7, 9
B.2, 7, 5, 6, 4, 3, 9
C.3, 2, 5, 4, 7, 6, 9
D.4, 2, 3, 5, 7, 6, 9
【答案】C
【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果
2． 单级中断系统中，中断服务程序内的执行顺序是（ ）。
I 保护现场；II 开中断；III 关中断；IV 保存断点；V 中断事件处理；VI 恢复现场；VII 中断返回
【答案】A
【解析】程序中断有单级中断和多级中断之分，单级中断在CPU 执行中断服务程序的过程中不能被打断， 即不允许中断嵌套。保存断点与关中断的任务是由硬件（中断隐指令）完成的，所以在单级中断系统中，中断服 务程序内应完成的任务有：①保存现场；②中断事件处理；③恢复现场；④开中断；⑤中断返回。
3． 假设某计算机的存储系统由Cache 和主存组成。某程序执行过程中访存1000次，其中访问Cache 缺失（未命中）50次，则Cache 的命中率是（ ）。
A.5%
B.9.5%
C.50%
D.95%
【答案】D
【解析】Cache 的命中率
次数，程序总访存次数
式可得：H=（1000-50）/1000=95%。
，其中为访问Cache 的次数，为访存主存的所以根据公, 程序访存次数减去失效次数就是访问Cache 的次数
4． 在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理
B. 数据格式转换
C. 路由选择
D. 可靠数据传输
【答案】B
【解析】应用层的相邻层即为表示层，表示层负责管理数据的压缩、加密与解密、格式装换等，故答案为B 。
5． 下列选项中，不可能在用户态发生的事件是（ ）。
A. 系统调用
B. 外部中断
C. 进程切换
D. 缺页
【答案】C 。
【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设
，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）
运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制
，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）
是在内核态（进程调度）发生的。
6． —个栈的入栈序列为其出栈序列是
的个数是（ ）
A.n-3
B.n-2
C.n-1
D. 无法确定
【答案】C
【解析】除了3本身以外，其他的值均可以取到，因此可能取值的个数为n-1。
7． 广义表 则式子的值为（ ）。
【答案】D
head 操作就是得到广义表中第一个的原子。【解析】
若，则则可能取值操作就是得到除第一个原子外剩下元
素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。
8． 假定不采用Cache 和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是（ ）。
A. 每个指令周期中CPU 都至少访问内存一次
B. 每个指令周期一定大于或等于一个CPU 时钟周期
C. 空操作指令的指令周期中任何寄存器的内容都不会被改变
D. 当前程序在每条指令执行结束时都可能被外部中断打断
【答案】C
【解析】本题涉及的概念比较多。首先，如果不采用Cache 和指令预取技术，每个指令周期中至少要访问内 存一次，即从内存中取指令。其次，指令有的简单有的复杂，每个指令周期总大于或等于一个CPU 时钟周期。第三，即使是空操作指令，在指令周期中程序计数器PC 的内容也会改变为取下一条指令做准备。第四，如果机器处于“开中断”状态，在每条指令执行结束时都可能被新的更高级的中断请求所打断。所以应选择选项C 。
9． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。
A.245Mbps
B.979Mbps C. D.
【答案】D
【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到的时间用来刷新
1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：
10．对序
列用希尔排序方法排序，经一趟后序列变
为
则该次采用的增量是（ ）。
A.1
B.4
C.3
D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。
11．设X 是树T 中的一个非根结点，B 是T 所对应的二叉树。在B 中，X 是其双亲的右孩子，下列结论正确的是（ ）。
A. 在树T 中，X 是其双亲的第一个孩子