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

一、选择题

1． 对于循环队列（ ）。

A. 无法判断队列是否为空

B. 无法判断队列是否为满

C. 队列不可能满

D. 以上说法都不是

答:D

【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：①另设一个布尔变量来区别队列是空还是满；②队满时，（rear+1）==font。

2． 有六个元素6, 5, 4, 3, 2, 1顺序入栈，下列不是合法的出栈序列的是（ ）。

A.543612

B.453126

C.346521

D.234156

答:C

【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出找。

3． 关键路径是AOE 网中（ ）。

A. 从始点到终点的最短路径

B. 从始点到终点的最长路径

C. 从始点到终点的边数最多的路径

D. 从始点到终点的边数最少的路径

答:B

【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径称作关键路径（critical path）。

4． 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。

A. 仅修改队头指针

B. 仅修改队尾指针

C. 队头、队尾指针都可能要修改

D. 队头、队尾指针都要修改

答:C

【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。

5． 下列选项中，不可能是快速排序第2趟排序结果的是（ ）

A.2, 3, 5, 4, 6, 7, 9

B.2, 7, 5, 6, 4, 3, 9

C.3, 2, 5, 4, 7, 6, 9

D.4, 2, 3, 5, 7, 6, 9

答:C

【解析】对于快速排序，每一趟都会使一个元素位于有序时的位置，而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比，只有9位于它有序的时候的位置，显然不是第二趟快速排序的结果

6． n 个顶点的无向图的邻接表最多有（ ）个表结点。

A.IT B.n （n-l ） C.n （n+l） D.n （n-l ）/2

答:B

【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n-1个结点连接，从而会产生n （n-l ）个表结点。

7． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。

答:B

【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。

8． 下面关于串的叙述中，不正确的是（ ）。

A. 串是字符的有限序列

B. 空串是由空格构成的串

C. 模式匹配是串的一种重要运算

D. 串既可以采用顺序存储，也可以采用链式存储

答:B

【解析】

空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。

9． 下列选项中，导致创建新进程的操作是（ ）。

用户登录成功

设备分配

启动程序执行

A. 仅和

B. 仅和

C. 仅和

D.

答:C

【解析】进程创建是需要填写PCB 表的，其中唯一不需要的是II 。考察一个进程创建的过程是这样的：当进程被创建，可以是用户创建，例如双击相关图标；也可以由父进程创建，例如lock （ ）时，操作系统首先到PCB 表区搜索空闲的表格，若无则直接拒绝创建进程，若有则填

，许多操写PCB 表创建进程。通常填写PCB 表的过程有一段时间（主要涉及资源分配需要协调）

，也有的操作系统不设这个中间状态。此时操作系作系统为此设立了一个中间状态称为“初始化”

统填写进程ID 号、处理机参数、进程参数（状态、特权、优先级）、分配内存（若是虚拟存储就分配虚拟地址）、映射文件等，一切就绪，将控制权交给系统进行下一步调度。设备分配可能引起进程状态的改变，但不会创建新进程，用户登录成功和启动程序执行都会创建新的进程，所以本题答案为C 。

10．串是一种特殊的线性表，其特殊性体现在（ ）。

A. 数据元素是一个字符

B. 可以顺序存储

C. 数据元素可以是多个字符

D. 可以链接存储

答:A

和

二、填空题

11．设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的

数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。