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

一、单项选择题

1． 已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆) ，插入关键字3，调整后的小根堆是（ ）.

A.3， 5， 12， 8， 28， 20， 15， 22， 19

B.3， 5， 12， 19， 20， 15， 22， 8， 28

C.3， 8， 12， 5， 20， 15， 22， 28， 19

D.3， 12， 5， 8， 28， 20， 15， 22， 19

【答案】A

【解析】在堆中插入或删除一个元素后，将不再满足堆的性质. 为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素. 具体过程如图(1)〜(5)所示，(1)为原堆，(2)为插入3后，(3)、(4)为调整过程，(5)为调整后的小根堆

.

(3)

(4)

(5)

2． 对关键码序列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) ;

一次划分结束。

3． 在下列存储形式中，哪一个不是树的存储形式？（ ）

A. 双亲表示法

B. 孩子链表表示法

C. 孩子兄弟表示法

D. 顺序存储表示法

【答案】D

【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位

置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。

4． 若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ）

A.h , c , a , b , d , e , g , f

B.e , a , f , g , b , h , c , d

C.d , b , c , a , h , e , f , g

D.a , b , c , d , h , e , f , g

【答案】D

【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。

5． 在含有n 个关键字的小根堆(堆顶元素最小) 中，关键字最大的记录有可能存储在（ ）位置上。 A. B.

C.1 D.

【答案】D

【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于Ln/2」的结点上。

6． 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据. 该缓冲区的逻辑结构应该是（ ）.

A. 找

B. 队列

C. 树

D. 图

【答案】B

【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后“先进先出”等再判断其逻辑结构. 栈和队列是操作受限的线性表，出”、栈具有先进后出的特性而队列具有先进先出的特性. 由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区