算法与数据结构专项练习6

1.排序方法中，将整个无序序列分割成若干小的子序列并分别进行插入排序的方法是（）
正确答案: A
希尔排序
冒泡排序
插入排序
选择排序
解析：
希尔排序：先将整个序列按一定增量分割为若干子序列分别进行直接插入排序，随后不断减少增量，当增量减至1时，整个文件恰被分成一组，算法便终止
其最坏时间复杂度依然为O(n2)
2.对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下（）
第一趟 ： 2，12，16，5，10，88
第二趟 ： 2，12，5，10，16，88
第三趟 ： 2，5，10，12，16，88
则采用的排序方法可能是 （）
正确答案: A
冒泡排序
希尔排序
归并排序
基数排序
解析：
冒泡排序每一趟都会保证最大元素就位
希尔排序每一趟会使以w为间隔的元素有序
归并排序则是依次保证以1、2、4、8…为块划分的局部有序
基数排序每一趟保证各个数对应的位从低位到高位有序
3.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关()
正确答案: D
直接插入排序
起泡排序
快速排序
直接选择排序
解析：

4.Shell排序是一种什么排序（）。
正确答案: A
插入
选择
交换
归并
解释：

shell‘排序：先将整个待排记录序列分割成为若干个子序列，然后分别进行直接插入排序。待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
5.下列哪个算法是对一个list排序的最快方法（）
正确答案: A
快速排序
冒泡排序
二分插入排序
线性排序
解析：
ist采用链式结构存储，在C++ STL中的list采用双向链表存储，比较适合用快速排序进行排序，这是由快速排序不需要随机访问元素的特点决定的。
冒泡排序适合list，但是算法复杂度为O(n^2)，没有快速排序快。
二分插入排序算法适合顺序存储情况，不适合链式存储
6.将5不同的数据进行交换排序，至多需要比较多少次
正确答案: B 你的答案: A (错误)
9
10
15
20
解析：
首先随便选择一个数为基数，再选择一个数和它比较就是1次，选择第三个数最多比较2次就可以确定它的位置，选择第四个数最多比较3次也就能够确定它的位置，最后一个数最多 比较4次同样可以确定它的位置了。1+2+3+4=10.
7.将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是_____。
正确答案: C
2-6-3-5-4-1-7
6-2-3-5-4-1-7
6-5-3-2-4-1-7
1-5-3-2-4-6-7
5-4-3-2-1-6-7
5-1-3-2-4-6-7
解析：
原数组已经是一个大顶堆，可直接开始排序。
（大顶堆：每个节点的值都不小于自己两个左右子节的完全二叉树）
每轮输出堆顶元素后，以堆中最后一个元素代替之（由于此题要求原地排序，即不产生额外的空间，堆顶元素与最后一个元素交换）。再将新的顶点元素不断与其子节点中大于该元素的较大者交换，直到该元素大于其左右两个子节点，或成为叶子节点。此时将剩余元素调整成一个新的大顶推。
7 2 6 6
/ \ / \ / \ /
6 3 ==> 6 3 ==> 2 3 ==> 5 3
/ \ / \ / \ / / \ / / \ /
5 4 1 2 5 4 1 7 5 4 1 7 2 4 1 7

由此得出，第一轮结束后的顺序是：6,5,3,2,4,1,7。
8.对下列四种排序方法,在排序中关键字比较次数同记录初始排列无关的是()
正确答案: B
直接插入
折半插入
快速排序
归并排序
解析：
直接插入排序很明显，在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；
折半插入排序，比较次数是固定的，与初始排序无关；
快速排序，初始排序不影响每次划分时的比较次数，都要比较n次，但是初始排序会影响划分次数，所以会影响总的比较次数；
归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较n次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较2*n-1次，所以与初始排序有关。