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

一、选择题

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

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

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

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

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

【答案】B

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

2． 用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。

【答案】A

【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。

3． 先序序列为a , b，c , d的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。本题中，结点a 为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bed 为右子树；②b 为左子树，cd 为右子树；③be 为左子树，d 为右子树；④bed 为左子树，右子树为空。然后将左右子树继续分解，如第①种情况的右子树先序遍历（bed ）可能有：a. 左子树为空，右子树为cd ；b. 左子树为c ，右子树为d ；c. 左子树为cd ，右子树为空。按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二 叉树。

4． 下列指令中，不能在用户态执行的是（ ）

A.trap 指令

B. 跳转指令

C. 后栈指令

D. 关中断指令

【答案】D

【解析】关中断指令必须在和心态才能执行，trap 指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。

5． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A. 二维数组和三维数组

B. 三元组和散列

C. 三元组和十字链表

D. 散列和十字链表

【答案】C

【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组（行标，列标，值）。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。

6． 一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。

A.

B.

C.

D. 字节

字节

字节

字节

【答案】C

【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下32-8=24位是段内位移空间，因此最大段长为B 。

7． 排序算法的稳定性是指（ ）。

A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C. 算法的排序性能与被排序元素的数量关系不大

D. 算法的排序性能与被排序元素的数量关系密切

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这

些记录的相对次序保持不变，即在原序列中，且在之前，而在排序后的序列中，仍在之前，则称这种排序算法是稳定的；否则称为不稳定的。

8． 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。

A.3, 5，12，8, 28，20, 15，22，19

B.3, 5, 12, 19, 20, 15, 22, 8, 28

C.3, 8, 12, 5, 20, 15, 22, 28, 19

D.3, 12, 5, 8, 28, 20, 15, 22, 19

【答案】A

【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）〜（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。