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

一、单项选择题

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

则并发执行进程P0和PI 时产生的情况是（ ）. A. 不能保证进程互斥进入临界区，会出现“饥饿”现象 B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象 C. 能保证进程互斥进入临界区，会出现“饥饿”现象 D. 能保证进程互斥进入临界区，不会出现“饥饿”现象 【答案】D

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

2． 下列选项中, 不能改善磁盘设备

A. 重排

请求次序

B. 在一个磁盘上设置多个分区

第 2 页，共 60 页

性能的是（ ）。

C. 预读和滞后写

D. 优化文件物理块的分布 【答案】B 。 【解析】

磁盘的一个瓶颈。“重排

性能主要是指其读写速度。相对而言,

磁盘的

性能是计算机性能提高

请求次序”可以优化磁臂调度的算法, 减少读写时间, 故正确; “预读和滞

性能,

后写”是利用内存作为磁盘的缓存, 使得对磁盘的访问变为对内存的访问, 也可以在总体上提高其性能; “优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间, 也可以提高磁盘而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘

盘设备性能的, 故答案为B 。

3． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。

A. 选择排序法 B. 插入排序法 C. 快速排序法 D. 堆排序法 【答案】A

【解析】选择排序的基本思想是:

第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录和

分别变为新的有序区和新的无序区。

和

，该趟排序

，将它与无序区的第1个记录R[i]交换，使

性能的提升没有什么帮助, 是不能改善磁

4． 某计算机存储器按字节编址, 采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位, 并且数据按边界对齐存储。某C 语言程序段如下:

若record 变量的首地址为0xC008, 则地址中内容及的地址分别为（ ）。 A. B. C. D. 【答案】D 。

32位整数a 需要占4个字节, 16位整数c 需要占2个字节, 而字符数据b 占一个字节。【解析】

a=273, 转换成十六进制是111H , 采用小端方式存放数据, 地址边界对齐存储,

地址

中存放c 。

第 3 页，共 60 页

中的内容为11H 。由于数据按中存放b ,

地址

中空闲,

地址

中存放a ,

地址

5． 若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。

A.12 B.20 C.32 D.33

【答案】B 。

【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。深度为h 的平衡二叉树中含有的最少结点数, 有

由此可得

。对应的平衡二叉树如下图所示。

表示

6． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法时间复杂度是（ ）。

A. B. C. D. 【答案】C 。

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,

查找每个顶点的邻接点所需时间为

, 其中n 为图中顶点数。而当以邻接表作图的存储结构时, 找邻接点所需时间为0(e), 其中e 为无向图中边的数或有向图中弧的数。由此, 当以邻接表作存储结构时, 深度优先搜索遍历图的时间复杂度为。即可得出正确答案。

7． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【答案】D

第 4 页，共 60 页