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

一、选择题

1． 某时刻进程的资源使用情况如下表所示

表

1

此时的安全序列是（ ）。

A.P1, P2, P3, P4

B.P1, P3, P2, P4

C.P1, P4, P3, P2

D. 不存在

【答案】D

【解析】典型的死锁避免算法，银行家算法的应用。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下表2，可以看到，经过P1, P4的运行以后，可用资源是2, 2，1，而P2, P3所需资源分别是1，3, 2和1，3，1。所以剩余资源已经不够P2或P3的分配，亦即找不到能够安全运行的序列，因此此时是处于不安全状态，所以不存在这样的安全序列。

表

2

2． 按指令流（I ）和数据流（D ）的组织方式，单处理机系统属于（ ）结构。

A.SISD

B.SIMD

C.MISD

D.MIMD

【答案】A

3． 某容量为256M 的存储器，由若干

数据引脚总数是：（ ）

A.19

B.22

C.30

D.36

【答案】A 位的DRAM 芯片构成，该DRAM 芯片的地址引脚和

【解析】DRAM 地址线复用，4M 为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根

4． 下列关于图的叙述中，正确的是（ ）。

回路是简单路径

存储稀疏图，用邻接矩阵比邻接表更省空间

若有向图中存在拓扑序列，则该图不存在回路

A. 仅

B. 仅

C. 仅

D. 仅

【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，图中存在回路。所以选项Ⅲ正确。

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

【答案】D

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

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

6． 某计算机存储器按字节编址，主存地址空间大小为64MB ，现用4Mx8位的RAM 芯片组成32MB 的主存储器，则存储器地址寄存器MAR 的位数至少是（ ）。

A.22位

B.23位

C.25位

D.26位

【答案】D

【解析】虽然实际的主存储器（RAM 区）只有32MB , 但不排除还有ROM 区，考虑到存储器扩展的需要，MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB ，所以MAR 的位数至少需要26位。

7． 下列指令中，不能在用户态执行的是（ ）

A.trap 指令

B. 跳转指令

C. 后栈指令

D. 关中断指令

【答案】D

【解析】关中断指令必须在和心态才能执行，trap 指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。

8． 下列选项中，不能构成折半查找中关键字比较序列的是（ ）。

A.500, 200, 450, 180

B.500, 450, 200, 180

C.180, 500, 200, 450

D.180, 200, 500, 450

【答案】A

【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误，第三次比较的关键字为450, 说明待查关键字位于间，所以第四次比较时不会遇到关键字180。

9． 5个字符有如下4种编码方案，不是前缀编码的是（ ）

A.01, 0000, 0001, 001, 1

B.011, 000, 001, 010, 1

C.000, 001, 010, 011, 100

D.0, 100, 110, 1110, 1100

【答案】D

【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支表示字符‘0’，右分支表示字符‘1’, 则可以用从根结点到叶子结点的路径上的分支字符串作为

D 选项中，该叶子结点字符的编码。如此得到的编码必是前缀编码。编码110是编码1100的前缀，

故不符合前缀编码的定义。