当前位置：问答库＞考研试题

一、选择题

1． 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。

I. 简单选择排序II. 希尔排序III. 快速排序IV . 堆排V . 二路归并排序

A. 仅 I 、III 、IV

B. 仅 I 、II 、III

C. 仅 II 、III 、IV

D •仅III 、IV 、V

【答案】A 。

【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。

2． 算法的计算量的大小称为计算的（ ）。

A. 效率

B. 复杂性

C. 现实性

D. 难度

【答案】B

【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。

3． 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。

A.3, 5，12，8, 28，20, 15，22，19

B.3, 5, 12, 19, 20, 15, 22, 8, 28

C.3, 8, 12, 5, 20, 15, 22, 28, 19

D.3, 12, 5, 8, 28, 20, 15, 22, 19

【答案】A

【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）〜（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。

4． 下列关于IP 路由器功能的描述中，正确的是（ ）。

I. 运行路由协议，设置路由表；II. 监测到拥塞时，合理丢弃IP 分组；III. 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失；IV . 根据收到的IP 分组的目的IP 地址，将其转发到合适的输出线路上。

A. 仅III 、IV

B. 仅 I 、II 、III

C. 仅 I 、II 、IV

D.I 、II 、III 、IV

【答案】C 。

【解析】路由器的主要功能是路由和转发，因此I 和IV 是正确的，而针对II 和III ，可以从ICMP 协议的差错控制出发，注意检测到拥塞时，合理丢弃IP 分组，并回传ICMP 源抑制报文，II 是正确的，而III 对收到的IP 分组头进行差错校验，确保传输的IP 分组不丢失，差错校验是正确的，但网络层不保证IP 分组不丢失，也就是不可靠的，因此III 的说法错误，正确的说法仅I 、II 、IV , 因此答案是C 。

5． 下列选项中，不可能在用户态发生的事件是（ ）。

A. 系统调用

B. 外部中断

C. 进程切换

D. 缺页

【答案】C 。

【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设

，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）

运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制

，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）

是在内核态（进程调度）发生的。

6． 在有向图G 的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是（ ） 。

A.G 中有弧 B.G 中有一条从V i 到V j 的路径

C.G 中没有弧

【答案】D

【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从V j 到V i 的路径，则在拓扑序列中V i 不可能在V j 前。