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

一、单项选择题

1． 对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:

第一趟:2, 12, 16, 5, 10, 88

第二趟:2, 12, 5, 10, 16, 88

第三趟:2, 5, 10, 12, 16, 88

则采用的排序方法可能是（ ）。

A. 起泡排序

B. 希尔排序

C. 归并排序

D. 基数排序

【答案】A

【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。

2． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。

A. 对称矩阵

B. 稀疏矩阵

C. 三角矩阵

D. —般矩阵

【答案】C

【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序:①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在图

中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。

3． 已知循环队列存储在一维数组

的值分别是（ ）。

A.0, 0

B.0, n-1

C.n-1, 0

D.n-1, n-1

【答案】B 中, 且队列非空时front 和rear 分别指向队头元素和处, 则初始时front 和rear 队尾元素。若初始时队列为空, 且要求第1个进入队列的元素存储在

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素, 若初始时队列为空, 且要求第1个进入队列的元素存储在A[0]处, 则此时front 和rear 的值都为0。由于进队操作要执

行, 则初始时front 的值为0、rear 的值为n-1。

其Next 数组值为（ ）。 4． 已知串

A.0123

B.1123

C.1231

D.1211

【答案】A

【解析】KMP 算法的next 数组建立的原则

5． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为（ ）。 A.

B.n/2 C.

D.n

【答案】C

【解析】最快查找一次成功，最慢查找n

次成功。平均查找次数为

。

6． 以太网交换机进行转发决策时使用的PDU 地址是（ ）.

A. 目的物理地址

B. 目的IP 地址

C. 源物理地址

D. 源IP 地址

【答案】A

那么

【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息(源结点的MAC 地址、目的结点的MAC 地址) ，就会得到与每个端口所连接结点的MAC 地址，并在交换机的内部建立一个“

端口地址”映射表. 建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC 地址，并通过“端口-MAC 地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP 地址的选项是不对的，因此答案为

A.

7． 线性表是具有n 个（ ）的有限序列(n＞0) 。

A. 表元素

B. 字符

C. 数据元素

D. 数据项

E. 信息项

【答案】C

【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。

8． 进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下:

则并发执行进程P0和PI 时产生的情况是（ ）.

A. 不能保证进程互斥进入临界区，会出现“饥饿”现象

B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象

C. 能保证进程互斥进入临界区，会出现“饥饿”现象

D. 能保证进程互斥进入临界区，不会出现“饥饿”现象

【答案】D