25版王道数据结构课后习题详细分析第八章 8.2 插入排序

本文主要是介绍25版王道数据结构课后习题详细分析第八章 8.2 插入排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、单项选择题

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

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

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

解析：第一趟:EE为一组，比较;AS为一组，比较;ST为一组，比较;YI为一组，比较后交换;QO为一组，比较后交换;UN为一组，比较后交换，结果为EASIONESTYQU。第二趟:EEY为一组，用直接插入排序需要依次比较Ⅰ和E、E和I、E和E、Y和I;AOSQ为一组，依次比较О和A、S和O、Q和S、Q和O;SNTU为一组，依次比较N和S、T和S、U和T。第一趟比较次数为6，第二趟比较次数为11，总比较次数为17。

正确答案：

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

解析：第一趟增量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。

正确答案：

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

解析：虽然折半插入排序是对直接插入排序的改进，但它改进的只是比较的次数，而移动次数未发

生变化,时间复杂度仍为O(2)。

正确答案：

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

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

正确答案：

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

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

正确答案：

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

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

正确答案：

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

解析：折半插入排序与直接插入排序都将待插入元素插入前面的有序子表，区别是:确定当前记录在前面有序子表中的位置时，直接插入排序采用顺序查找法，而折半插入排序采用折半查找法。排序的总趟数取决于元素个数n，两者都是n-1趟。元素的移动次数都取决于初始序列，两者相同。使用辅助空间的数量也都是O(1)。折半插入排序的比较次数与序列初态无关，时间复杂度为为O(nlogzn);而直接插入排序的比较次数与序列初态有关，时间复杂度为O(n)一O(n2)。

正确答案：

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

解析：首先，第二个元素为1，是整个序列中的最小元素，可知该希尔排序为从小到大排序。然后考虑增量问题，若增量为2，则第1+2个元素4明显比第1个元素9要小，排除A。若增量为3，则第i,i+3,i+6 (i=1,2,3）个元素都为有序序列，符合希尔排序的特点。若增量为4，则第1个元素9比第1+4个元素7要大，排除C。若增量为5，则第1个元素9比第1+5个元素8要大，排除D。

正确答案：

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