对于n个记录的集合进行归并排序，所需的附加空间消耗是（）

填空题对于n个记录的集合进行归并排序，所需的附加空间消耗是（）

1.填空题二路归并排序的时间复杂度是（）

O（nlog₂n）

2.填空题在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。

3.填空题若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是（）的排序方法。

4.填空题堆排序是不稳定，空间复杂度为（）。在最坏情况下，其时间复杂度也为（）

O（1）；O（nlog₂n）

5.填空题在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是（），需要内存容量最多的是（）

6.填空题对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为（），在整个排序过程中最多需要进行（）趟排序才可以完成。

7.填空题当向一个大根堆插入一个具有最大值的元素时，需要逐层（）调整，直到被调整到（）位置为止。

8.填空题对两棵具有相同关键字集合而形状不同的二叉排序树，（）遍历它们得到的序列的顺序是一样的。

9.填空题散列表的查找效率主要取决于散列表造表时选择的（）和（）

10.填空题在分块查找中首先查找（），然后再查找相应的（）