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

一、单项选择题

1． 一个非空广义表的表尾（ ）。

A. 不能是子表

B. 只能是子表

C. 只能是原子

D. 是原子或子表

【答案】B

【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。

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

Ⅰ. 修改页表

Ⅱ. 磁盘

Ⅲ. 分配页框

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ

C. 仅Ⅲ

D. Ⅰ、Ⅱ和Ⅲ

【答案】D

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

缺页中断处理程序调用设备驱动程序做磁盘

, 将位于外存(一般是磁盘) 上的页面调入内存, 调入后转身去修改页表, 将页表中代表该页是否在内存的标志位(一般称为存在位或有效位、在位位) 修改为“真”, 将物理页框号填入相应位置, 若必要还需修改其它相关表项等。完成上述任务后, 缺页中断处理程序返回, 继续程序的执行。从上述过程可以看出, 涉及的相关处理非常多, 因此, 答案就显而易见了。

3． 可以用（ ）定义一个完整的数据结构。

A. 数据元素

B. 数据对象

C. 数据关系

D 抽象数据类型

【答案】D

【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。

4． 已知两个长度分别为m 和n 的升序链表, 若将它们合并为一个长度为m+n的降序链表, 则最坏情况下的时间复杂度是（ ） A. B. C. D.

【答案】D

m 和n 是两个升序链表长度分别为m 和n , 在合并过程中最坏的情况是两个链表中的【解析】

元素依次进行比较, 比较的次数是m 和n 中的最大值。

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． 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）.

A. 逻辑设备名

B. 物理设备名

C. 主设备号

D. 从设备号

【答案】A

【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等. 而操作系统内部管理设备使用的是设备编号.

7． 在下列表述中，正确的是（ ）

A. 含有一个或多个空格字符的串称为空格串

B. 对n(n＞0) 个顶点的网，求出权最小的n ﹣1条边便可构成其最小生成树

C. 选择排序算法是不稳定的

D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1

【答案】C

【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时，每次挑最小权值边，是要求该边的两点都在不同的连通分量上的。

8． 假设某计算机的存储系统由Cache 和主存组成. 某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.

A.5% B.

C.50%

D.95%

【答案】D

【解析】Cache 的命中率H ＝N 1(N1＋N 2) ，其中N 1为访问Cache 的次数，N 2为访存主存的次数，程序总访存次数为N 1＋N 2，程序访存次数减去失效次数就是访问Cache 的次数队. 所以根据公式可得：H ＝(1000﹣50) /100＝95%.

9． 若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 则根结点的孩子结点（ ）。

A. 只有e

B. 有e 、b

C. 有e 、c

D. 无法确定

【答案】A 。

【解析】由题目可知, 若一棵二叉树的前序遍历序列为a , e , b , d , c , 后序遍历序列为b , c , d , e , a , 其中a 为这棵二叉树的根结点, 接下来, 在前序遍历的第二个结点为e , 而后序遍历的倒数第二个结点为e , 说明a 的孩子结点只有e 。