扫码获取更多资源

●排序习题

填空题

1. 在待排序的记录序列基本有序的前提下，效率最高的排序方法是（ ）0

2. 在排序中，从待排序记录序列中依次取出记录，并将其依次放入有序序列（初始为

空）一端的方法，称为（ ）。

3. 对一组记录关键字序列｛54, 38, 96, 23, 15, 72, 60, 45, 83｝进行直接插入排序，当

把第七个记录的关键字60插入到有序序列时，为寻找插入位置需要比较（ ）次。

4. 设有1000个无序记录，希望用最快速度挑选出其中前10个关键字最大的记录，最

好选用（ ）排序方法。

5. 在堆排序、快速排序和归并排序中，如果只从存储空间考虑，则应该选取（ ）方

问答题

1. 在高度为h的堆中，最多有多少个记录？最少有多少个记录？在大根堆中，关键字 最小的记录可能存放在堆的哪些地方？

2. 将两个长度为n的有序表归并为一个长度为2n的有序表，最少需要比较n次，最多 需要比较2n-l次，试说明这两种情况发生时，两个被归并的表有什么特征。

3. 如果记录关键字序列初态是反序的，且要求输入稳定，则在直接插入排序、冒泡排序 和快速排序中选择哪种方法为宜？

4. 下列各种情况选择什么排序方法合适？

（1） n = 30,要求在最坏的情况下，排序速度最快；

（2） n=30,要求排序速度既要快，又要排序稳定。

(1) 关键字从小到大有序(kx

(2) 关键字从大到小有序(kx>k2>…>kn)0

(3) 奇数关键字顺序有序，偶数关键字顺序有序(kiVk’V…，k2〈ki…)。

(4) 前半部分元素按关键字有序，后半部分元素按关键字有序，即：虹Vk^V-Vkm， 上+1 Vkm+2V …。

应用题

1. 试构造对5个整数元素进行排序，最多只用7次比较的算法思想。

2. 对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这n个记录的初 始序列。

(1) 当n = 8时，在最好的情况下需要进行多少次比较？试说明理由。

(2) 给出n=8时的一个最好情况的初始排列实例。

3. 判别以下记录关键字序列是否为小根堆，如果不是，则把它调整为堆。

(1) ｛100, 86, 48, 73, 35, 39, 42, 57, 66, 21｝；

(2) ｛12, 70, 33, 65, 24, 56, 48, 92, 86, 33｝；

(3) ｛103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20｝；

(4) ｛05, 56, 20, 03, 23, 40, 38, 29, 61, 05, 76, 28, 100｝。

4. 如果想得到一组记录关键字序列中第k个最小元素的部分有序序列，则最好采用什 么排序方法；如果想得到一组记录关键字序列｛57, 40, 38, 11, 13, 34, 48, 75, 25, 6, 19, 9, 7｝中第四个最小元素之前的部分有序序列｛6, 7, 9, 11｝,则当使用所选择的算法实 现时，要执行多少次比较。

5. 以记录关键字序列｛265, 301, 751, 129, 937, 863, 742, 694, 076, 438｝为例，分别 写出执行以下排序算法的各趟排序结束时，关键字序列的状态。

(1)直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序

(5) 简单选择排序(6)堆排序 (7)归并排序(8)基数排序

联系我们：