一、单项选择题
————————————————————
————————————————————
解析：我们知道插入排序不能保证在一趟排序结束后一定有元素放在最终位置上。事实上，归并排序也不能保证。例如，序列{6,5,7,8,2,1,4,3}进行一趟二路归并排序(从小到大)后为{5,6,7,8,1,2,3,4}，显然它们都未被放在最终位置上。
正确答案：
————————————————————
————————————————————
解析：基数排序是基于关键字各位的大小进行排序的，而不是基于关键字的比较进行的
正确答案：
————————————————————
————————————————————
解析：归并排序在平均情况和最坏情况下的空间复杂度都是O(n)，快速排序只在最坏情况下才是O(n)，平均情况是O(logn)。因此，归并排序是本章所有排序算法中占用辅助空间最多的。
正确答案：
————————————————————
————————————————————
解析：前面已讲过选择排序的比较次数与序列初始状态无关，归并排序的比较次数的数量级也与序列的初始状态无关。读者应能从算法的原理方面来考虑为什么和初始状态无关。
正确答案：
————————————————————
————————————————————
解析：N个元素进行k路归并排序的趟数m满足kT=N，即m=「 log:N，本题中为「 logzn To
正确答案：
————————————————————
————————————————————
解析：N个元素进行k路归并排序的趟数m满足kT=N，这里要求的是k，代入可得k=3。
正确答案：
————————————————————
————————————————————
解析：注意，当一个表中的最小元素比另一个表中的最大元素还大时，比较的次数是最少的，仅比较N次;而当两个表中的元素依次间隔地比较时，即a<b<a<b<…<a,<b,时，比较的次数是最多的，为2N-1次。
建议读者对此举一反三:若将本题中的两个有序表的长度分别设为M和N,
则最多(或最少)
的比较次数是多少?时间复杂度又是多少?
正确答案：
————————————————————
————————————————————
解析：第一趟归并后{1,2}，{4,63}，{3,5}，{7,8}，共比较4次;第二趟归并后{1,2,4,6},{3,5,7,8}共比较4次;第三趟归并后{1,2,3,4,5,6,7,8}，共比较6次。三趟归并共需进行14次比较。
正确答案：
————————————————————
————————————————————
解析：由于这里采用二路归并排序算法，而且是第二趟排序，因此每4个元素放在一起归并。可将序列划分为{25,50,15,35}，{80,85,20, 40}和36,70}，分别对它们进行排序后有{15.25,35,50%.{20,40,80,85}和{36, 70}。
正确答案：
————————————————————
————————————————————
解析：按照所有中国人的生日排序，一方面N是非常大的，另一方面关键字所含的排序码数为2,且一个排序码的基数为12，另一个排序码的基数为31，都是较小的常数值，因此采用基数排序可以在O(N)内完成排序过程。
正确答案：
————————————————————
————————————————————
解析：本题思路来自基数排序的LSD，首先应确定k、k的排序顺序，若先排k再排k，则排序结果不符合题意，排除A和C。再考虑排序的稳定性，当k排好序后，再对k排序，若对k排序采用的方法是不稳定的，则对于k相同而k不同的元素可能会改变相对次序，从而不一定能满足题设要求。直接插入排序是稳定的，而简单选择排序是不稳定的，只能选D。
正确答案：
————————————————————
————————————————————
解析：基数排序有MSD和LSD两种，基数排序是稳定的。对于A，不符合LSD 和 MSD:对于B，符合MSD，但关键字42、46的相对位置发生了变化;对于D，不符合LSD 和 MSD.
正确答案：
————————————————————
————————————————————
解析：基数排序中建立的队列个数等于进制数。
正确答案：
————————————————————
————————————————————
解析：快速排序的平均空间复杂度是O(logn)，归并排序的空间复杂度是O(n)，其他都是O(1)。
正确答案：
————————————————————
————————————————————
解析：考虑两个升序链表合并，两两比较表中元素，每比较一次，确定一个元素的链接位置（取较小元素，头插法)。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，因为2max(m,n)≥m+n，所以时间复杂度为O(max(m,n))。此外，每次比较把两个链表中的较小结点插入新链表的表头，直到一个链表为空，因为原链表是升序排列的，要求合并后为降序排列的，因此还要把另一个链表剩下的结点一一插入新链表的表头，不论是最好情况还是最坏情况，都需要遍历两个链表中的所有结点。
正确答案：
————————————————————
————————————————————
解析：
正确答案：
————————————————————
————————————————————
解析：基数排序的元素移动次数与序列初态无关，而其他三种排序算法都与序列初态有关。
正确答案：
————————————————————
————————————————————
解析：基数排序是一种稳定的排序算法。由于采用最低位优先（LSD）的基数排序，即第一趟对个位进行分配和收集操作，因此第一趟分配和收集后的结果是{151,301,372,892,93,43,485,946,146,236,327,9}，元素372之前、之后紧邻的元素分别是301和892。
正确答案：
————————————————————
————————————————————
解析：送分题。本书对归并的定义原话是“归并的含义是将两个或两个以上的有序表合并成一个新的有序表”，而二路归并是将两个有序表合并为一个新的有序表。
正确答案：
二、综合应用题
————————————————————
————————————————————
解答：
n= 10，需要排序的趟数=l log2101=4，各趟的排序结果如下;初始序列:503,87,512,61,908,170,897,275,653,462
第一趟:87,503,61,512,170,908,275,897,462,653（长度为2)第二趟:61,87,503,512,170,275,897,908,462,653（长度为4)第三趟:61,87,170,275,503,512,897,908,462,653（长度为8)第四趟:61,87,170,275,462,503,512,653,897,908（长度为10)
————————————————————
————————————————————
解答：
