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

一、选择题

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

A.

B.

C.

D.

【答案】D

【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。

2． 折半查找的时间复杂性为（ ）。

【答案】D

【解析】顺序查找的事件复杂度为

度为

总线的数据线上传输的信息包括（ ）。

接口中的状态字III. 中断类型号 3． 下列选项中，在I.

A. 仅 I 、II

B. 仅 I 、III

C. 仅 II 、III

D.I 、II 、III

【答案】D 。

【解析】

在

总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。

因为折半查找是查找效率最高的算法，它的事件复杂接口中的命令字

II.

4． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。

该机的MIPS 数是（ ）

A.100

B.200

C.400

D.600

【答案】C

【解析】基准程序的计算机的主频为为1200MHz ， 该机器的

5． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A. 顺序表

B. 双链表

C. 带头结点的双循环链表

D. 单循环链表

【答案】A

【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进

行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。

6． 在有向图G 的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是（ ） 。

A.G 中有弧 B.G 中有一条从V i 到V j 的路径

C.G 中没有弧

【答案】D

【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在从顶点B 到顶点A 的路径。又因为若G 中有一条从V j 到V i 的路径，则在拓扑序列中V i 不可能在V j 前。

7． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。

A.1

B.2

C.3

D.4

【答案】C 。

【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。

8． 下列措施中，能加快虚实地址转换的是1增大快表（TLB ） 2让页表常驻内存3增大交换区（ ）。

A. 仅1

B. 仅2

C. 仅 1，2

D. 仅 2, 3

【答案】C

【解析】加大快表能增加快表的命中率，即减少了访问内存的次数；让页表常驻内存能够使cpu 不用访问内存找页表，从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用，对虚实地址转换并无影响

9． 连续存储设计时，存储单元的地址（ ）。

A. 一定连续

B. 一定不连续

C. 不一定连续

D. 部分连续，部分不连续

【答案】A

【解析】连续存储是指数据的物理存储相连，即存储单元的地址是连续的。

10．下列选项中，用于设备和控制器（’接口）之间互连的接口标准是（ ）

A.PCI

B.USB

C.AGP

D.PCI-Express

【答案】B

【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。

11．一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A.107

B.108

C.214

D.215

【答案】B