若对27个元素只进行3趟多路归并排序，则选取的归并路数为（）

正确答案：A

正确答案：A
解析：排序是将无序的记录序列调整为有序记录序列的一种操作。直接插入排序：插入排序的准则是，在有序序列中插入新的记录以达到扩大有序区的长度的目的。起泡排序：起泡排序是交换类排序方法中的一种简单排序方法。其基本思想为依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录。希尔排序：希尔排序又称“缩小增量排序”，它的基本思想是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序。快速排序：起泡排序是通过一趟“起泡”选定关键字最大的记录，所有剩余关键字均小于它的记录继续进行排序。快速排序则是通过一趟排序选定一个关键字介于“中间”的记录，从而使剩余记录可以分成两个子序列分别继续排序，通常称该记录为“轴枢”。堆排序：利用堆的特性进行的排序方法即为“堆排序”。“堆排序”是一种选择类的排序方法。归并排序：归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。最简单的情况是，只含一个记录的序列显然是个有序序列，经过“逐趟归并”使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列为止。2-路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列“归并”为一个有序序列。基数排序：利用多关键字排序的思想。快速排序、堆排序或归并排序平均时间复杂度较低，为O(nlogn)。直接插入排序、起泡排序、归并排序和基数排序是稳定的。

正确答案：A,C
【解析】①在初始序列杂乱无序的前提下，最快的是快速排序。②若要求辅助空间为O(1)，应选堆排序。③若要求排序稳定，且关键字为实数，则应选归并排序和基数排序。

正确答案：B

正确答案：A
本题主要考查排序算法。本题给出的数组如果采用直接插入排序，那么其排序过程如下：首先1和1比较找到合适的插入位置，然后2和1比较，找到合适的插入位置；然后4和2比较，找到4的合适插入位置，然后7和4比较，找到7的合适插入位置，然后5和7比较，因为5比7小，因此要与4比较，然后就找到了5的合适位置，整个排序过程结束。总的比较次数为1+1+1+1+2=6次。归并排序的算法思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。其过程如下：1和1比较，然后归并，2和4比较，然后归并，7和5比较，然后归并，解析来将再将[1,1]和[2,4]归并，用2分别与两个1比较得到[1,1,2,4],然后再用[1,1,2,4]与[5,7]归并。这时，用5与[1,1,2,4]中每个元素分别比较一次，最后即可得到整个有序序列。总的比较次数为：1+1+1+2+4=9次。堆排序的基本思想是先将序列建立堆，然后输出堆顶元素，再将剩下的序列建立堆，然后再输出堆顶元素，依此类推，直到所有元素均输出为止。因此在堆排序过程中，最重要的就是建堆。本题中给出的数组序列就是一个小顶堆，然后输出堆顶，将剩下的部分调整为小顶堆，调整的过程为，首先将最后一个元素5置换到堆顶，然后用5与左孩子结点比较，由于大于左孩子，因此与其置换位置，然后值为5的结点仍然大于其左孩子结点，再置换位置，这样就得到了新的小顶堆，这个过程总共比较2次。后面的排序过程是同样的道理。本题采用堆排序算法总共的比较次数为7次。快速排序的基本思想是：①以某个元素为支点（通常是第一个元素），通过比较关键码和交换记录，将待排序的序列分成两个区间。其中左区间中所有元素的关键字均不大于支点元素的关键字，而右区间中所有元素的关键字均不小于支点元素的关键字。称此过程为一次划分；②分别对左右区间的待排序序列，再按照以上方法进行划分，直到整个序列按关键字有序为止。由于本题给出的例子基本是从小到大有序，不适合采用快速排序发，其总共需要的比较次数为15次。

参考答案：A

正确答案：B
解析：归并就是将两个或两个以上的有序表组合成一个新的有序表。设三趟归并中每次归并x个有序表，则第一趟归并后剩余27/x个表，第二趟归并后剩余27/(x2)个表，归并三次后剩余27/(x3)。令27/(x3)=1，则x=3。故选取的归并路数为3。

正确答案：A

正确答案：√

答案：A

解析：