发布时间 : 星期二 文章数据结构习题册更新完毕开始阅读2b2a7704e45c3b3567ec8b91
10. 以下说法错误的是（ ）
A、直接插入排序的空间复杂度为O(1)。 B、快速排序附加存储开销为O(log2n)。 C、堆排序的空间复杂度为O(n)。
D、二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 11. 以下不稳定的排序方法是（ ）
A、直接插入排序 B、冒泡排序 C、直接选择排序 D、二路归并排序 12. 以下稳定的排序方法是（ ）
A、快速排序 B、冒泡排序 C、直接选择排序 D、堆排序
2
13. 以下时间复杂性不是O(n)的排序方法是（ ）
A、直接插入排序 B、二路归并排序 C、冒泡排序 D、直接选择排序 14. 以下时间复杂性不是O(nlog2n)的排序方法是（ ）
A、堆排序 B、直接插入排序 C、二路归并排序 D、快速排序 15. 快速排序方法在（ ）情况下最不利于发挥其长处。 A、 要排序的数据量太大 B、 要排序的数据中含有多个相同值 C、 要排序的数据已基本有序 D、 要排序的数据个数为奇
16. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（ ）排序法。 A、起泡排序 B、快速排序 C、堆排序 D、基数排序 17. 快速排序在最坏的情况下的时间复杂度是（ ）
23
A、O(log2n) B、O(nlog2n) C、O(n) D、O(n)
18. 一组记录的关键码为（46，79，56，38，40，84）则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）
A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79
19. 若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行（ ）次比较。
A、33 B、45 C、70 D、91 20. 一组记录的关键字为（32，41，15，39，77，12，48，30，52），按2－路归并排序的方法对该序列进行一趟归并后的结果为（ ）
A、15,32,41,12,39,77,30,48,52 B、12,15,32,39,41,77,30,48,52 C、32,41,15,39,12,77, 30,48,52 D、12,15,30,32,39,41,48,52,77
二、判断题
1． 如果某种排序算法是不稳定的，则该方法没有实际意义。
2． 对于n个记录的集合进行冒泡排序，所需要的平均时间是O（nlog2n）。 3． 对于n个记录的集合进行归并排序，所需要的平均时间是O（nlog2n）。 4． 对于n个记录的集合进行快速排序，所需要的平均时间是O（n）。 5． 堆排序所需的时间与待排序的记录个数无关。
三、填空题 1、在直接插入和直接选择排序中，若初始数据基本有序，则选用（ ），若初始数据基本反序，则选用（ ）。 2、在对一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（ ），在整个排序过程中共需进行（ ）趟才可完成。 3、n个记录的冒泡排序算法所需最大移动次数为（ ），最小移动次数为（ ）。
25
4、对n个结点进行快速排序，最大比较次数为（ ）。
5、对于直接插入排序、冒泡排序、简单选择排序、堆排序、快速排序有：（1）当文件“局部有序”或文件长度较小时，最佳的内部排序方法是（ ）。（2）快速排序在最坏情况下时间复杂度是（ ）比（ ）性能差；（3）就平均时间而言，（ ）最佳。
6、在堆排序、快速排序和归并排序中，若只从存储时间考虑，则应首先选取（ ）方法，其次选用（ ）方法，最后选用（ ）方法；若只从排序结果的稳定性考虑，则应选取（ ）方法；若只从平均情况下排序最快考虑，则应选取（ ）方法，若只从最坏情况下排序最快并节省内存，则应选取（ ）方法。
四、简答题
1、 简要回答下列问题：
（1） 什么是内部排序、外部排序？（2）什么是排序方法的稳定性？ 2、 已知序列（70，83，100，65，10，32，7，9），请给出采用插入排序、快速排序和冒泡排序方法对
该序列做升序排序的每一趟的结果。
26