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

一、单项选择题

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

(1)进程与进程

(2)处理机与设备

(3)处理机与通道

(4)设备与设备

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

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

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

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

【答案】D

【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.

2． 现在有一颗无重复关键字的平衡二叉树(AVL 树) , 对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中, 正确的是（ ）。

A. 根节点的度一定为2

B. 树中最小元素一定是叶节点

C. 最后插入的元素一定是叶节点

D. 树中最大元素一定是无左子树

【答案】D

【解析】二叉树的中序遍历定义是“若二叉树为空, 则空操作; 否则:

①中序遍历左子树; ②访问根节点; ③中序遍历右子树”。

A 项错误, 当树中仅有一个或者两个结点时, 根节点的度就可能不为2; B 项错误, 树中最小元素是中序遍历时最后访问的节点, 当没有右子树时, 最后访问的节点是根节点; C 项错误, 当最后插入的元素破坏树的平衡后, 树会进行调整, 使其成为中间节点; D 项正确, 由中序遍历的特点可知, 左子树的值大于根节点, 所以最大元素一定没有左子树。

3． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列, 能属于同一棵哈夫曼树的是（ ）。

A.24, 10, 5和24, 10, 7

B.24, 10, 5和24, 12, 7

C.24, 10, 10和24, 14, 11

D.24, 10, 5和24, 14, 6

【答案】D

【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中, 第二个被访问的两个结点的权值要么相等, 要么和为根节点的权值, 故B 项错误。同理, 通过第三个被访问的节点排除A 项。C 项, 由两条路径可推出三个叶子节点的权值分别是:3、10和11, 而根据哈夫曼树的定义可知, 权值为3的节点应该和权值为10的结点结合, 故C 项错误。D 项, 反推出有四个叶子节点, 权值分别为:5、5、6和8, 满足哈夫曼树的条件。

4． 已知字符串S 为“abaabaabacacaabaabcc ”, 模式串t 为“abaabc ”, 采用KMP 算法进行匹配, 第一次出现“失配”(

A.i=l, j=0

B.i=5, j=0

C.i=5, j=2

D.i=6, j=2

【答案】C

【解析】模式匹配(KMP)算法对普通的暴力匹配的改进在于:每当匹配过程中匹配失败时, 主串(本题为S) 的指针(i)不需要回溯, 而是利用已经得到的“部分匹配”的结果将模式串(t)向右“滑动”尽可能远的一段距离后, 继续进行比较。模式串“滑动”的距离是由模式串(t)本身决定的, 即t

的子串

中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab”, 其相等且最长的前后缀为“ab”, 一次下一个j=2。

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

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

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

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

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

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=tj，且ri 在ij 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

) 时, i=j=5, 则下次开始匹配时, i 和j 的值分别是（ ）。

6． 下列有关浮点数加减运算的叙述中, 正确的是（ ）。

Ⅰ. 对阶操作不会引起阶码上溢或下溢

Ⅱ. 右规和尾数舍入都可能引起阶码上溢

Ⅲ. 左规时可能引起阶码下溢

Ⅳ. 尾数溢出时结果不一定溢出

A. 仅Ⅱ Ⅲ

B. 仅Ⅰ Ⅱ Ⅳ

C. 仅Ⅰ Ⅲ Ⅳ

D. Ⅰ Ⅱ ⅢⅣ

【答案】D

【解析】浮点数的加减运算步骤包括:①对阶, 使两个操作数的小数点位置对齐, 阶码小的尾数右移, 可能产生溢出, 但是阶码不会溢出; ②尾数求和, 将对阶后的尾数按定点数加(减) 运算规则运算; ③规格化, 包括左规和右规, 左规时阶码减少, 可能出现阶码下溢, 而右规时, 阶码增加可能出现阶码上溢; ④舍入, 该过程可能需要右规调整, 因此可能出现阶码上溢; ⑤溢出判断, 浮点数的溢出与否是由阶码的符号决定的, 而不是由尾数溢出判断的, 因此尾数溢出时结果不一定溢出。因此Ⅰ Ⅱ Ⅲ Ⅳ均正确。

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

A. 选择排序法

B. 插入排序法

C. 快速排序法

D. 堆排序法

【答案】A

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

第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录

和分别变为新的有序区和新的无序区。 和，该趟排序，将它与无序区的第1个记录R[i]交换，使

8． 分区分配内存管理方式的主要保护措施是（ ）.

A. 界地址保护

B. 程序代码保护

C. 数据保护

D. 栈保护

【答案】A

【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护. 通常的界地址保护