8.2 插入排序·习题
复习入口
8.2 插入排序 · 8.2.1 直接插入排序 · 8.2.2 折半插入排序 · 8.2.3 希尔排序
本节共23题:选择题21题,综合应用题2题。每题答案紧接题目折叠显示。
文字转录进度:23/23题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P342 · 解析P344 · 目视转录
对 5 个不同数据元素进行直接插入排序,最多需要的比较次数是( )。
A. 8
B. 10
C. 15
D. 25
查看答案与解析
答案:B。
最坏需 n(n−1)/2 次关键字比较,n=5 时为 10。此处不考虑与哨兵的比较。
单项选择题 02
原书题目P342 · 解析P344 · 目视转录
待排序元素序列基本有序时,效率最高的算法是( )。
A. 直接插入排序
B. 简单选择排序
C. 快速排序
D. 归并排序
查看答案与解析
答案:A。
基本有序时,直接插入排序时间接近 ,其他算法时间均大于 。
单项选择题 03
原书题目P342 · 解析P344 · 目视转录
图书馆计算机类书籍区共有 12 列书架,书架上的书都按编号排列。其中有些书被读者放错位置,但通常不超过一个书架。将这些书重新放回正确位置,应采用何种算法?( )
A. 堆排序
B. 直接插入排序
C. 归并排序
D. 简单选择排序
查看答案与解析
答案:B。
大部分图书有序,直接插入排序较合适。
单项选择题 04
原书题目P343 · 解析P344 · 目视转录
对有 n 个元素的顺序表做直接插入排序,最坏所需比较次数为( ),最好所需比较次数为( )。
A. n−1
B. n+1
C. n/2
D. n(n−1)/2
查看答案与解析
答案:D、A。
逆序时需比较 1+2+…+(n−1)=n(n−1)/2 次;正序时只需 n−1 次。不考虑与哨兵比较。
单项选择题 05
原书题目P343 · 解析P344 · 目视转录
数据序列 {8,10,13,4,6,7,22,2,3} 只能是( )两趟排序后的结果。
A. 简单选择排序
B. 冒泡排序
C. 直接插入排序
D. 堆排序
查看答案与解析
答案:C。
冒泡、选择排序两趟后应有两个最大或最小元素在最终位置;插入排序两趟后前三个元素局部有序,故只能是插入排序。
注意:每趟可确定一个元素最终位置的有冒泡、简单选择、堆、快速排序;前三者可形成全局有序子序列,快速排序仅确定枢轴元素位置。
单项选择题 06
原书题目P343 · 解析P345 · 目视转录
用直接插入排序对下列 4 个表从小到大排序,比较次数最少的是( )。
A. 94,32,40,90,80,46,21,69
B. 21,32,46,40,80,69,90,94
C. 32,40,21,46,69,94,90,80
D. 90,69,80,46,21,32,94,40
查看答案与解析
答案:B。
越接近正序,比较越少,B、C 较接近正序。B 各趟插入 32、46 各比较 1 次,插入 40 比较 2 次,插入 80 比较 1 次,插入 69 比较 2 次,之后同理,共 9 次;C 共 11 次,故选 B。
单项选择题 07
原书题目P343 · 解析P345 · 目视转录
下列算法中,( )可能在最后一趟开始前所有元素都不在最终位置。
A. 堆排序
B. 冒泡排序
C. 直接插入排序
D. 快速排序
查看答案与解析
答案:C。
直接插入排序中,若最后一个元素应插入第一位置,则此前有序子序列的所有元素都不在最终位置。
单项选择题 08
原书题目P343 · 解析P345 · 目视转录
希尔排序属于( )。
A. 插入排序
B. 交换排序
C. 选择排序
D. 归并排序
查看答案与解析
答案:A。
希尔排序由直接插入排序改进提出,本质仍属于插入排序。
单项选择题 09
原书题目P343 · 解析P345 · 目视转录
对 {15,9,7,8,20,−1,4} 做希尔排序,一趟后变为 {15,−1,4,8,20,9,7},本趟增量为( )。
A. 1
B. 4
C. 3
D. 2
查看答案与解析
答案:B。
记录只在组内交换。9 与 −1 交换、7 与 4 交换,位置差均为 4,因此增量为 4。
单项选择题 10
原书题目P343 · 解析P345 · 目视转录
序列 {15,9,7,8,20,−1,4} 一趟排序后变成 {9,15,7,8,20,−1,4},所采用的方法是( )。
A. 选择排序
B. 快速排序
C. 直接插入排序
D. 冒泡排序
查看答案与解析
答案:C。
前两个元素局部有序,显然一趟直接插入排序有效,也可排除其他方法。
单项选择题 11
原书题目P343 · 解析P345 · 目视转录
对 {98,36,−9,0,47,23,1,8,10,7} 做希尔排序,下列( )是增量 4 的一趟结果。
A. {10,7,−9,0,47,23,1,8,98,36}
B. {−9,0,36,98,1,8,23,47,7,10}
C. {36,98,−9,0,23,47,1,8,7,10}
D. 以上都不对
查看答案与解析
答案:A。
相距 4 的记录组成一组,组内直接插入排序,只有 A 满足要求。
单项选择题 12
原书题目P343 · 解析P345 · 目视转录
对 {E,A,S,Y,Q,U,E,S,T,I,O,N} 按字典顺序排序,采用增量 d=6,3,1 的希尔排序。前两趟后关键字总比较次数为( )。
A. 15
B. 17
C. 16
D. 18
查看答案与解析
答案:B。
第一趟分组 EE、AS、ST、YI、QO、UN,每组比较 1 次,后三组交换,得 EASIONESTYQU,共 6 次。
第二趟分组 EIEY、AOSQ、SNTU。EIEY 依次比较 I和E、E和I、E和E、Y和I,共 4 次;AOSQ 比较 O和A、S和O、Q和S、Q和O,共 4 次;SNTU 比较 N和S、T和S、U和T,共 3 次。第二趟共 11 次,两趟总共 17 次。
单项选择题 13
原书题目P343 · 解析P345 · 目视转录
输入序列 {13,24,7,1,8,9,11,56,34,51,2,77,5},增量 d=5,3,1,希尔排序两趟后的结果为( )。
A. 1,7,8,9,13,24,11,34,51,2,5,56,77
B. 1,7,5,2,8,9,24,11,34,51,13,77,56
C. 2,11,5,1,8,9,24,7,34,51,13,77,56
D. 2,5,11,1,8,9,7,24,34,13,51,77,56
查看答案与解析
答案: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。
单项选择题 14
原书题目P343 · 解析P345 · 目视转录
折半插入排序的时间复杂度为( )。
A.
B.
C.
D.
查看答案与解析
答案:C。
只改进比较次数,移动次数不变,时间复杂度仍为 。
单项选择题 15
原书题目P343 · 解析P345 · 目视转录
某些算法每趟都会把一个元素放到最终位置。( )不会保证出现此种情况。
A. 希尔排序
B. 堆排序
C. 冒泡排序
D. 快速排序
查看答案与解析
答案:A。
希尔排序基于插入排序,不一定在每趟将某元素放到最终位置。
单项选择题 16
原书题目P343 · 解析P345 · 目视转录
以下排序算法中,不稳定的是( )。
A. 冒泡排序
B. 直接插入排序
C. 希尔排序
D. 归并排序
查看答案与解析
答案:C。
希尔排序是复杂的插入排序,是不稳定的排序算法。
单项选择题 17
原书题目P344 · 解析P345 · 目视转录
以下排序算法中,稳定的是( )。
A. 快速排序
B. 堆排序
C. 直接插入排序
D. 简单选择排序
查看答案与解析
答案:C。
插入、交换、选择三类算法中,通常简单方法稳定,如直接插入、折半插入、冒泡;但简单选择是例外。复杂方法如希尔、快速、堆排序不稳定。
单项选择题 18
原书题目P344 · 解析P345 · 目视转录
【2012 统考真题】同一待排序序列分别进行折半插入排序与直接插入排序,两者可能不同的是( )。
A. 排序总趟数
B. 元素移动次数
C. 辅助空间数量
D. 元素间比较次数
查看答案与解析
答案:D。
两者都把元素插入前面有序子表,区别是确定位置时一个用折半查找,一个用顺序查找。总趟数均 n−1,移动次数取决于初始序列且相同,辅助空间均 。折半插入的比较次数与初始状态无关,为 ;直接插入的比较次数与初态有关,为 ~。
单项选择题 19
原书题目P344 · 解析P346 · 目视转录
【2014 统考真题】用希尔排序,第一趟结果为 9,1,4,13,7,8,20,23,15,该趟增量可能为( )。
A. 2
B. 3
C. 4
D. 5
查看答案与解析
答案:B。
第二元素 1 为全局最小,可知是升序。增量 2 时第 1+2 个元素 4 小于首元素 9,排除;增量 3 时同组的 1、4、7 位置元素组成 9,13,20,是有序的,其他组也有序;增量 4 时 9>7,排除;增量 5 时 9>8,排除。故选 3。
单项选择题 20
原书题目P344 · 解析P346 · 目视转录
【2015 统考真题】希尔排序组内采用的是( )。
A. 直接插入排序
B. 折半插入排序
C. 快速排序
D. 归并排序
查看答案与解析
答案:A。
先按增量将元素分成子序列,各组直接插入排序,再缩小增量继续。增量足够小时整个序列基本有序,最后对全体做一次直接插入排序。
单项选择题 21
原书题目P344 · 解析P346 · 目视转录
【2018 统考真题】初始序列 (8,3,9,11,2,1,4,7,5,10,6),希尔排序第一趟为 (1,3,7,5,2,6,4,9,11,10,8),第二趟为 (1,2,6,4,3,7,5,8,11,10,9)。两趟增量依次为( )。
A. 3,1
B. 3,2
C. 5,2
D. 5,3
查看答案与解析
答案:D。
第一趟分组为 8,1,6;3,4;9,7;11,5;2,10,间隔 5,排序后组内递增。第二趟从第一趟结果分组为 1,5,4,10;3,2,9,8;7,6,11,间隔 3,排序后也组内递增。因此增量为 5、3。
综合应用题
综合应用题 01
原书题目P344 · 解析P346 · 目视转录
给出关键字序列 {4,5,1,2,6,3} 的直接插入排序过程。
查看答案与解析
| 趟数 | 序列 | 操作 |
|---|---|---|
| 初始 | 4,5,1,2,6,3 | |
| 1 | 4,5,1,2,6,3 | 将5插入{4} |
| 2 | 1,4,5,2,6,3 | 将1插入{4,5} |
| 3 | 1,2,4,5,6,3 | 将2插入{1,4,5} |
| 4 | 1,2,4,5,6,3 | 将6插入{1,2,4,5} |
| 5 | 1,2,3,4,5,6 | 将3插入{1,2,4,5,6} |
综合应用题 02
原书题目P344 · 解析P346 · 目视转录
给出 {50,26,38,80,70,90,8,30,40,20} 的希尔排序过程,取增量序列 d={5,3,1},结果从小到大。
查看答案与解析
| 趟数 | 增量 | 序列 |
|---|---|---|
| 初始 | 50,26,38,80,70,90,8,30,40,20 | |
| 1 | 5 | 50,8,30,40,20,90,26,38,80,70 |
| 2 | 3 | 26,8,30,40,20,80,50,38,90,70 |
| 3 | 1 | 8,20,26,30,38,40,50,70,80,90 |