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

一、单项选择题

1． 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。

A. 选择排序法

B. 插入排序法

C. 快速排序法

D. 堆排序法

【答案】A

【解析】选择排序的基本思想是:

第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录

和

2． 下列选项中, 在

Ⅰ.

Ⅱ. 分别变为新的有序区和新的无序区。 总线的数据线上传输的信息包括（ ）。 和，该趟排序，将它与无序区的第1个记录R[i]交换，使接口中的命令字 接口中的状态字

Ⅲ. 中断类型号

A. 仅Ⅰ、Ⅱ

B. 仅Ⅰ、Ⅲ

C. 仅Ⅱ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

【答案】D 。

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

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

A.G 中有弧

C.G 中没有弧

【答案】D

B.G 中有一条从到的路径 D.G 中有一条从到的路径

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

4． 排序算法的稳定性是指（ ）。

A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C. 算法的排序性能与被排序元素的数量关系不大

D. 算法的排序性能与被排序元素的数量关系密切

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=tj，且ri 在ij 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

5． 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。

A.(2，5，12，16)26(60，32，72)

B.(5，16，2，12)28(60，32，72)

C.(2，16，12，5)28(60，32，72)

D.(5，16，2，12)28(32，60，72)

【答案】B

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

第一次比较:28比72小，不交换;

第二次比较:28比5大，交换，此时为(5，16，32，12，60，2，28，72) ;

第三次比较:16比28小，不交换；

第四次比较:32比28大，交换，此时为(5，16，28，12，60，2，32，72) ;

第五次比较:28比2大，交换，此时为(5，16，2，12，60，28，32，72) ;

第六次比较:28比12大，不交换；

第七次比较:28比60小，交换，此时为(5，16，2，12，28，60，32，72) ;

一次划分结束。

6． 对进行基数排序，一趟排序的结果是:（ ）

A. 05， 46， 13， 55， 94， 17， 42 B.

C. 42，13， 94，05， 55， 46，17

D. 05，13， 46，55，17，42，94

【答案】C

【解析】基数排序有两种:最低位优先和最高位优先。

①最低位优先的过程

先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是 根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。

②以r 为基数的最低位优先排序的过程 假设线性表由结点序列

成，

其中

分配:开始时，把

收集:把构成，每个结点的关键字由d 元组。在排序过程中，使用r 个队列组。排序过程就是对i=0， 1，... ，d －1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性:

表中的每一个结点各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的。如果的关键字k=k，就把放进Q k 队列中。

线性表。

7． 有n(n＞0) 个分支结点的满二叉树的深度是（ ）。

A.n 2﹣l

B.log 2(n＋1) ＋1

C.log 2(n＋1)

D.log 2(n—1)

【答案】C

【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树，

所以非分支的结点总数为1，所以满二叉树共有n ＋1个结点，所以满二叉树的深度为log 2 (n＋1) 。

8． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。

A.O(1)

B.O(N)

C.O(N2) D.

【答案】B

【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定

关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。

9． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。

A.n

B.n ﹣2

C.n ﹣1

D.n ＋1

【答案】c