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

一、填空题

1． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。

【答案】23；100CH

2． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。

【答案】n ; n+1

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

3． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。

4． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n (n－1) /2

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。

5． 在基于关键字比较且时间为_ 的排序中，若要求排序是稳定的，则可选用_____排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。

【答案】归并；堆

6． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

二、单项选择题

7． 下列关于管道(Pipe)通信的叙述中, 正确的是（ ）

A. —个管道可实现双向数据传输

B. 管道的容量仅受磁盘容量大小限制

C. 进程对管道进行读操作和写操作都可以被阻塞

D. —个管道只能有一个读写进程或一个写进程对其操作

【答案】C

【解析】只有写进程才能对管道写入数据, 读进程对管道进行读取数据, 只能半双工通信, 即某一时刻只能单向传输。管道为空, 则读操作被堵塞, 而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确

8． 下面关于求关键路径的说法不正确的是（ ）。

A. 求关键路径是以拓扑排序为基础的

B. —个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D. 关键活动一' 定位于关键路径上

【答案】C

【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。

9． 链表不具有的特点是（ ）。

A. 插入、删除不需要移动元素

B. 可随机访问任一元素

C. 不必事先估计存储空间

D. 所需空间与线性长度成正比

【答案】B

【解析】B 项是顺序表的特点。只要确定了顺序线性表的起始位置，线性表中的任一数据元素都可随机存取。

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

11．在一个文件被用户进程首次打开的过程中, 操作系统需做的是（ ）

A. 将文件内容读到内存中

B. 将文件控制块读到内存中

C. 修改文件控制块中的读写权限

D. 将文件的数据缓冲区首指针返回给用户进程

【答案】B

【解析】概念

12．对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。

A. 顺序存储方式

B. 链式存储方式

C. 散列存储方式

D. 以上均可以

【答案】B

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

(1)进程与进程

(2)处理机与设备

(3)处理机与通道

(4)设备与设备

A. (1)、(2)和(3)

B. (1)、(2)和(4)

C. (1)、(3)和(4)

D. (2)、(3)和(4)