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

一、选择题

1． 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。

Ⅰ. 简单选择排序Ⅱ. 希尔排序Ⅲ. 快速排序Ⅳ. 堆排Ⅴ. 二路归并排序

A. 仅Ⅰ、Ⅲ、Ⅳ

B. 仅Ⅰ、Ⅱ、Ⅲ

C. 仅Ⅱ、Ⅲ、IV

D. 仅Ⅲ、Ⅳ、Ⅴ

【答案】A 。

【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。

2． 下列说法中正确的是（ ）。

A.SRAM 存储器技术提高了计算机的速度

B. 若主存由ROM 和RAM 组成，容量分别为则主存地址共需位

C. 闪速存储器是一种高密度、非易失性的读/写半导体存储器

D. 存取时间是指连续两次读操作所需间隔的最小时间

【答案】C

3． 已知小根堆为8, 15, 10, 21, 34, 16, 12, 删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。

A.1

B.2

C.3

D.4

【答案】C

【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比

较，12小于15, 所以不用交换；然后与10比较，因为10小于12, 所以交换10和12的位置；调整后12再与16比较，12小于16, 调整堆过程结束。因此12共与15、10、16进行了三次比较。

4． 下列有关RAM 和ROM 的叙述中，正确的是（ ）。

I.RAM 是易失性存储器，ROM 是非易失性存储器

II.RAM 和ROM 都采用随机存取方式进行信息访问

III.RAM 和ROM 都可用作Cache

IV .RAM 和ROM 都需要进行刷新

A. 仅I 和II

B. 仅II 和III

C. 仅I 、II 和IV

D. 仅II 、III 和IV

【答案】A

RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性）

，区别在同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）

于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache ，也不需要刷新，所以III 和IV 的叙述都是错误的。

5． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）

A.

B.

C.

D.

【答案】D

m 和n 是两个升序链表长度分别为m 和m 在合并过程中最坏的情况是两个链表中的【解析】

元素依次进行比较，比较的次数是m 和n 中的最大值。

6． 设与某资源相关联的信号量初值为3，当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。

A.0、1

B.1、0

C.1、2

D.2、0

【答案】B

【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。

7． 已知字符串S 为

出现“失配”

A.i=l, j=0

B.i=5, j=0

C.i=5, j=2

D.i=6, j=2

【答案】C 模式串t 为采用KMP 算法进行匹配，第一次时，i=j=5, 则下次开始匹配时，i 和j 的值分别是（ ）。

【解析】模式匹配（KMP ）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S ）的指针（i ）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t ）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t ）本身决定的，即t 的子串中前缀串和后缀串相等的最长长度。本题中第一次失配i=5, 字串为“abaab ”，其相等且最长的前后缀为“ab ”，一次下一个j=2。

8． float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中，且

A.C1040000H

B.C2420000H

C.C1840000H

D.C1C20000H

【答案】A 则FR1的内容是（ ）。

【解析】首先将十进制数转换为二进制数-1000.01，接着把它写成规格化形式

=1，阶码=10000010, 尾数（按IEEE754标准），然后计算阶码的移码=偏置值+阶码真值=127+3=130, 最后短浮点数代码：数符位写成十六进制为C1040000H 。选项D 是一个很容易被误选的选项，其错误在于没有考虑IEEE754标准中隐含最高位1的情况，偏置值是128。

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

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，满足哈夫曼树的条件。