《数据结构》形成性考核册

第九章 排序

一、 填空题

1、 在直接选择排序中，记录比较次数的时间复杂度为_____________，记录移动次数的时间复杂度为_____________ 。

2、 冒泡排序是一种_____________（稳定/不稳定？）的排序算法。

3、 20个记录进行归并排序时，共需要进行____________趟归并，在第三趟归并时是把长度为_____________的有序表两两归并为长度为_______________的有序表。 4、 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，在冒泡排序、快速排序、堆排序及归并排序四种排序方法中， 最好选用_____________排序方法。

5、 对n个元素的序列进行冒泡排序时，最少的比较次数是_____________。 6、 在插入排序和选择排序中，若初始数据基本正序，则选用_____________；若初始数据基本反序，则选用_____________。

7、 在待排序的元素序列基本有序的前提下，插入排序、冒泡排序、快速排序及归并排序中效率最高的是_____________排序方法。

8、 一组记录的排序码为（46，79，56，38，40，84），利用堆排序方法建立的初值堆为____________________________。

9、 快速排序在平均情况下的时间复杂度为______________，在最坏情况下的时间复杂度为______________。

10、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为______________，整个堆排序过程的时间复杂度为______________。

11、 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较______________次。 12、 假定一组记录的排序码为（46，79，56，38，40，80），对其进行快速排序的过程中，对应二叉搜索树的深度为_____________，分支结点数为_____________。

第 41 页 共 49 页

二、 应用题

1、 已知一组元素的排序码为：

（46，74，16，53，14，26，40，38，86，65，27，34）

（1）利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。

（2）利用直接选择排序方法写出每次选择和交换后的排列结果；

第 42 页 共 49 页

（3）利用堆排序的方法写出在构成初始堆和利用堆排序的过程中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。

第 43 页 共 49 页

（4） 利用快速排序的方法写出每一层划分后的排列结果，并画出由此快速排序得到的

二叉搜索树。

（5） 利用归并排序的方法写出每一趟二路归并排序后的结果。

第 44 页 共 49 页