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

一、选择题

1． 设与某资源相关联的信号量初值为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。

2． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。

A. 顺序存储

B. 散列存储

C. 链式存储

D. 索引存储

【答案】A

【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。

3． 对序

列用希尔排序方法排序，经一趟后序列变

为

则该次采用的增量是（ ）。

A.1

B.4

C.3

D.2

【答案】B

【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。

4． 折半查找的时间复杂性为（ ）。

【答案】D

【解析】顺序查找的事件复杂度为因为折半查找是查找效率最高的算法，它的事件复杂

度为

5． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。

A. 前序遍历

B. 中序遍历

C. 后序遍历

【答案】B

【解析】树的后序遍历恰好对应于二叉树的中序遍历。

6． 已知一算术表达式的中缀表达式为其后缀形式为（ ）。

【答案】D

【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。

7． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。

A.1, 2.3.4

B.2，3, 4.1

C.3, 2, 4, 1

D.4, 3, 2, 1

【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反，这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右，这8棵二叉树的中序序列分别为：

（1）4. 3. 2. 1，

（2）3, 4, 2, 1

（3）2, 4, 3, 1

（4）2, 3, 4，1

（5）1，4，3, 2

（6）1, 3, 4, 2

（7）1，2, 4, 3

（8）1, 2, 3, 4

显然选项C 的中序序列不会出现。

8． 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程 中元素之间进行的比较次数是（ ）。

A.1

B.2

C.4

D.5

【答案】B

【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆，

（2）为插入18后，

（3）比较10与18，交换后，

（4）比较25与18, 不交换，即为调整后的新的大根堆。

因此调整过程中元素之间进行的比较次数为2。

9． 串的长度是指（ ）。

A. 串中所含不同字母的个数

B. 串中所含字符的个数

C. 串中所含不同字符的个数

D. 串中所含非空格字符的个数

【答案】B

【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。

10．若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的是（ ）

I. 处理越界错 II. 置换页 III. 分配内存

A. 仅I 、II