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

一、单项选择题

1． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。

A. 直接插入排序

B. 起泡排序

C. 简单选择排序

D. 快速排序

【答案】A

【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n －1趟排序，也即时间复杂度仍为0(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也

2即n －1趟，比较的时间复杂度由O(n) 降至O(n)。

2． 下列哪一种图的邻接矩阵是对称矩阵？（ ）

A. 有向图

B. 无向图

C.AOV 网

D.AOE 网

【答案】B

【解析】邻接矩阵存储，就是用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间关系的二维数组称为邻接矩阵。因为无向图中边是没有方向的，

所以

，所以无向图的邻接矩阵是对称矩阵。

3． 设二维数组

A.(i﹣1)*n＋j

B.(i﹣1)*n＋j ﹣l

C.i*(j﹣1)

D.j*m＋i ﹣l

(即m 行n 列) 按行存储在数组中，则二维数组元素A[i，j]在一维数组B 中的下标为（ ）。

【答案】A

【解析】前i ﹣1的元素个数为(i﹣1)*n，所以二维数组元素A[i，j]在一维数组B 中的下标为(i﹣1)*n＋j 。需要注意数组B 的下标是从0开始，还是从1开始。

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

A. 命令解释程序

B. 缺页处理程序

C. 进程调度程序

D. 时钟中断处理程序

【答案】A

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

5． 下列选项中，导致创建新进程的操作是（ ）.

(1)用户登录成功

(2)设备分配

(3)启动程序执行

A. 仅(1)和(2)

B. 仅(2)和(3)

C. 仅(1)和(3)

D. (1)、(2)和(3)

【答案】C

【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是(2).考察一个进程创建的过程是这样的:当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填写PCB 表创建进程. 通常填写PCB 表的过程有一段时间(主要涉及资源分配需要协调），许多操作系统为此设立了一个中间状态称为“初始化”，也有的操作系统不设这个中间状态. 此时操作系统填写进程ID 号、处理机参数、进程参数(状态、特权、优先级) 、分配内存(若是虚拟存储就分配虚拟地址) 、映射文件等，一切就绪，将控制权交给系统进行下一步调度. 设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C.

6． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。

A.24, 10, 5和24, 10, 7

B.24, 10, 5和24, 12, 7

C.24, 10, 10和24, 14, 11

D.24, 10, 5和24, 14, 6

【答案】D

【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。

7． 假设某计算机按字编址, Cache 有4个行, Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空, 采用2路组相联映射方式和LRU 替换算法, 当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数是（ ）。

A.1

B.2

C.3

D.4

【答案】C 。

【解析】Cache 有4个行, 2路组相联, 即Cache 被分成2组, 每组2行。主存地址为0〜1、4〜5、8〜9可映射到第0组Cache 中, 主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空, 采用LRU 替换算法, 当访问主存的10个地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数共有3次, 分别发生在第7、8和10步时。

8． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.

B.n/2 C.

D.n

【答案】C

【解析】最快查找一次成功，最慢查找n

次成功。平均查找次数为

。

9． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）

那么A.O(2n)

B.O(n)

C.O(n2)

D.O(log2n )