数据结构与算法-考研试题(中国科学院计算机技术研究所 1998年内部排序)

单项选择（1998年中国科学院计算机技术研究所）

若需在O(log2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是【】。

A、快速排序

B、堆排序

C、归并排序

D、直接插入排序

答案解析

C

【解析】

快速排序和堆排序都是不稳定的，排除；

归并排序稳定，时间复杂度O(nlog₂n)，满足条件；

直接插入排序，时间复杂度为O(n²)，排除。

讨论

数据结构与算法

在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是【】。

下述排序算法中，所需辅助存储量最多的是__________，所需辅助存储量最少的是__________，平均速度最快的是__________。A. 快速排序 B. 归并排序 C. 堆排序

在分析二叉查找树性能时常加入失败结点，即外结点，从而形成扩充的二叉树。若设失败结点i所在层次为li，那么查找失败到达失败结点时所做的数据比较次数是多少？

最佳二叉树是AVL树（平衡二叉树）。

二叉树中，具有两个子女的结点的中序后继结点最多只能有一个子女。

若散列表的负载因子α<1，则可避免碰撞的产生。

设a、b、c、d和e这5个字符的编码分别为1、2、3、4和5，并设标识符依以下次序出现ac、bd、aa、be、ab、ad、cd、bc、ae和cd。要求用哈希（Hash）方式将它们存放在具有10个位置的表中。① 对上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少。② 用线性探测再散列法解决冲突。写出上述各关键字在表中的位置。

设有12个数据{25，40，33，47，12，66，72，87，94，22，5，58}，它们存储在散列表中，利用双散列解决冲突，要求插入新数据的平均查找次数不超过3次。① 该散列表的大小m应该设计多大？② 试为该散列表设计相应的散列函数（用除留余数法）并计算寻找下一个“空位”时向前跨步步长的再散列函数。③ 顺次将各个数据散列到表中。④ 计算查找成功的平均查找次数。

若杂凑表（Hash）的地址范围为[0,9]，杂凑函数为H(key)=(key2+2) MOD 9，并采用链地址法处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入杂凑表的状态。

假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行【】次探测。

内部排序

下列排序算法中，哪些时间复杂度不会超过nlogn【】。

初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为【】。

对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为__________。

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的位置发生颠倒，则称该排序算法是不稳定的，【】就是不稳定的排序算法。

下列排序算法中，不稳定的是【】。Ⅰ. 希尔排序Ⅱ. 归并排序Ⅲ. 快速排序Ⅳ. 堆排序Ⅴ. 基数排序

使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢【】。

若有n个元素已构成一个小根堆，那么如果增加一个元素Kn+1，请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，应该选【】。

快速排序的速度在所有排序方法中为最快，而且所需附加的空间也最少。

在起泡（冒泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，请举例说明之。快速排序过程中有没有这种现象？

#tts_2#

#tis_2#