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

一、选择题

1． 数据序列结果。

A. 选择排序 B. 起泡排序 C. 插入排序 D. 堆排序 【答案】C

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

2． 有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。

A.543612 B.453126 C.346521 D.234156 【答案】C

【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。

3． —

组记录的关键码为

准得到的一次划分结果为（ ）。

【答案】C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为

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

则利用快速排序的方法，以第一个记录为基

一次划分结束。

4． 元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。

A.3 B.4 C.5 D.6

【答案】B

【解析】d 首先出栈后的状态如下图所示。

此时可有以下4种操作：

（1）e 进找后出栈，出梭序列为decba 。 （2）c 出找，e 进找后出栈，出找序列为dceba 。 （3）cb 出找，e 进找后出栈，出找序列为dcbea 。

（4）cba 出找，e 进找后出找，出找序列为dcbae 。

5． 在缺页处理过程中，操作系统执行的操作可能是（ ）。

I. 修改页表 II. 磁盘I/O III. 分配页框 A. 仅 I 、II B. 仅II C. 仅III D.I 、II 和III 【答案】D

【解析】首先我们要考虑的是，为什么会发生缺页中断? 当然，在一个采用虚拟存储管理技术的系统中，程 序是部分装入的，还有部分是处于外存上的，因此，当需要访问那部分位于外存上的代码或数据时，系统会产生 缺页中断。产生缺页中断的目的是要将位于外存上的代码或数据装入内存，据此，缺页中断接下去所做的工作就是首先要在内存中找到空闲页框并分配给需要访问的页（若没有空闲的页面则要调用页面置换程序找到一处页 面，将该页面的内容处理掉，或回写，分配妥当以后，缺页中断处理程序调用设备磁盘，或覆盖掉，然后将此页分配给需要访问的页）

驱动程序做磁盘1/0, 将位于外存（一般是磁盘）上的页面调入内存，调入后转身去修改 页表，将，将物理页表中代表该页是否在内存的标志位（一般称为存在位或有效位、在位位）修改为“真”

页框号填入相应位置，若必要还需修改其它相关表项等。完成上述任务后，缺页中断处理程序返 回，继续程序的执行。 从上述过程可以看出，涉及的相关处理非常多，因此，答案就显而易见了。

6． 二叉树在线索化后，仍不能有效求解的问题是（ ）。

A. 前序线索二叉树中求前序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 【答案】D

【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。

7． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。

A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排序 【答案】B

【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。

8． 将一个的三对角矩阵，按行优先存入一维数组中，A 中元素（即该元素下标

A.198 B.195 C.197

【答案】B

在B 数组中的位置K 为（ ）。

【解析】将对角矩阵存入三对角矩阵压缩地址计算公式如下：

9． 最大容量为n 的循环队列，队尾指针是rear ，队头：front , 则队空的条件是（ ）。

A.

B.

C.

D. 【答案】B

【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采用