查找和排序(11)

习题习题习题习题习题习题习题习题习题

_________。

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

6、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的___________ 和记录的___________。

7、在堆入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有______________________ 。

8、设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。

9、直接插入排序用监视哨的作用是_________________。

10、在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较________次。

11、利用快速排序方法对记录（50，40，95，20，15，70，60，45，80）进行快速排序，其需递归调用的次数为________，其中第二次递归调用是对________组记录进行快速排序。

12、在堆排序，快速排序和归并排序中，若只从存储空间考虑，则首先选取________方法，其次选取________方法；若只从排序结果的稳定性考虑，则应选取________方法；若只 从平均情况下排序最快考虑，则应选取________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取________方法。

13、对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 的关键字开始

三、判断题

1、 直接选择排序在最好情况下的时间复杂度是O(n）。

2、 在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlogn）。

3、 在用堆排序算法排序时，如果要进行增序，则需要采用“大顶堆”。

4、 在待排数据基本有序的情况下，快速排序的效果最好。

5、 两分法插入排序所需比较次数与待排序记录的初始状态相关。

6、 希尔排序的最后一趟与直接插入排序过程相同。

7、 在任何情况下，归并排序都比简单排序速度快。

8、 堆是满二叉树。

9、堆肯定是一棵平衡二叉树。