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

一、选择题

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

A.5%

B.9.5%

C.50%

D.95%

【答案】D

【解析】Cache 的命中率

次数，程序总访存次数，其中为访问Cache 的次数，为访存主存的所以根据公, 程序访存次数减去失效次数就是访问Cache 的次数

式可得：H=（1000-50）/1000=95%。

2． 下列选项中，不可能是快速排序第2趟排序结果的是（ ）

A.2, 3, 5, 4, 6, 7, 9

B.2, 7, 5, 6, 4, 3, 9

C.3, 2, 5, 4, 7, 6, 9

D.4, 2, 3, 5, 7, 6, 9

【答案】C

【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果

3． 已知串

A.0123

B.1123

C.1231

D.1211

【答案】A 其Next 数组值为（ ）。

【解析】KMP 算法的next 数组建立的原则

4． 在’

A.PPP 体系结构中，直接为ICMP 提供服务的协议是（ ）。

B.IP

C.UDP

D.TCP

【答案】B 。

【解析】首先明确ICMP 是网络层的协议，由于服务必须是下一层向上一层提供服务的，因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层，在网络层上面，所以显然错误，而PPP 协议是广域网数据链路层协议，直接为网络层，也就是IP 层提供服务，ICMP 协议是封装在网络层，因此PPP 不能直接为ICMP 提供服务，ICMP 报文直接封装在IP 分组中，故答案是B 。

5． 设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。

A.0、1

B.1、0

C.1、2

D.2、0

【答案】B

【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。

6． 循环队列存储在数组中，则入队时的操作为（ ）。 A. B. C. D.

【答案】D

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

A. 直接插入排序

B. 起泡排序

C. 简单选择排序

D. 快速排序

【答案】A

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

；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）

n-1趟，

比较的时间复杂度由 降至

8． 若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。

A.d ，c ，e ，b ，f ，a

B.c ，b ，d ，a ，e ，f

C.b ，c ，a ，e ，f ，d

D.a ，f ，e ，d ，c ，b

【答案】D

【解析】4个选项所给序列的进、出栈操作序列分别为：

选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop

选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop

选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop

选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop

按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。

9． 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含2条微程序，各指令对应的微程序平均由4条微指令组成，采用断定法（下址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是：（ ）

A.5

B.6

C.8

D.9

【答案】C 【解析】

10．单处理机系统中，可并行的是（ ）。

I. 进程与进程

II. 处理机与设备

III. 处理机与通道

IV. 设备与设备

A.I 、II 和III

B.I 、II 和IV

C.I 、III 和IV

D.II 、III 和IV

【答案】D

【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。

所以至少需要8位才能表示完130个地址。