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

一、填空题

1． 在基于关键字比较且时间为

【答案】归并；堆

2． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

3． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。

【答案】15

2n

【解析】当时，100n2>2n，而，时，100n ＜2

4． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

_ 的排序中，若要求排序是稳定的，则可选用_____

排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。

【答案】模式匹配；模式串

5． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

。当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为

一个元素时，此时堆的元素个数最少，元素个数为。

6． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。

【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

7． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。

9． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。

10．设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。 11．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2

而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

12．无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

二、单项选择题

13．数据序列(8，9，10，4，5，6，20，1，2) 只能是下列排序算法中的（ ）的两趟排序后的结果。

A. 选择排序 B. 起泡排序

C. 插入排序 D. 堆排序 【答案】C

【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。

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

A. 找 B. 队列 C. 树 D. 图 【答案】B

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

15．计算机开后, 操作系统最终被加载到（ ）

A.BIOS B.ROM C.EPROM D.RAM 【答案】D

【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区, 这段区城是RAM , 故答案选D 。

16．下面关于求关键路径的说法不正确的是（ ）。

A. 求关键路径是以拓扑排序为基础的

B. —个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D. 关键活动一' 定位于关键路径上 【答案】C

【解析】一个事件的最迟开始事件是这个事件能够拖到的最晚时间，从这个时刻开始做完这个事件不影响其后续事件的开始时间。