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

一、单项选择题

1． 某同步总线的时钟频率为100MHz , 宽度为32位, 地址/数据线复用, 每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发) 传输方式, 则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。

A.20ns

B.40ns

C.50ns

D.80ns

【答案】C 。

【解析】总线的时钟频率为100MHz , 则时钟周期为10ns 。数据是128位, 总线宽度是32位, 所以需要4个时钟周期, 而传输地址还需要一个周期, 所以传输一个128位的数据至少需要5个时钟周期, 所以至少需要。

2． 下述文件中适合于磁带存储的是（ ）。

A. 顺序文件

B. 索引文件

C. 哈希文件

D. 多关键字文件

【答案】A

【解析】磁带存储是一种顺序存储，顺序文件(sequential file)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。

3． 归并排序中，归并的趟数是（ ）。

A.O(n) B. C. D.

【答案】B

【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n

。因此每次归并元素的个数増加一倍。所以

。

。所以归并的趟数为

4． 主机甲和主机乙之间已建立了一个TCP 连接，TCP 最大段长度为1000字节，若主机甲的当前拥塞窗口为4000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的对第一个段的确认段，确认段中通告的接收窗口大小为2000字节，则此时主机甲还可以向主机乙发送的最大字节数是（ ）.

A.1000

B.2000

C.3000

D.4000

【答案】A

【解析】发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为min{4000，2000) ＝2000字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000－1000＝1000字节，正确选项为A.

5． 下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。

A. 二叉排序树

B. 哈夫曼树

C.A VL 树

D. 堆

【答案】D

【解析】堆的定义:

n 个关键字序列K 1，K 2，... ，K n 称为堆，当且仅当该序列满足如下性质(简称为堆性质) :

(1)

(2)

且且或

满足第(1)种情况的堆，称为小顶堆；满足第(2)种情况的堆，称为大顶堆。

由堆的定义可知堆可以满足上述性质。

6． 下列选项中, 不能构成折半查找中关键字比较序列的是（ ）。

A.500, 200, 450, 180

B.500, 450, 200, 180

C.180, 500, 200, 450

D.180, 200, 500, 450

【答案】A

【解析】折半查找的过程是:先确定待查找记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足:对每一个关键字, 其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误, 第三次比较的关键字为450, 说明待查关键字位于200〜450间, 所以第四次比较时不会遇到关键字180。

7． 下列寄存器中, 汇编语言程序员可见的是（ ）。

A. 存储器地址寄存器(MAR)

B. 程序计数器(PC)

C. 存储器数据寄存器(MDR)

D. 指令寄存器(IR)

【答案】B

【解析】CPU 有5个专用寄存器, 它们是程序计数器(PC)、指令寄存器(IR)、存储器地址寄存器(MAR)、存储器数据寄存器(MBR)和状态标志寄存器(PSWR), 这些寄存器中有些是CPU 的内部工作寄存器, 对汇编语言程序员来说是透明的, 在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值, 所以程序计数器(PC)对于汇编语言程序员可见的。

8． 下列四个序列中，哪一个是堆（ ）?

A.75，65，30，15，25，45，20，10

B.75，65，45，10，30，25，20，15

C.75，45，65，30，15，25，20，10

D.75，45，65，10，25，30，20，15

【答案】C

【解析】堆的定义:

n 个关键字序列

①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；

大根堆:满足第②种情况的堆。

根据堆定义即可得出答案。

9． 基于比较方法的n 个数据的内部排序。 最坏情况下的时间复杂度能达到的最好下界是（ ）。

A. B.

C. O (n) D.

【答案】A

【解析】在内部排序中，最坏情况下的时间复杂度为

10．下面关于串的叙述中，不正确的是（ ）。

A. 串是字符的有限序列

B. 空串是由空格构成的串

C. 模式匹配是串的一种重要运算

。