一、单项选择题

————————————————————

————————————————————

解析：直接插入排序在最坏的情况下要做n(n-1)/2次关键字的比较，当n=5时，关键字的比较次数为10。注意不考虑与哨兵的比较。

正确答案：B

————————————————————

————————————————————

解析：由于序列初始基本有序，因此使用直接插入排序算法的时间复杂度接近O(n)，而使用其他算法的时间复杂度均大于O(n)。

正确答案：A

————————————————————

————————————————————

解析：由于大部分图书都是有序的，因此采用直接插入排序比较合适。

正确答案：B

————————————————————

————————————————————

解析：待排序表为反序时，直接插入排序需要进行n(n-1)/2次比较(从前往后依次需要比较1,2…,n-1次):待排序表为正序时，只需进行n-1次比较。注意本题不考虑与哨兵的比较。

正确答案：D、A

————————————————————

————————————————————

解析：冒泡排序和选择排序经过两趟排序后，应该有两个最大(或最小)元素放在其最终位置：插入排序经过两趟排序后，前三个元素应该是局部有序的。只可能是插入排序。

正确答案：C

————————————————————

————————————————————

解析：越接近正序的序列，直接插入排序的比较次数就越少。B和C是比较接近正序的，然后分别判断两个序列的比较次数，以B为例：第一趟，插入32，比较1次;第二趟，插入46，比较1次;第三趟，插入40，因为40比46小但比32大，所以比较2次;第四趟，插入80，比较1次;第五趟，插入69，比较2次;以此类推，共比较9次。同理求出C的比较次数为11次。所以选B项。

正确答案：B

————————————————————

————————————————————

解析：在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置，则前面的有序子序列中的所有元素都不在最终位置上。

正确答案：C

————————————————————

————————————————————

解析：希尔排序是对直接插入排序算法改进后提出来的，本质上仍属于插入排序的范畴。

正确答案：A

————————————————————

————————————————————

解析：希尔排序将序列分成若干组，记录只在组内进行交换。由观察可知，经过一趟后9和-1交换，7和4交换，可知增量为4。

正确答案：B

————————————————————

————————————————————

解析：前两个元素已经局部有序，很明显一趟直接插入排序算法有效。再排除其他算法即可。

正确答案：C

————————————————————

————————————————————

解析：增量为4意味着所有相距为4的记录构成一组，然后在组内进行直接插入排序，经观察，只有A项满足要求。

正确答案：A

————————————————————

————————————————————

解析：

正确答案：B

————————————————————

————————————————————

解析：第一趟增量d=5，第一趟排序后，结果为2,11,5,1,8,9,24,7,34,51,13,77,56。第二趟增量d=3，第二趟排序后，结果为1,7,5,2,8,9,24,11,34,51,13,77,56。

正确答案：B

————————————————————

————————————————————

解析：虽然折半插入排序是对直接插入排序的改进，但它改进的只是比较的次数，而移动次数未发生变化,时间复杂度仍为O(n²)。

正确答案：C

————————————————————

————————————————————

解析：因为希尔排序是基于插入排序算法提出的，所以它不一定在每趟排序过程后将某一元素放置到最终位置上。

正确答案：A

————————————————————

————————————————————

解析：希尔排序是一种复杂的插入排序算法，它是一种不稳定的排序算法。

正确答案：C

————————————————————

————————————————————

解析：基于插入、交换、选择的三类排序算法中，通常简单方法是稳定的(直接插入、折半插入、冒泡)，但有一个例外就是简单选择，复杂方法都是不稳定的(希尔排序、快速排序、堆排序)。

正确答案：C

————————————————————

————————————————————

解析：

正确答案：D

————————————————————

————————————————————

解析：

正确答案：B

————————————————————

————————————————————

解析：

正确答案：A

————————————————————

————————————————————

解析：

正确答案：D

二、综合应用题

————————————————————

————————————————————

解答：

————————————————————

————————————————————

解答：