2018年东北石油大学计算机与信息技术学院702教育技术学之数据结构考研核心题库
● 摘要
一、单项选择题
1． 下列选项中, 会导致用户进程从态切换到内核的操作是（ ）
Ⅰ. 整数除以零
Ⅱ.sin （ ）函数调用
Ⅲ.read 系统调用
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。
2． 单级中断系统中, 中断服务程序内的执行顺序是（ ）。
Ⅰ保护现场; Ⅱ开中断; Ⅲ关中断; Ⅳ保存断点; Ⅴ中断事件处理; Ⅵ恢复现场; Ⅶ中断返回 A. B. C. D.
【答案】A
【解析】程序中断有单级中断和多级中断之分, 单级中断在CPU 执行中断服务程序的过程中不能被打断, 即不允许中断嵌套。保存断点与关中断的任务是由硬件(中断隐指令) 完成的, 所以在单级中断系统中, 中断服务程序内应完成的任务有:
①保存现场; ②中断事件处理; ③恢复现场; ④开中断; ⑤中断返回。
3． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
A.push ，pop ，push ，pop ，push ，pop
B.push ，push ，push ，pop ，pop ，pop
C.push ，push ，，pop ，pop ，push ，pop
D.push ，pop ，push ，push ，pop ，pop
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，
push 的数目始终大于等于pop 的数目。
4． 对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次釆用的增量是（ ）。
A.1
B.4
C.3
D.2
【答案】B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的增量是4。
5． 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 元素a , b , c , d , e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是（ ）。
A.b , a , c , d , e
B.d , b , a , c , e
C.d , b , c , a , e
D.e , c , b , a , d
【答案】C
【解析】根据题意, 队列两端都可以输入数据元素, 但是只能在一端输出数据元素, 这种队列为
输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队, 从而得出不可能的情况。
假设L 代表从左端入队, R 代表从右端入队, 出队都是从左端L 出。四个选项所给序列的进队操作序列分别为:
选项A.aL(或aR) , bL , cR , dR , eR
选项B.aL(或aR) , bL , cR , dL , eR
选项C. 不可能出现选项
D.aL(或aR) , bL , cL , dR , eL
6． 以下与数据的存储结构无关的术语是（ ）。
A. 循环队列
B. 链表
C. 哈希表
D. 栈
【答案】D
【解析】循环队列体现线性表是以顺序存储。用散列法存储的线性表称散列表。链表说明线性表是以链式结构存储的。栈不能体现出是顺序还是链式存储结构。
7． 下列选项中, 在用户态执行的是（ ）。
A. 命令解释程序
B. 缺页处理程序
C. 进程调度程序
D. 时钟中断处理程序
【答案】A
【解析】题目是问用户态执行, 可见是有关操作系统基本概念的问题。四个选项中, 用户唯一能面对的是命令解释程序, 缺页处理程序和时钟中断都属于中断, 在核心态执行, 而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口, 可以运行在用户态, 接受用户的命令操作控制。
8． 由3个“1”和5个“0”组成的8位二进制补码, 能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
D.-3
【答案】B
【解析】能表示的最小整数一定是负数, 符号位占用1个“1”; 负数的补码和原码的转化是:原码符号位不变, 数值部分按位取反, 末位加“1”。
因此最小的整数的补码是“10000011”, 原码为“111111101”, 即
9． 某字长为8位的计算机中, 已知整型变量x 、y 的机器数分别为
, A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
【解析】将x 左移一位, y 右移一位, 两个数的补码相加的机器数为11000000, 故答案选择A 。
10．下列选项中, 能缩短程序执行时间的措施是（ ）。
Ⅰ. 提高CPU 时钟频率
Ⅱ. 优化数据通路结构
Ⅲ. 对程序进行编译优化
A. 仅Ⅰ和Ⅱ
b. 仅Ⅰ和Ⅲ
c. 仅Ⅱ和Ⅲ
d. Ⅰ、Ⅱ和Ⅲ
【答案】D
【解析】一般说来, CPU 时钟频率(主频) 越高, CPU 的速度就越快; 优化数据通路结构, 可以有
。 。若整型变量, 则z 的机器数为（ ）