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

一、单项选择题

1． 下列不是设计一个“好”的算法应考虑达到的目标是（ ）。

A. 可行的

B. 健壮的

C. 无二义性的

D. 可读性好的

【答案】A

【解析】设计一个“好”的算法应考虑以下目标:正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。

2． 某计算机处理器主频为50MHz , 采用定时查询方式控制设备A 的, 查询程序运行一次所用的时钟周期数至少为500。在设备A 工作期间, 为保证数据不丢失, 每秒需对其查询至少200次, 则CPU 用于设备A 的

A. B. C. D.

【答案】C 的时间占整个CPU 时间的百分比至少是（ ）。 【解析】对于设备A , 每秒中查询至少200次, 每次查询至少500个时钟周期, 总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的的时间占整个CPU 时间的百分比至少为100000/50。

3． 已知关键字序列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)为调整后的小根堆.

(3)

(4)

(5)

4． 数据链路层采用选择重传协议(SR)传输数据, 发送方已发送了0H3号数据帧, 现已收到1号帧的确认, 而0、2号帧依次超时, 则此时需要重传的帧数是（ ）。

A.1

B.2

C.3

D.4

【答案】B

【解析】在选择重传协议中, 接收方逐个地确认正确接收的分组, 不管接收到的分组是否有序, 只要正确接收就发送选择ACK 分组进行确认。因此选择重传不支持累积确认, 要特别注意其与

GBN 协议的区别。本题收到1号帧的确认, 说明1号帧正确接收, 0和2号帧依次超时, 因此必须重传, 然而3号帧尚未超时, 是否正确接收未知, 故不用重传, 因此必须重传0和2号帧, 答案是B 。

5． 设X 是树T 中的一个非根结点，B 是T 所对应的二叉树。在B 中，X 是其双亲的右孩子，下列结论正确的是（ ）。

A. 在树T 中，X 是其双亲的第一个孩子

B. 在树T 中，X 一定无右兄弟

C. 在树T 中，X 一定是叶结点

D. 在树T 中，X 一定有左兄弟

【答案】D

【解析】由树和二叉树的转换关系可知，X 一定有左兄弟，X 是其双亲的第二个孩子，不能确定在树T 中，X 是否有右兄弟，是否是叶结点。

6． 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法（ ）。

A. 分块

B. 顺序

C. 折半

D. 哈希

【答案】A

【解析】分块查找，把线形表分成若干块，块间是顺序存储的，所以查找速度较快。在每一块中的数据元素的存储顺序是任意的，所以便于线性表的动态变化。

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

8． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，A[0][0]存放于B[0]中，那么第i 行的对角元素A[i][i]存放于B 中（ ）处。

A.(i＋3)*i/2

B.(i＋1)*i/2