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。

基本有序时,直接插入排序时间接近 O(n)O(n),其他算法时间均大于 O(n)O(n)。

单项选择题 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. O(n)O(n)

B. O(nlog⁡2n)O(n\log_2n)

C. O(n2)O(n^2)

D. O(n3)O(n^3)

查看答案与解析

答案:C。

只改进比较次数,移动次数不变,时间复杂度仍为 O(n2)O(n^2)。

单项选择题 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,移动次数取决于初始序列且相同,辅助空间均 O(1)O(1)。折半插入的比较次数与初始状态无关,为 O(nlog⁡2n)O(n\log_2n);直接插入的比较次数与初态有关,为 O(n)O(n)~O(n2)O(n^2)。

单项选择题 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
14,5,1,2,6,3将5插入{4}
21,4,5,2,6,3将1插入{4,5}
31,2,4,5,6,3将2插入{1,4,5}
41,2,4,5,6,3将6插入{1,2,4,5}
51,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
1550,8,30,40,20,90,26,38,80,70
2326,8,30,40,20,80,50,38,90,70
318,20,26,30,38,40,50,70,80,90