8.6 内部排序算法的比较及应用·习题
复习入口
8.6 内部排序算法的比较及应用 · 8.6.1 内部排序算法的比较 · 8.6.2 内部排序算法的应用
本节共24题:选择题21题,综合应用题3题。每题答案紧接题目折叠显示。
文字转录进度:24/24题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P382 · 解析P384 · 目视转录
若要求排序稳定,且关键字为实数,则应选( )。
A. 直接插入排序
B. 选择排序
C. 基数排序
D. 快速排序
查看答案与解析
答案:A。
稳定性排除 B、D。按本章所述基数排序实现,不能直接对 float、double 实数排序,排除 C。
单项选择题 02
原书题目P382 · 解析P384 · 目视转录
时间复杂度 且稳定的算法是( )。
A. 堆排序
B. 快速排序
C. 归并排序
D. 直接插入排序
查看答案与解析
答案:C。
堆、快速不稳定;直接插入时间复杂度为 。
单项选择题 03
原书题目P382 · 解析P384 · 目视转录
n 个结点序列中已有十分接近有序的情况,直接插入、归并、快速排序的时间复杂度依次为( )。
A.
B.
C.
D.
查看答案与解析
答案:C。
各算法的时间、空间复杂度及稳定性可参见本章表8.1。
单项选择题 04
原书题目P382 · 解析P384 · 目视转录
下列算法中,属于稳定排序的是(①),平均时间复杂度为 的是(②),最好情况下可达线性时间的是(③)。(多选。)
Ⅰ. 冒泡排序
Ⅱ. 堆排序
Ⅲ. 选择排序
Ⅳ. 直接插入排序
Ⅴ. 希尔排序
Ⅵ. 归并排序
Ⅶ. 快速排序
查看答案与解析
答案:①Ⅰ、Ⅳ、Ⅵ;②Ⅱ、Ⅵ、Ⅶ;③Ⅰ、Ⅳ。
应从原理理解稳定性。堆与归并最好、最坏时间为同一数量级,均 。
单项选择题 05
原书题目P382 · 解析P384 · 目视转录
按辅助空间比较,堆排序、快速排序、归并排序关系为( )。
A. 堆排序<快速排序<归并排序
B. 堆排序<归并排序<快速排序
C. 堆排序>归并排序>快速排序
D. 堆排序>快速排序>归并排序
查看答案与解析
答案:A。
堆空间 ;快速平均 、最坏 ;归并 。
单项选择题 06
原书题目P382 · 解析P384 · 目视转录
排序趟数与初态无关的是( )。
Ⅰ.快速 Ⅱ.简单选择 Ⅲ.冒泡 Ⅳ.基数
A. Ⅰ、Ⅲ
B. Ⅱ、Ⅳ
C. Ⅰ、Ⅱ、Ⅳ
D. Ⅰ、Ⅳ
查看答案与解析
答案:B。
冒泡趟数1~n−1,与初态有关;简单选择每趟选一个最大或最小值,固定n−1;基数每趟分配收集,固定d趟。快速的划分次数与枢轴和划分均衡性有关,初始基本有序时可能极不均衡。
单项选择题 07
原书题目P382 · 解析P384 · 目视转录
排序趟数与初态有关的是( )。
A. 直接插入排序
B. 二路归并排序
C. 快速排序
D. 堆排序
查看答案与解析
答案:C。
直接插入固定n−1趟,二路归并固定⌈log₂n⌉趟,堆建好后需n−1趟输出并调整,均与初态无关。
单项选择题 08
原书题目P382 · 解析P384 · 目视转录
对 n 个元素排序,趟数肯定为 n−1 的是( )。
A. 直接插入和快速
B. 冒泡和快速
C. 简单选择和直接插入
D. 简单选择和冒泡
查看答案与解析
答案:C。
简单选择与直接插入始终n−1;冒泡1~n−1;快速约log₂n~n−1,取决于初态及划分方法。
单项选择题 09
原书题目P382 · 解析P384 · 目视转录
序列初态 {1,2,3,4,5,10,6,7,8,9},要使元素比较次数最少,应采用( )。
A. 插入排序
B. 选择排序
C. 希尔排序
D. 冒泡排序
查看答案与解析
答案:A。
选择比较次数与初态无关,先排除。基本有序时插入比较少,本题仅n−1+4次,希尔、冒泡均远大于此。
单项选择题 10
原书题目P382 · 解析P385 · 目视转录
相同元素个数、不同初态的序列,总比较次数相同的是( )。
A. 折半插入排序和简单选择排序
B. 基数排序和归并排序
C. 冒泡排序和快速排序
D. 堆排序
查看答案与解析
答案:A。
简单选择总比较次数确定。原书认为折半插入每趟比较为 ,m为当前已排序子序列长度,因此比较次数也确定。基数不是基于比较的排序,其他算法比较次数与初态有关。
单项选择题 11
原书题目P382 · 解析P385 · 目视转录
一般情况下,以下查找效率最低的数据结构是( )。
A. 有序顺序表
B. 二叉排序树
C. 堆
D. 平衡二叉树
查看答案与解析
答案:C。
堆适合排序,但查找时整体无序,效率不及其他查找结构。
单项选择题 12
原书题目P382 · 解析P385 · 目视转录
多核CPU可同时执行独立任务,归并排序各归并段可并行。下列不能并行执行的有( )。
Ⅰ.基数 Ⅱ.快速 Ⅲ.冒泡 Ⅳ.堆
A. Ⅰ、Ⅲ
B. Ⅰ、Ⅱ
C. Ⅰ、Ⅲ、Ⅳ
D. Ⅱ、Ⅳ
查看答案与解析
答案:A。
基数每趟利用前趟已排好的序列,无法按各趟并行;快速各划分子序列互不影响,可并行;冒泡每趟处理所有未排序元素,无法按此方式并行;堆中左右子堆执行互不影响,可以并行。
单项选择题 13
原书题目P383 · 解析P385 · 目视转录
【2009 统考真题】{11,12,13,7,8,9,23,4,5} 是某算法第二趟结果,该算法只能是( )。
A. 冒泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
查看答案与解析
答案:B。
冒泡、选择每趟有元素最终就位,题中两端的 {11,12}、{4,5} 并非最终位置,排除。归并第二趟前4个元素应有序,但11,12,13,7不有序,排除。
单项选择题 14
原书题目P383 · 解析P385 · 目视转录
【2010 统考真题】对 (2,12,16,88,5,10) 排序,前三趟为:
- 2,12,16,5,10,88
- 2,12,5,10,16,88
- 2,5,10,12,16,88
可能采用的是( )。
A. 冒泡排序
B. 希尔排序
C. 归并排序
D. 基数排序
查看答案与解析
答案:A。
每趟从前向后比较使最大值沉底,符合冒泡。归并第一趟仍为(2,12,16,88,5,10),基数第一趟为(10,2,12,5,16,88),希尔也不符合。
单项选择题 15
原书题目P383 · 解析P385 · 目视转录
【2012 统考真题】每趟处理所有未确定最终位置的元素。下列每趟结束均至少确定一个元素最终位置的方法是( )。
Ⅰ.简单选择 Ⅱ.希尔 Ⅲ.快速 Ⅳ.堆 Ⅴ.二路归并
A. 仅Ⅰ、Ⅲ、Ⅳ
B. 仅Ⅰ、Ⅲ、Ⅴ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
查看答案与解析
答案:A。
简单选择每趟选最小值放最终位置;希尔只使子表局部有序,不能保证;快速使枢轴最终就位;堆每次交换根与表尾,确定其最终位置;二路归并仅合并有序段,不能保证最终就位。
单项选择题 16
原书题目P383 · 解析P385 · 目视转录
【2017 统考真题】内部排序选择归并而非插入,可能理由是( )。
Ⅰ.归并代码更短 Ⅱ.归并占用空间更少 Ⅲ.归并运行效率更高
A. 仅Ⅱ
B. 仅Ⅲ
C. 仅Ⅰ、Ⅱ
D. 仅Ⅰ、Ⅲ
查看答案与解析
答案:B。
归并代码更复杂、空间 ,插入空间 ;但归并时间 ,插入 。
单项选择题 17
原书题目P383 · 解析P385 · 目视转录
【2017 统考真题】将顺序存储更换成链式存储,时间效率会降低的是( )。
Ⅰ.插入 Ⅱ.选择 Ⅲ.冒泡 Ⅳ.希尔 Ⅴ.堆
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ、Ⅲ
C. 仅Ⅲ、Ⅳ
D. 仅Ⅳ、Ⅴ
查看答案与解析
答案:D。
插入、选择、冒泡在两种存储下均为 。希尔、堆均利用顺序存储的随机访问特性,链式存储不支持,时间复杂度会增加。
单项选择题 18
原书题目P383 · 解析P385 · 目视转录
【2019 统考真题】选择排序算法,除时空效率外,还需考虑( )。
Ⅰ.数据规模 Ⅱ.存储方式 Ⅲ.稳定性 Ⅳ.初始状态
A. 仅Ⅲ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅱ、Ⅲ、Ⅳ
D. Ⅰ、Ⅱ、Ⅲ、Ⅳ
查看答案与解析
答案:D。
小规模可选 简单算法,大规模宜 ,大到内存放不下需外部排序,Ⅰ正确。有些算法如堆仅适用顺序存储,Ⅱ正确。有稳定性要求应排除不稳定算法,Ⅲ正确。基本有序时直接插入效率高,冒泡、直接插入可达 ,归并仍为 ,Ⅳ正确。
单项选择题 19
原书题目P383 · 解析P385 · 目视转录
【2020 统考真题】对大部分已有序数组,直接插入比简单选择效率更高,原因是( )。
Ⅰ.直接插入比较次数更少。
Ⅱ.直接插入辅助空间更少。
Ⅲ.直接插入移动次数更少。
A. 仅Ⅰ
B. 仅Ⅲ
C. 仅Ⅰ、Ⅱ
D. Ⅰ、Ⅱ和Ⅲ
查看答案与解析
答案:A。
有序时直接插入比较n−1次,简单选择比较n(n−1)/2次,Ⅰ正确。两者空间都 ,Ⅱ错误。全有序时移动均0;通常直接插入需依次挪位,简单选择仅交换找到的最小值,后者移动较少,Ⅲ错误。
单项选择题 20
原书题目P383 · 解析P386 · 目视转录
【2022 统考真题】采用直接插入而非快速排序,可能原因是( )。
Ⅰ.大部分已有序 Ⅱ.元素数量很少 Ⅲ.要求空间 Ⅳ.要求稳定
A. 仅Ⅰ、Ⅱ
B. 仅Ⅲ、Ⅳ
C. 仅Ⅰ、Ⅱ、Ⅳ
D. Ⅰ、Ⅱ、Ⅲ、Ⅳ
查看答案与解析
答案:D。
| 算法 | 适合初态 | 适合数量 | 空间 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | 大部分有序 | 较少 | O(1) | 稳定 |
| 快速 | 基本无序 | 较多 | 平均O(log₂n) | 不稳定 |
四项均可能是理由。
单项选择题 21
原书题目P383 · 解析P386 · 目视转录
【2023 统考真题】下列不稳定的算法是( )。
Ⅰ.希尔 Ⅱ.归并 Ⅲ.快速 Ⅳ.堆 Ⅴ.基数
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ、Ⅴ
C. 仅Ⅰ、Ⅲ、Ⅳ
D. 仅Ⅲ、Ⅳ、Ⅴ
查看答案与解析
答案:C。
稳定的有插入、冒泡、归并、基数;不稳定的有简单选择、快速、希尔、堆。
综合应用题
综合应用题 01
原书题目P384 · 解析P386 · 目视转录
关键字 {3,7,6,9,7,1,4,5,20},排序的最小交换次数是多少?
查看答案与解析
直接插入交换更多,采用简单选择。按原书过程:
| 步骤 | 序列 | 交换 |
|---|---|---|
| 初始 | 3,7,6,9,7,1,4,5,20 | |
| 1 | 1,7,6,9,7,3,4,5,20 | 1与3 |
| 2 | 1,3,6,9,7,7,4,5,20 | 3与7 |
| 3 | 1,3,4,9,7,7,6,5,20 | 4与6 |
| 4 | 1,3,4,5,7,7,6,9,20 | 5与9 |
| 5 | 1,3,4,5,6,7,7,9,20 | 6与7 |
最小交换5次。注意求的是交换次数,并非移动次数或比较次数。
综合应用题 02
原书题目P384 · 解析P386 · 目视转录
顺序表用数组A[]表示,元素存于下标1~m+n,前m个递增有序、后n个递增有序,设计使全表有序的算法。
- 基本思想。
- C/C++实现及关键注释。
- 时间与空间复杂度。
查看答案与解析
- 视为已完成前m个元素插入的表,从m+1开始将后n个依次插入前面的有序表。
- 实现如下。
void Insert_Sort(ElemType A[], int m, int n) {
int i, j;
for (i = m + 1; i <= m + n; i++) {
A[0] = A[i]; // 哨兵
for (j = i - 1; A[j] > A[0]; j--)
A[j + 1] = A[j];
A[j + 1] = A[0];
}
}
- 原书给出最坏比较与移动次数均为 ,时间 、空间 。也可把两段归并,时间 、空间 。
综合应用题 03
原书题目P384 · 解析P386 · 目视转录
数组中存有元素 K₁,K₂,…,Kₙ,要求把Kₙ放在排序后的正确位置。编写算法,关键字比较次数不超过n。
查看答案与解析
以末元素Kₙ为枢轴,进行一趟快速划分,先从前向后,再从后向前查找。
int Partition(ElemType K[], int n) {
int i = 1, j = n;
ElemType pivot = K[j];
while (i < j) {
while (i < j && K[i] <= pivot)
i++;
if (i < j)
K[j] = K[i];
while (i < j && K[j] >= pivot)
j--;
if (i < j)
K[i] = K[j];
}
K[i] = pivot;
return i;
}
返回枢轴最终位置。