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

一、选择题

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

I. 回路是简单路径

II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A. 仅 II B. 仅 I 、II C. 仅III D. 仅 I 、III 【答案】C

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

2． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。

A. 仅1 B. 仅2 C. 仅 1，2 D. 仅 2, 3 【答案】C

【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响

3． 下列关于虚拟存储的叙述中，正确的是（ ）。

A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术 C. 虚拟存储容量只受外存容量的限制

D. 虚拟存储容量只受内存容量的限制 【答案】D 。

【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。

4． 下述文件中适合于磁带存储的是（ ）。

A. 顺序文件 B. 索引文件 C. 哈希文件 D. 多关键字文件 【答案】A

【解析】磁带存储是一种顺序存储，顺序文件

是记录按其在文件中的逻辑顺序

依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。

5． 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是（ ）

A. B. C. D.

【答案】D

【解析】根据广度优先遍历的定义，可知选项A 、B 、C 都为广度优先遍历，而选项D 是深度优先遍历而不是广度优先遍历，故答案为D 。

6． 进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下：

则并发执行进程

和

时产生的情况是（ ）。

A. 不能保证进程互斥进入临界区，会出现“饥饿”现象 B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象 C. 能保证进程互斥进入临界区，会出现“饥饿”现象 D. 能保证进程互斥进入临界区，不会出现“饥饿”现象 【答案】D

【解析】这是皮特森算法（Peterson ’S Algorithm ）的实现，保证进入临界区的进程合理安全。该算法为了防止两个进程为进入临界区而无限期等待，设置变量turn , 表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入。先到先人，后到等待，从而完成临界区访问的要求。

7． 元素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 。