超星 - 第10章内排序 - 查题吧

填空题

对n个元素的序列进行冒泡排序,最小的比较次数是,此时元素的排列情况,在的情况下比较次数最多,其比较次数为。

填空题

对n个结点进行快速排序,最大比较次数是____。

填空题

利用快速排序方法对记录(50,40,95,20,15,70,60,45,80)进行快速排序,其需递归调用的次数为,其中第二次递归调用是对一组记录进行快速排序。

填空题

从时间上看,快速排序的平均性能好于其他排序方法,但从空间上看,快速排序需要一个栈空间来实现递归,若每一趟快速排序都将记录序列均匀地分割成长度相接近的两个序列,则栈的最大深度(含最外层也进栈)为;在最坏情况下,栈的深度为;如果每次先对较短的子序列进行快速排序,则栈的最大深度降为;所需要的附加空间为。

填空题

在对一组记录(50,40,95,20,15,70,60,45,80)进行(大根)堆排序时,根据初始记录构成初始堆后,最后4条记录为____。

填空题

在内部排序中,平均比较次数最少的是,要求附加的内存容量最大的是,排序时不稳定的有等几种方法。

填空题

在归并排序中,若待排序记录的个数为20,则共需要进行趟归并,在第三趟归并中是把长度为的有序表归并为长度为的序表。

填空题

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

填空题

目前以比较操作为基础的内部排序的时间复杂度T(m)的范围是;其比较次数与待排序记录的初始状态无关的是。

填空题

在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的是,需要内存容量最多的是。

1