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

一、单项选择题

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

一次划分结束。

2． 为支持 中视频文件的快速随机播放, 播放性能最好的文件数据块组织方式是（ ）

A. 连续结构

B. 链式结构

C. 直接索引结构

D. 多级索引结钩

【答案】A

【解析】为了实现快速随机播放, 要保证最短的查询时间, 即不能选取链表和索引结构, 因此连续结构最优。

3． 某计算机主存容量为64KB ，其中ROM 区为4KB ，其余为RAM 区，按字节编址. 现要用2K ×8位的ROM 芯片和4K ×4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）

A.1、15

B.2、15

C.1、30

D.2、30

【答案】D

【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB. 存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种. 选用2Kx8位的ROM 芯片，只需采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用(60)/4*2片芯片进行字和位同时扩展便可得60KB 的RAM 区.

4． 已知一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，则该完全二叉树的结点个数最多是（ ）.

A.39

B.52

C.111

D.119

【答案】C

【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层. 题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度. 根据题意，一棵完全二叉树的第6层(设根为第1层) 有8个叶结点，可知此二叉树的高度是6或7. 题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7. 由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是

目中二叉树的第6层结点数是. 又根据二叉树的性质1可知，题个结点，已知有8个叶子结点，那么其余32﹣8＝24个结点均为分支结点，这些结点在第7层上最多有48个子结点(即叶子结点). 所以此二叉树的结点数最多 可达

5． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是

取值的个数是（ ） A. B. C.

D. 无法确定

【答案】C

【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。

6． 在任意一棵非空二叉排序树T1中, 删除某结点v 之后形成二叉排序树T2, 再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中, 正确的是（ ）

Ⅰ. 若v 是T1的叶结点, 则T1与T3不同

Ⅱ. 若v 是T1的叶结点, 则T1与T3相同

。若, 则, 则可能

Ⅲ. 若v 不是T1的叶结点, 则T1与T3不同

Ⅳ. 若v 不是T1的叶结点, 则T1与T3相同

A. 仅Ⅰ、Ⅲ

B. 仅Ⅰ、Ⅳ

c. 仅Ⅱ、Ⅲ

d. 仅Ⅱ、Ⅳ

【答案】C

【解析】在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中, 如果删除的结点是叶子结点那么在插入结点后, 后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点, 那么再插入这个结点后, 后来的二叉树可能发生变化, 不完全相同。

7． 单处理机系统中，可并行的是（ ）.

(1)进程与进程

(2)处理机与设备

(3)处理机与通道

(4)设备与设备

A. (1)、(2)和(3)

B. (1)、(2)和(4)

C. (1)、(3)和(4)

D. (2)、(3)和(4)

【答案】D

【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.

8． 将两个各有N 个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。

A.N

B.2N －1

C.2N

D.N －1

【答案】A

【解析】归并排序基本思想:归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。归并排序最好情况下的复杂度为O(n)。