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

一、选择题

1． 下列说法不正确的是（ ）。

A. 图的遍历是从给定的源点出发每个顶点仅被访问一次

B. 遍历的基本方法有两种：深度遍历和广度遍历

C. 图的深度遍历不适用于有向图

D. 图的深度遍历是一个递归过程

【答案】C

【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。

2． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）

A.1, 2, 1, 2

B.2, 2, 1, 1

C.3, 4, 2, 3

D.4, 4, 2, 2

【答案】C

【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。

3． 对同一待排序列分别进行折半插入排序和直接插入排序， 两者之间可能的不同之处是（ ）。

A. 排序的总趟数

B. 元素的移动次数

C. 使用辅助空间的数量

D. 元素之间的比较次数

【答案】D 。

【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，

而记录的移动次数不变。折半插入排序的时间复杂度仍为

所以两者之间的不同只可能是元素之间的比较次数。

4． 下列选项中，能引起外部中断的事件是（ ）。

A. 键盘输入

B. 除数为0

C. 浮点运算下溢

D. 访存缺页

【答案】A

【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。

5． 已知一算术表达式的中缀表达式为

【答案】D

【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。

6． 下列排序算法中，占用辅助空间最多的是（ ）。

A. 归并排序

B. 快速排序

C. 希尔排序

D. 堆排序

【答案】A

【解析】

归并排序的辅助空间为

快速排序所占用的辅助空间为堆排序所占 用的辅助空间为

7． 已知小根堆为8，15，10，21，34， 16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。

A.1

B.2

C.3

D.4

【答案】C

【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个

其后缀形式为（ ）。

有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15, 所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调

整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。

8． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。

A.0（n ） B.0（n+e） C.0（n*n） D.0（n*n*n）

【答案】B

【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0（n+e）

9． 下列选项中，在用户态执行的是（ ）。

A. 命令解释程序

B. 缺页处理程序

C. 进程调度程序

D. 时钟中断处理程序

【答案】A

【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。

10．数据序列

结果。

A. 选择排序

B. 起泡排序

C. 插入排序

D. 堆排序

【答案】C

【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。

11．下面关于哈希（Hash ，杂凑）查找的说法正确的是（ ）。

A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B. 除留余数法是所有哈希函数中最好的

C. 不存在特别好与坏的哈希函数，要视情况而定

D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可

【答案】C

只能是下列排序算法中的（ ）的两趟排序后的