8.5 归并排序、基数排序和计数排序·习题
复习入口
8.5 归并排序、基数排序和计数排序 · 8.5.1 归并排序 · 8.5.2 基数排序 · 8.5.3 计数排序
本节共23题:选择题20题,综合应用题3题。每题答案紧接题目折叠显示。
文字转录进度:23/23题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P375 · 解析P377 · 目视转录
以下算法中,( )一趟后不一定能选出一个元素放在最终位置。
A. 简单选择排序
B. 冒泡排序
C. 归并排序
D. 堆排序
查看答案与解析
答案:C。
插入排序不保证一趟后元素就位,归并也不保证。例如 {6,5,7,8,2,1,4,3} 一趟升序归并后为 {5,6,7,8,1,2,3,4},所有元素均未在最终位置。
单项选择题 02
原书题目P375 · 解析P377 · 目视转录
以下算法中,( )不需要关键字比较。
A. 快速排序
B. 归并排序
C. 基数排序
D. 堆排序
查看答案与解析
答案:C。
基数排序按关键字各位大小排序,不基于整个关键字之间的比较。
单项选择题 03
原书题目P375 · 解析P377 · 目视转录
下列算法中,平均空间复杂度为 的是( ),最坏空间复杂度为 的是( )。
Ⅰ.希尔 Ⅱ.堆 Ⅲ.冒泡 Ⅳ.归并 Ⅴ.快速 Ⅵ.基数
A. Ⅰ、Ⅳ、Ⅵ
B. Ⅱ、Ⅴ
C. Ⅳ、Ⅴ
D. Ⅳ
查看答案与解析
答案:D、C。
归并平均、最坏空间均 ;快速仅最坏为 ,平均 。因此按本章所比较算法,归并占辅助空间最多。
单项选择题 04
原书题目P375 · 解析P377 · 目视转录
排序过程中比较次数数量级与序列初态无关的是( )。
A. 归并排序
B. 插入排序
C. 快速排序
D. 冒泡排序
查看答案与解析
答案:A。
简单选择的比较次数与初态无关,归并的比较次数数量级也与初态无关。应从算法原理理解原因。
单项选择题 05
原书题目P375 · 解析P377 · 目视转录
二路归并排序的归并趟数数量级是( )。
A.
B.
C.
D.
查看答案与解析
答案:B。
N 个元素 k 路归并趟数 m 满足 kᵐ=N,即 m=⌈logₖN⌉。本题 k=2。
单项选择题 06
原书题目P375 · 解析P377 · 目视转录
对 27 个元素只进行三趟多路归并,选取的归并路数最少为( )。
A. 2
B. 3
C. 4
D. 5
查看答案与解析
答案:B。
kᵐ=N,代入 m=3、N=27,得 k=3。
单项选择题 07
原书题目P375 · 解析P377 · 目视转录
将两个各有 N 个元素的有序表合成一个有序表,最少比较( )次,最多比较( )次。
A. N
B. 2N−1
C. 2N
D. N−1
查看答案与解析
答案:A、B。
一个表的最小值比另一个表最大值还大时,比较次数最少,仅 N 次;两表元素交错时,如 a₁<b₁<a₂<b₂<…<aₙ<bₙ,最多 2N−1 次。可进一步思考两表长度分别 M、N 时的最少、最多次数和时间复杂度。
单项选择题 08
原书题目P375 · 解析P377 · 目视转录
归并排序序列 {1,2,6,4,5,3,8,7},共需比较( )次。
A. 12
B. 13
C. 14
D. 15
查看答案与解析
答案:C。
第一趟 {1,2}、{4,6}、{3,5}、{7,8},比较4次;第二趟 {1,2,4,6}、{3,5,7,8},比较4次;第三趟合为 {1,2,3,4,5,6,7,8},比较6次,共14次。
单项选择题 09
原书题目P375 · 解析P377 · 目视转录
一趟二路归并后关键字为 {25,50,15,35,80,85,20,40,36,70},包含5个长度2的有序表。第二趟结果为( )。
A. 15,25,35,50,80,20,85,40,70,36
B. 15,25,35,50,20,40,80,85,36,70
C. 15,25,50,35,80,85,20,36,40,70
D. 15,25,35,50,80,20,36,40,70,85
查看答案与解析
答案:B。
第二趟每4个元素归并,分为 {25,50,15,35}、{80,85,20,40}、{36,70},分别变为 {15,25,35,50}、{20,40,80,85}、{36,70}。
单项选择题 10
原书题目P375 · 解析P377 · 目视转录
将中国人按生日排序,不计年份、只考虑月日,最快的算法是( )。
A. 归并排序
B. 希尔排序
C. 快速排序
D. 基数排序
查看答案与解析
答案:D。
N 很大,但只有月、日两排序码,基数12、31均为小常数,采用基数排序可在 内完成。
单项选择题 11
原书题目P375 · 解析P378 · 目视转录
元素有数据项 k₁、k₂,要求先按 k₁ 从小到大,同 k₁ 再按 k₂ 从小到大。满足要求的方法是( )。
A. 先按 k₁ 直接插入,再按 k₂ 简单选择
B. 先按 k₂ 直接插入,再按 k₁ 简单选择
C. 先按 k₁ 简单选择,再按 k₂ 直接插入
D. 先按 k₂ 简单选择,再按 k₁ 直接插入
查看答案与解析
答案:D。
来自 LSD 思想,应先排 k₂ 再排 k₁,排除 A、C。后一次排序必须稳定,否则相同 k₁ 元素原已按 k₂ 的次序可能改变。直接插入稳定、简单选择不稳定,所以选 D。
单项选择题 12
原书题目P375 · 解析P378 · 目视转录
对 {05,46,13,55,94,17,42} 基数排序,一趟后结果为( )。
A. 05,46,13,55,94,17,42
B. 05,13,17,42,46,55,94
C. 42,13,94,05,55,46,17
D. 05,13,46,55,17,42,94
查看答案与解析
答案:C。
基数排序分 MSD、LSD,两者均稳定。A 不符合两者;B 似 MSD,但42、46相对位置改变;D也不符合。C为按个位分配收集的结果。
单项选择题 13
原书题目P376 · 解析P378 · 目视转录
n 个十进制整数基数排序,最大整数为5位,过程中临时建立的队列个数是( )。
A. n
B. 2
C. 5
D. 10
查看答案与解析
答案:D。
队列个数等于进制基数,即10。
单项选择题 14
原书题目P376 · 解析P378 · 目视转录
下列算法需要附加存储空间最大的是( )。
A. 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
查看答案与解析
答案:C。
快速平均空间 ,归并 ,其他为 。
单项选择题 15
原书题目P376 · 解析P378 · 目视转录
【2013 统考真题】两个长度为 m、n 的升序链表合并成长度 m+n 的降序链表,最坏时间复杂度为( )。
A.
B.
C.
D.
查看答案与解析
答案:D。
每次比较两表元素,取较小者头插到新表,比较后确定一个链域位置。一表结束后将另一表剩余元素逐个头插,最终降序。最坏两表元素交错,2max(m,n)≥m+n,故为 。无论最好、最坏,都需要遍历两表所有结点。
单项选择题 16
原书题目P376 · 解析P378 · 目视转录
【2013 统考真题】关键字 110,119,007,911,114,120,122 基数排序,第二趟分配、收集后是( )。
A. 007,110,119,114,911,120,122
B. 007,110,119,114,911,122,120
C. 007,110,911,114,119,120,122
D. 110,120,911,122,114,007,119
查看答案与解析
答案:C。
首趟按个位分配:0队列110→120,1队列911,2队列122,4队列114,7队列007,9队列119;收集为110,120,911,122,114,007,119。
第二趟按十位分配:0队列007,1队列110→911→114→119,2队列120→122;收集为007,110,911,114,119,120,122。
单项选择题 17
原书题目P376 · 解析P378 · 目视转录
【2015 统考真题】下列算法中,元素移动次数与关键字初态无关的是( )。
A. 直接插入排序
B. 冒泡排序
C. 基数排序
D. 快速排序
查看答案与解析
答案:C。
基数排序的元素移动次数与初态无关,其他三种有关。
单项选择题 18
原书题目P376 · 解析P378 · 目视转录
【2021 统考真题】S[]={93,946,372,9,146,151,301,485,236,327,43,892},用 LSD 基数排序升序。第一趟分配收集后,372之前、之后紧邻元素分别是( )。
A. 43,892
B. 236,301
C. 301,892
D. 485,301
查看答案与解析
答案:C。
首趟按个位稳定分配、收集,结果为 {151,301,372,892,93,43,485,946,146,236,327,9},372两侧为301、892。
单项选择题 19
原书题目P376 · 解析P379 · 目视转录
【2022 统考真题】对含 n 元素的 M 二路归并排序,二路归并的功能是( )。
A. 将两个有序表合并为一个新有序表
B. 将 M 划成两部分,元素个数大致相等
C. 将 M 划成 n 部分,每部分仅一个元素
D. 将 M 划成两部分,一部分所有值小于另一部分
查看答案与解析
答案:A。
归并是把两个或两个以上有序表合并为新有序表,二路归并即合并两个有序表。
单项选择题 20
原书题目P376 · 解析P379 · 目视转录
【2024 统考真题】3个有序序列 (3,5)、(7,9)、(6),从左到右依次选择进行二路归并,关键字总比较次数为( )。
A. 3
B. 4
C. 5
D. 6
查看答案与解析
答案:C。
先合并(3,5)与(7,9),比较3与7、5与7,共2次,余下7、9直接加入。再合并(3,5,7,9)与(6),比较3与6、5与6、7与6,共3次,余下7、9直接加入。总计5次。
综合应用题
综合应用题 01
原书题目P376 · 解析P379 · 目视转录
序列 {503,87,512,61,908,170,897,275,653,462},采用非递归二路归并升序,需几趟?给出每趟结果。
查看答案与解析
n=10,需⌈log₂10⌉=4趟。
| 趟数 | 序列 |
|---|---|
| 初始 | 503,87,512,61,908,170,897,275,653,462 |
| 1(有序段长2) | 87,503,61,512,170,908,275,897,462,653 |
| 2(段长4) | 61,87,503,512,170,275,897,908,462,653 |
| 3(段长8) | 61,87,170,275,503,512,897,908,462,653 |
| 4(段长10) | 61,87,170,275,462,503,512,653,897,908 |
综合应用题 02
原书题目P376 · 解析P379 · 目视转录
关键字 {12,2,16,30,28,10,16*,20,6,18},写出 LSD 基数排序每趟结果。
查看答案与解析
采用链式队列,保持同桶内相对顺序。
| 趟数 | 非空队列(队首→队尾) | 收集结果 |
|---|---|---|
| 个位 | 0:30→10→20;2:12→2;6:16→16*→6;8:28→18 | 30,10,20,12,2,16,16*,6,28,18 |
| 十位 | 0:2→6;1:10→12→16→16*→18;2:20→28;3:30 | 2,6,10,12,16,16*,18,20,28,30 |
共2次分配与收集。
综合应用题 03
原书题目P376 · 解析P380 · 目视转录
【2021 统考真题】已知算法如下。
void cmpCountSort(int a[], int b[], int n) {
int i, j, *count;
count = (int *)malloc(sizeof(int) * n);
// C++:count = new int[n];
for (i = 0; i < n; i++) count[i] = 0;
for (i = 0; i < n - 1; i++)
for (j = i + 1; j < n; j++)
if (a[i] < a[j]) count[j]++;
else count[i]++;
for (i = 0; i < n; i++) b[count[i]] = a[i];
free(count);
// 原书 C++ 对应语句:delete count;
}
- a[]={25,−10,25,10,11,19}、b[6],调用后 b 内容为何?
- a 含 n 个元素,元素间比较次数多少?
- 算法稳定吗?若稳定说明原因,否则改为稳定算法。
查看答案与解析
算法基于计数排序思想,count 记录元素应放的秩。例如 count[1]=3 表示有3个元素较小,a[1]应位于b[3]。
- b={−10,10,11,19,25,25}。
- 每个元素与其后所有元素比较一次,即所有元素对均比较,共 (n−1)+(n−2)+…+1=n(n−1)/2 次。
- 不稳定。修改判断为:
if (a[i] <= a[j]) count[j]++;
else count[i]++;
原判断在两值相等时增加前面元素的count,使原先靠前的元素排序后靠后。加等号后可保持原先相对顺序。
转录核对:若采用 C++ 的
new int[n]分配数组,释放应使用delete[] count,原书注释中的delete count不匹配数组分配。