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

一、单项选择题

1． 若需在

（ ）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

【答案】C

【解析】稳定排序有:插入排序、起泡排序、归并排序、基数排序。不稳定排序有:快速排序、

堆排序、shell 排序。时间复杂度平均为的有:归并排序、堆排序、shell 排序、快速排序。

2． 已知字符串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。

3． 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ） A. B. C. D.

【答案】A

第 2 页，共 60 页 的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是) 时, i=j=5, 则下次开始匹配时, i 和j 的值分别是（ ）。

【解析】寄存器个数

指令编址方式如下所示:

偏移量有32-8-4-4=16位

16位补码取值范围为, 所以偏移量取值范围为

4． 希尔排序的组内排序采用的是（ ）。

A. 直接插入排序

B. 折半插入排序

C. 快速排序

D. 归并排序

【答案】A

【解析】希尔排序基本思想是:先将整个待排元素序列按某个增量分割成若干个子序列, 在子序列内进行直接插入排序, 然后依次缩减增量再进行排序, 待整个序列中的元素基本有序(增量足够小) 时, 再对全体元素进行一次直接插入排序。

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

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

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

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

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

【答案】A

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

6． 若用户进程访问内存时产生缺页, 则下列选项中, 操作系统可能执行的是（ ）

Ⅰ. 处理越界错

Ⅱ. 置换页

Ⅲ. 分配内存

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ和Ⅲ

【答案】B

【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断, 系统地执行的操作可能是

第 3 页，共 60 页

置换页面或分配内存。系统内没有越界的错误, 不会进行越界出错处理。

7． 下列选项中, 不可能是快速排序第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, 23, 5, 7, 6, 9

【答案】C

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

8． 下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。

A.CSMA

B.CDMA C. D.

【答案】D

【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。

9． 若串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 。

10．栈和队的共同点是（ ）。

A. 都是先进后出

B. 都是后进先出

C. 只允许在端点处插入和删除元素

D. 没有共同点

【答案】C

【解析】栈和队列的区别是栈是先进后出的数据结构，队列是先进先出的数据结构，栈和队

第 4 页，共 60 页