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

一、单项选择题

1． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。

A. 直接插入排序

B. 起泡排序

C. 基数排序

D. 快速排序

【答案】C

【解析】C 项, 基数排序是采用分配和收集实现的, 不需要进行关键字的比较。ABD 三项都依赖关键字的比较, 不同的初始排列次序下元素移动的次数有很大变化, 最好情况元素正序, 则不用移动, 最坏情况元素反序, 则需要移动次(n为元素个数) 。

2． 下列二叉排序树中，满足平衡二叉树定义的是（ ）. A. B. C. D.

【答案】B

【解析】平衡二叉树是指左右子树高度差(平衡因子) 的绝对值不超过1的二叉树.A 项中根结

B 项中每个结点的平衡因子的绝对值均不超过1；C 项中根结点的平衡因子是；点的平衡因子是2；

D 项中根结点的平衡因子是3.

3． 下列调整中, 不可能导致饥饿现象的是（ ）

A. 时间片转移

B. 静态优先及调度

C. 非抢占式作业优先

D. 抢占式短作业优先

【答案】A

【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间, 不会产生饥饿的现象, 其余三个都会产生饥饿。

4． 求整数阶乘的算法如下, 其时间复杂度是（ ）。

A.

B.0(n) C. 2D.O(n)

【答案】B 。

【解析】设fact(n)的运行时间函数是T(n)。

该函数中语句①的运行时间是0(1), 语句②的运行时间是

算的时间。

因此, 当

则,

时

, ; 。

即fact(n)的时间复杂度为O(n)。 当11>1时, , 其中O(1)为乘法运

通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。

5． 用希尔排序方法对一个数据序列进行排序时, 若第1趟排序结果为9, 1, 4, 13, 7, 8, 20, 23, 15, 则该趟排序采用的增量(间隔) 可能是（ ）

A.2

B.3 C.4

D.5

【答案】B

【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组, 而它们是无序的, 所以A 错误

对于C , 增量为4, 那么9, 7, 15是一组, 而它们是无序的, 所以C 错误

对于D , 增量为5, 那么9, 8是一组, 降序, 1, 20是一组, 而它们是升序, 所以D 也错误。对于B ,