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 · 目视转录

下列算法中,平均空间复杂度为 O(n)O(n) 的是( ),最坏空间复杂度为 O(n)O(n) 的是( )。

Ⅰ.希尔 Ⅱ.堆 Ⅲ.冒泡 Ⅳ.归并 Ⅴ.快速 Ⅵ.基数

A. Ⅰ、Ⅳ、Ⅵ

B. Ⅱ、Ⅴ

C. Ⅳ、Ⅴ

D. Ⅳ

查看答案与解析

答案:D、C。

归并平均、最坏空间均 O(n)O(n);快速仅最坏为 O(n)O(n),平均 O(log⁡2n)O(\log_2n)。因此按本章所比较算法,归并占辅助空间最多。

单项选择题 04

原书题目P375 · 解析P377 · 目视转录

排序过程中比较次数数量级与序列初态无关的是( )。

A. 归并排序

B. 插入排序

C. 快速排序

D. 冒泡排序

查看答案与解析

答案:A。

简单选择的比较次数与初态无关,归并的比较次数数量级也与初态无关。应从算法原理理解原因。

单项选择题 05

原书题目P375 · 解析P377 · 目视转录

二路归并排序的归并趟数数量级是( )。

A. O(n)O(n)

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

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

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

查看答案与解析

答案: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均为小常数,采用基数排序可在 O(N)O(N) 内完成。

单项选择题 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。

快速平均空间 O(log⁡2n)O(\log_2n),归并 O(n)O(n),其他为 O(1)O(1)。

单项选择题 15

原书题目P376 · 解析P378 · 目视转录

【2013 统考真题】两个长度为 m、n 的升序链表合并成长度 m+n 的降序链表,最坏时间复杂度为( )。

A. O(n)O(n)

B. O(mn)O(mn)

C. O(min⁡(m,n))O(\min(m,n))

D. O(max⁡(m,n))O(\max(m,n))

查看答案与解析

答案:D。

每次比较两表元素,取较小者头插到新表,比较后确定一个链域位置。一表结束后将另一表剩余元素逐个头插,最终降序。最坏两表元素交错,2max(m,n)≥m+n,故为 O(max⁡(m,n))O(\max(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→1830,10,20,12,2,16,16*,6,28,18
十位0:2→6;1:10→12→16→16*→18;2:20→28;3:302,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;
}
  1. a[]={25,−10,25,10,11,19}、b[6],调用后 b 内容为何?
  2. a 含 n 个元素,元素间比较次数多少?
  3. 算法稳定吗?若稳定说明原因,否则改为稳定算法。
查看答案与解析

算法基于计数排序思想,count 记录元素应放的秩。例如 count[1]=3 表示有3个元素较小,a[1]应位于b[3]。

  1. b={−10,10,11,19,25,25}。
  2. 每个元素与其后所有元素比较一次,即所有元素对均比较,共 (n−1)+(n−2)+…+1=n(n−1)/2 次。
  3. 不稳定。修改判断为:
if (a[i] <= a[j]) count[j]++;
else count[i]++;

原判断在两值相等时增加前面元素的count,使原先靠前的元素排序后靠后。加等号后可保持原先相对顺序。

转录核对:若采用 C++ 的 new int[n] 分配数组,释放应使用 delete[] count,原书注释中的 delete count 不匹配数组分配。