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

一、选择题

1． 若需在0（nlog2n ）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A. 快速排序

B. 堆排序

C. 归并排序

D. 直接插入排序

【答案】C

【解析】稳定排序有：插入排序、起泡排序、归并排序、基数排序。不稳定排序有：快速排序、堆排序、shell 排序。时间复杂度平均为的有：归并排序、堆排序、shell 排序、快速排序。

2． 单链表中，增加一个头结点的目的是为了（ ）。

A. 使单链表至少有一个结点

B. 标识表结点中首结点的位置

C. 方便运算的实现

D. 说明单链表是线性表的链式存储

【答案】C

【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。

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

A. 仅1

B. 仅2

C. 仅 1，2

D. 仅 2, 3

【答案】C

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

4． 站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence

）分别是

和

C 收到A 发送的数据是（ ）

A.000

B.101

C.110

D.111

【答案】B

【解析】用A 的码片与信息做内积运算

5． —个非空广义表的表尾（ ）。

A. 不能是子表

B. 只能是子表

C. 只能是原子

D. 是原子或子表

【答案】B

【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。

6． 下列调整中，不可能导致饥饿现象的是（ ）

A. 时间片转移

B. 静态优先及调度

C. 非抢占式作业优先

D. 抢占式短作业优先

【答案】A

【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。

7． 若某文件系统索引结点（inode ）中有直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是（ ）

A. 索引结点的总数

B. 间接地址索引的级数

C. 地址项的个数

D. 文件块大小

【答案】A

【解析】根据文件长度与索引结构的关系可知，只有选项A 是与单个文件长度无关的。 若C 从链路上收到的序列是则

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． 下列给出的指令系统特点中，有利于实现指令流水线的是（ ）。

I. 指令格式规整且长度一致

II. 指令和数据按边界对齐存放

III. 只有Load / Store指令才能对操作数进行存储访问

A. 仅

B. 仅

C. 仅 D.

【答案】D

【解析】特点I 和III 都是RISC 机的特征，而特点II 则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。

10．下列关于无向连通图特性的叙述中，正确的是（ ）。

I. 所有的顶点的度之和为偶数

II. 边数大于顶点个数减1

III. 至少有一个顶点的度为1

A. 只有I

B. 只有II

C.I 和II

D.I 和III

【答案】A

【解析】在图中，顶点的度TD

点数，

之和与边的数目满足关系式：（n 为图的总结