2017年沈阳航空航天大学计算机学院805数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 已知循环队列存储在一维数组
rear 的值分别是（ ）。
A.0, 0
B.0, n-1
C.n-1, 0
D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素，若初始时队列为空，且要求第1 个进入队列的元素存储在A[0]处，则此时front 和rear 的值都为0。由于进队操作要执行（rear+1） % n，则初始 时front 的值为0、rear 的值为n-1。
2． 下列AOE 网表示一项包含8个活动的工程。通过同时加快若干进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（ ）
中，且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和
A.c 和e
B.d 和e
C.f 和d
D.f 和h
【答案】C
【解析】根据AOE 网的定义可知，同时缩短几条关键路径上的活动时间，可以缩短整个工期。
3． 某计算机有五级中断的顺序为
A.11110
B.01101
C.00011
D.01010 则中断屏蔽字为表示对级中断进行屏蔽。若中断响应优先级从高到低的顺序是且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。
【答案】D
【解析】由于B
排除掉。的中断处理优先级下降，屏蔽字中需要3个0, 所以可以将选项A 、
需要对开放，所以相应位应该为即为01010。
4． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
5． 由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。
A.-126
B.-125
C.-32
D.-3
【答案】B
；负数的补码和原码的转化是：【解析】能表示的最小整数一定是负数，符号位占用1个“1”
原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码
为“11111101”，即
6． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。
A.0（nlogn ）
B.O （logn ）
C.O （n ） D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为0（nlogn ）。
已知待排序的n 个元素可分为个组，每个组包含k 个元素，且任一组内的各元素均分别大干前一
7． 下列关于RISC 的叙述中，错误的是（ ）。
A.RISC 普遍采用微程序控制器
B.RISC 大多数指令在一个时钟周期内完成
C.RISC 的内部通用寄存器数量相对CISC 多
D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少
【答案】A
【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
8． 在下面的排序方法中，辅助空间为的是（ ）。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
【答案】D
9． 若
A.x+y
B.-x+y
C.x-y
D.-x-y
【答案】C
【解析】8位定点补码能表示的数的范围为：
A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补码能表示的数的范围，会发生溢出
10．对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
A.4
B.3
C.2
D.1
【答案】B
【解析】拓扑排序的步骤为：
（1）在有向图中选一个没有前驱的顶点并且输出它；
（2）从图中删除该顶点和以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。题中所给图有三个不同的拓扑棑序序列，分别为abced ，abecd ，aebcd 。
11．计算机硬件能够直接执行的是（ ）。
I .机器语言程序汇编语言程序硬件描述语言程序