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

一、单项选择题

1． 若串S ＝'software'%其子串的数目是（ ）。

A.8

B.37

C.36

D.9

【答案】B

【解析】子串的定义是:串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n(n＞0) ，长为n 的子串有1个，长为n ﹣1的子串有2个，长为n ﹣2的子串有3个，...... ，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案为:8*(8＋1)/2十1＝37。故选B 。

2． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）

A.G 的邻接多重表需要n(n－1) 个边结点和n 个顶点结点

B.G 的连通分量个数最少

C.G 为连通图

D.G 所有顶点的度的总和为n(n—1)

【答案】A

A 项中G 的邻接多重表中需要【解析】

n 个结点的度的总和为n(n－1) 。

3． 已知循环队列存储在一维数组

的值分别是（ ）。

A.0, 0

B.0, n-1

C.n-1, 0

D.n-1, n-1

【答案】B

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素, 若初始时队列为空, 且要求第1个进入队列的元素存储在A[0]处, 则此时front 和rear 的值都为0。由于进队操作要执

第 2 页，共 73 页 个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n －1，则中, 且队列非空时front 和rear 分别指向队头元素和处, 则初始时front 和rear 队尾元素。若初始时队列为空, 且要求第1个进入队列的元素存储在

行, 则初始时front 的值为0、rear 的值为n-1。

4． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A.N

B.2N －1

C.2N

D.N －1

【答案】A

【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。

5． 当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。

Ⅰ. 撤销部分进程

Ⅱ. 增加磁盘交换区的容量

Ⅲ. 提高用户进程的优先级

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅲ

D. 仅Ⅰ、Ⅱ

【答案】A

【解析】“抖动”现象是指刚刚被换出的页很快又要被访问, 为此, 又要换出其他页, 而该页又很快被访问, 必须换入, 如此频繁地置换页面, 以致操作系统的大部分时间都花在页面置换上, 引起系统性能下降甚至崩溃。引起系统抖动现象的原因是对换的信息量过大, 内存容量不足, 置换算法选择不当。所以解决的办法就是降低交换页面数量, 加大内存容量, 改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的, 只能增加内存容量。增加内存容量可以是直接添加物理内存(大型计算机都可以在不关机的情况下增加物理内存条) , 或者, 降低进程数量, 相对地增加内存。而增加交换区容量并不能解决物理内存不足的问题, 提高用户进程的优先级会使系统的状态更加恶化。

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

A. 重排请求次序

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

C. 预读和滞后写

D. 优化文件物理块的分布

【答案】B 。

【解析】

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

磁盘的

第 3 页，共 73 页

性能的是（ ）。 性能是计算机性能提高

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

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

而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘性能的提升没有什么帮助, 是不能改善磁盘设备性能的, 故答案为B 。

7． 中断处理和子程序调用都需要压桟以保护现场, 中断处理一定会保存而子程序调用不需要保存其内容的是（ ）。

A. 程序计数器

B. 程序状态字寄存器

C. 通用数据寄存器

D. 通用地址寄存器

【答案】B 。

【解析】中断处理与子程序调用最大的区别是中断处理程序与正在运行的进程可能无关, 而子程序调用与正在运行的进程有关。中断是要打断处理器的正常工作次序, 并要求其去处理某一事件的一种常用手段。因此, 除了要保护当前程序的地址, 计数器(指针) 和数据寄存器以外, 还需要保存程序状态字。子程序调用是与当前进程有关, 是正在运行的程序有意安排执行的, 这一类调用发生的时间以及位置具有确定性, 处于同一个进程内, 因此不需要保存程序状态字。所以中断处理和子程序调用不同的区别是中断处理程序必定会保存程序状态字寄存器。

8． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。

A. 求子串

B. 判断是否相等

C. 模型匹配

D. 连接

【答案】C

【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。

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

A. 选择排序法

B. 插入排序法

C. 快速排序法

D. 堆排序法

【答案】A

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

第 4 页，共 73 页