Day 3

作者： 作者的头像   huolong , 时间：2026-08-24 22:20:19 , 所有人可见, 阅读  82

CSP-J 第一轮（初赛）通关集训 · 第三天

Day 3 上午：数组、高精度、前缀和差分、字符串与结构体（3小时）

第一部分：核心知识精讲与考点速记

1. 数组与内存连续性

  • 一维数组：
    • 数组在内存中占据一段连续的物理存储单元。
    • 下标寻址公式（元素类型占 $S$ 字节）：$\text{Address}(a[i]) = \text{Base_Address} + i \times S$（因此支持 $O(1)$ 随机访问）。
  • 二维数组：
    • C++ 中二维数组 $a[M][N]$ 按行优先（Row-major order）顺序连续存储： $$\text{Address}(a[i][j]) = \text{Base_Address} + (i \times N + j) \times S$$
  • 空间换算实战：
    • 声明 int a[1000][1000]; 占用的内存空间为： $$\frac{1000 \times 1000 \times 4\text{ B}}{1024 \times 1024} \approx 3.81\text{ MB}$$

2. 高精度运算原理与复杂度

  • 核心思想：利用整型数组或 string 逆序存储超大整数的每一位（低位存低下标，方便进位）。
  • 高精度四则运算复杂度对比（常考）：
    • 高精度加法 / 减法：时间复杂度为 $O(N)$（$N$ 为较长数的位数），逐位相加并处理进位（carry = sum / 10）。
    • 高精度乘法（模拟竖式）：设两数位数分别为 $n$ 和 $m$，其时间复杂度为 $O(n \times m)$（与两个乘数的位数乘积相关，绝非只与较长者相关）。
    • 高精度除以低精度：从高位向低位模拟除法，时间复杂度为 $O(N)$。

3. 前缀和与差分思想（完善程序题高频考点）

  • 一维前缀和：
    • 预处理公式：$S[i] = S[i-1] + a[i]$（$O(n)$ 预处理，下标通常从 1 开始，$S[0] = 0$）。
    • 区间查询公式：区间 $[l, r]$ 的元素之和为 $S[r] - S[l-1]$（$O(1)$ 极速查询）。
  • 一维差分数组：
    • 定义公式：$D[i] = a[i] - a[i-1]$（$a[i]$ 恰好为 $D[i]$ 的前缀和）。
    • 区间修改操作：将区间 $[l, r]$ 内所有数同时加上 $v$，只需修改两个端点： $$D[l] \leftarrow D[l] + v, \quad D[r+1] \leftarrow D[r+1] - v$$
    • 最后对 $D$ 数组求前缀和，即可在 $O(n)$ 时间内复原出修改后的整个数组。

4. 字符串处理与子串计算公式

  • 字符数组 (char[]) vs std::string：
    • char str[]：以空字符 '\0' 作为结束标志，使用 <cstring> 中的 strlen(str) 求实际有效长度（不计入 '\0'）。
    • std::string：C++ 标准库动态字符串类，支持 + 拼接字符或字符串，.length() 与 .size() 完全等价。
  • 字符串的子串数量计算公式（初赛单选必考）：
    • 对于长度为 $n$ 且字符互不相同的字符串： $$\text{子串总数（含空串）} = \frac{n(n+1)}{2} + 1$$ $$\text{非空子串数} = \frac{n(n+1)}{2}$$
    • 例："copyright" 长度为 9，字符互不相同，子串总数 $= \frac{9 \times 10}{2} + 1 = 46$ 个。
  • 含重复字符的子串手工去重套路：
    • 若字符串包含重复字符（如 "abcab"），需按子串长度 $1, 2, \dots, n$ 分类枚举并手动剔除重复项。

5. 结构体与自定义排序

  • 结构体成员访问语法：
    • 结构体普通变量访问成员用点号 .（如 student.score = 95;）。
    • 结构体指针变量访问成员用箭头 ->（如 p->score = 95; 等价于 (*p).score = 95;）。
  • std::sort 与自定义 cmp 规则： cpp struct Node { int id, score; }; // 规则：按分数从高到低排序；分数相同时，按 id 从小到大排序 bool cmp(Node a, Node b) { if (a.score != b.score) return a.score > b.score; return a.id < b.id; } // 排序调用：sort(a + 1, a + n + 1, cmp);

第二部分：上午精选真题实战（1~18题）

  1. 关于字符串的定义与特性，下列说法中正确的是（ ）。 A. 字符串是一种特殊的线性表 B. 字符串的长度必须严格大于零 C. 字符串不能采用一维数组的形式存储 D. 仅由空格字符构成的字符串被称为空串

  2. 字符串 "copyright" 的所有不同子串（包含空串）的总个数是（ ）。 A. 72 B. 45 C. 46 D. 36

  3. 字符串 "AAABBBCCC" 的所有互不相同的非空子串的总个数是（ ）。 A. 3 B. 12 C. 36 D. 45

  4. 字符串 "Olympic" 的所有非空子串的数目是（ ）。 A. 28 B. 29 C. 16 D. 17

  5. 字符串 "abcab" 中内容互不相同的子串（含空串）共有（ ）个。 A. 12 B. 13 C. 14 D. 15

  6. 设有结构体定义如下： cpp struct Data { double value; } data; 若要将 data 的成员 value 赋值为 3.14，正确的语句是（ ）。 A. data.value = 3.14; B. value.data = 3.14; C. data->value = 3.14; D. value->data = 3.14;

  7. 下列关于高精度运算的说法中，错误的是（ ）。 A. 高精度运算主要用于处理超出标准整型表示范围的大整数 B. 高精度除以低精度整数的运算过程通常从高位向低位模拟 C. 高精度乘法的时间复杂度只与两乘数中较长者的位数有关 D. 高精度加法的核心逻辑在于处理逐位相加后的进位

  8. 下列关于 C++ 中 std::string 类的描述中，正确的是（ ）。 A. string 对象的长度在定义后不能发生动态改变 B. 可以使用 + 运算符直接连接 string 对象与 char 字符 C. 成员函数 .length() 和 .size() 返回的数值可能不同 D. 字符串末尾的 '\0' 字符会被计入 .length() 的长度中

  9. 设有指针定义与操作如下： cpp int x = 101, y = 201; int *p = &x, *q = &y; p = q; 执行语句 p = q; 后，产生的实际效果是（ ）。 A. 将变量 $x$ 的值赋为 201 B. 将变量 $y$ 的值赋为 101 C. 指针 $q$ 指向了变量 $x$ D. 指针 $p$ 指向了变量 $y$

  10. 下列关于链表和数组特性的对比描述中，错误的是（ ）。 A. 数组在声明后物理大小通常固定，而链表可以动态扩容 B. 数组支持根据下标 $O(1)$ 随机访问，链表只能顺序遍历访问 C. 链表节点除了存储数据本身外，还需要额外存储后继指针信息 D. 数组中的元素无法直接进行排序，而链表可以

  11. 已知一维数组 $a[1\dots 10]$ 的前缀和数组为 $S[1\dots 10]$，若要求区间 $[3, 7]$ 内所有元素的和，等价的计算表达式是（ ）。 A. $S[7] - S[3]$ B. $S[7] - S[2]$ C. $S[6] - S[2]$ D. $S[7] - S[4]$

  12. 对长度为 $N$ 的差分数组 $D[1\dots N]$ 执行操作：将区间 $[l, r]$ 内所有数同时加上整数 $k$，正确的代码实现是（ ）。 A. D[l] += k; D[r] -= k; B. D[l] += k; D[r + 1] -= k; C. D[l - 1] += k; D[r] -= k; D. D[l + 1] += k; D[r] -= k;

  13. 在 64 位编译环境下，执行 sizeof("Hello") 表达式的运算结果是（ ）。 A. 5 B. 6 C. 8 D. 4

  14. 设有二维数组 int a[4][5];，若首元素 a[0][0] 的内存地址为 1000，且每个 int 占 4 字节，则元素 a[2][3] 的内存起始地址是（ ）。 A. 1048 B. 1052 C. 1056 D. 1060

  15. 阅读下列结构体排序代码片段： cpp struct Student { string name; int score; } a[100]; bool cmp(Student x, Student y) { return x.score < y.score; } 执行 sort(a, a + n, cmp); 后，数组元素将按照（ ）。 A. 分数从高到低降序排列 B. 分数从低到高升序排列 C. 姓名字典序升序排列 D. 姓名字典序降序排列

  16. 已知字符串 $S = \text{"ababa"}$，该字符串中共有（ ）个互不相同的非空子串。 A. 7 B. 8 C. 9 D. 15

  17. 下列关于字符数组与字符串常量的描述中，正确的是（ ）。 A. 字符数组 char s[5] = "hello"; 可以正常通过编译且不会产生越界 B. strlen("abc\0def") 的计算结果是 3 C. strcmp("abc", "abd") 的返回值大于 0 D. 两个 char[] 数组可以直接使用 == 运算符比较字符串内容是否相等

  18. 计算两个 1000 位的大整数相乘，采用传统模拟竖式乘法算法，总共需要进行的单精度一位数乘法次数约为（ ）。 A. 1000 B. 2000 C. $10^6$ D. $2 \times 10^6$

第三部分：上午真题解析与答案速查

  1. 【答案】A
    【解析】 字符串是以字符为数据元素的特殊线性表；空串的长度为 0；字符串可以用一维字符数组存储；仅含空格的串长度为其空格个数，不是空串。
  2. 【答案】C
    【解析】 "copyright" 长度 $n = 9$，9 个字符互不相同。其子串总数（含空串）为 $\frac{n(n+1)}{2} + 1 = \frac{9 \times 10}{2} + 1 = 46$。
  3. 【答案】C
    【解析】 字符串长 9，全部非空子串如果不去重共 $\frac{9 \times 10}{2} = 45$ 个。分类去重统计：
  4. 长度 1："A", "B", "C"（3个）；
  5. 长度 2："AA", "AB", "BB", "BC", "CC"（5个）；
  6. 长度 3："AAA", "AAB", "ABB", "BBB", "BBC", "BCC", "CCC"（7个）；
  7. 长度 4：6个；长度 5：5个；长度 6：4个；长度 7：3个；长度 8：2个；长度 9：1个。
    总数 $= 3 + 5 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36$ 个。
  8. 【答案】A
    【解析】 "Olympic" 长度 $n = 7$，字符无重复。非空子串数为 $\frac{7 \times 8}{2} = 28$ 个。
  9. 【答案】B
    【解析】 长度 $n=5$。按长度枚举互不相同的子串：
  10. 长度 0：空串（1个）；
  11. 长度 1："a", "b", "c"（3个）；
  12. 长度 2："ab", "bc", "ca"（3个）；
  13. 长度 3："abc", "bca", "cab"（3个）；
  14. 长度 4："abca", "bcab"（2个）；
  15. 长度 5："abcab"（1个）。
    总计 $= 1 + 3 + 3 + 3 + 2 + 1 = 13$ 个。
  16. 【答案】A
    【解析】 data 是普通结构体变量，访问其成员需使用点号运算符 .，故写为 data.value = 3.14;。
  17. 【答案】C
    【解析】 设两个大整数位数分别为 $n$ 和 $m$，模拟竖式乘法需要双重循环将每一位两两相乘，时间复杂度为 $O(n \times m)$，与两数的位数乘积直接相关。
  18. 【答案】B
    【解析】 C++ std::string 重载了 + 运算符，支持拼接；string 大小可动态伸缩；.length() 与 .size() 语义与返回值完全相同；length() 统计的是实际字符数，不计入底层的 '\0'。
  19. 【答案】D
    【解析】 指针赋值 p = q; 是将指针 $q$ 存储的内存地址（即变量 $y$ 的地址 &y）复制给指针 $p$，因此执行后指针 $p$ 也指向了变量 $y$。
  20. 【答案】D
    【解析】 数组内部元素可以通过 std::sort 或各类排序算法进行排序，D 选项说法显然错误。
  21. 【答案】B
    【解析】 前缀和区间和公式：$\sum_{i=l}^r a[i] = S[r] - S[l-1]$。代入 $l=3, r=7$，结果为 $S[7] - S[2]$。
  22. 【答案】B
    【解析】 一维差分标准模板：左端点 $l$ 处加 $k$（D[l] += k），右端点之后一个位置 $r+1$ 处减 $k$（D[r+1] -= k）。
  23. 【答案】B
    【解析】 字符串字面量 "Hello" 末尾会自动包含一个看不见的隐藏空字符 '\0'，因此其在内存中实际占用 $5 + 1 = 6$ 个字节。
  24. 【答案】B
    【解析】 二维数组行优先存储，a[2][3] 前面共有 2 整行（每行 5 个元素）以及第 2 行前面的 3 个元素，共 $2 \times 5 + 3 = 13$ 个元素。偏移字节数 $= 13 \times 4 = 52$ 字节，地址为 $1000 + 52 = 1052$。
  25. 【答案】B
    【解析】 比较函数 cmp(x, y) 返回 x.score < y.score，表示分数较小的排在前面，因此排序后为升序排列。
  26. 【答案】B
    【解析】 长度为 5 的字符串 "ababa"：
    • 长度 1："a", "b"（2个）；
    • 长度 2："ab", "ba"（2个）；
    • 长度 3："aba", "bab"（2个）；
    • 长度 4："abab", "baba"（2个）；
    • 长度 5："ababa"（1个？注意 "ababa" 包含的非空子串）。
      具体非空子串集合：{"a", "b", "ab", "ba", "aba", "bab", "abab", "baba", "ababa"} 共 9 个？去重枚举：长1(2), 长2(2), 长3(2), 长4(2), 长5(1)，总计 $2+2+2+2+1 = 9$ 个（选项选 C）。
  27. 【答案】B
    【解析】 strlen 读取到第一个 '\0' 处立即停止并返回前面的字符数，故 "abc\0def" 的长度为 3；A 选项 "hello" 加 '\0' 占 6 字节，放进长度 5 的数组会导致越界。
  28. 【答案】C
    【解析】 模拟高精度乘法，1000 位乘 1000 位需要执行 $1000 \times 1000 = 10^6$ 次个位数相乘。

---

Day 3 下午：7 大排序算法全景对比、稳定性与逆序对（3小时）

第一部分：核心知识精讲与考点速记

1. 7 大经典排序算法终极全景对比表（初赛单选必考）

排序算法 平均时间复杂度 最好时间复杂度 最坏时间复杂度 额外空间复杂度 稳定性 核心算法思想
冒泡排序 $O(n^2)$ $O(n)$（加优化标志） $O(n^2)$ $O(1)$ 稳定 相邻元素两两比较交换
插入排序 $O(n^2)$ $O(n)$（已正序） $O(n^2)$ $O(1)$ 稳定 将未排序元素插入已排序序列
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定 每次选极值放到未排序序列首部
快速排序 $O(n \log n)$ $O(n \log n)$ $O(n^2)$（退化为最值划分） $O(\log n)$ 不稳定 分治基准划分（Pivot）
归并排序 $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ 稳定 分治递归拆半，双指针有序合并
计数排序 $O(n + k)$ $O(n + k)$ $O(n + k)$ $O(k)$ 稳定 统计值域频数（非比较排序）
基数排序 $O(d(n + r))$ $O(d(n + r))$ $O(d(n + r))$ $O(n + r)$ 稳定 按数位（个/十/百位）分配收集

2. 排序算法四大黄金定律与记忆口诀

  • 稳定性定义：若待排序序列中存在两个相等的元素 $A$ 和 $B$，在排序前 $A$ 在 $B$ 前面；若排序后 $A$ 依然恒在 $B$ 前面，则称该算法是稳定的。
  • 不稳定排序速记口诀： $$\text{“快（快排）选（选择）堆（堆排）希（希尔）不稳定！”}$$
  • 比较排序的理论下界：
    • 任何基于元素关键字两两比较的排序算法，在最坏情况下的时间复杂度下界必定是 $\Omega(n \log n)$。
    • 突破 $O(n \log n)$ 下界的都是非比较排序（计数排序、基数排序、桶排序）。
  • 快速排序退化与优化：
    • 当待排序列原本就已经有序（正序或逆序）且每次都选取端点作为基准时，快排会严重退化为 $O(n^2)$。
    • 归并排序在任何情况下（最好/最坏/平均）时间复杂度恒为稳定 $O(n \log n)$，但代价是需要 $O(n)$ 的辅助数组空间。

3. 逆序对与排序交换次数的手推关系

  • 逆序对定义：在序列 $A[1\dots n]$ 中，若下标 $i < j$ 且数值 $A[i] > A[j]$，则称 $(A[i], A[j])$ 构成一个逆序对。
  • 冒泡排序与逆序对的等价定理：
    • 冒泡排序每次只交换相邻的两个逆序元素。
    • 每一次有效的相邻元素交换，必然且只能减少序列中恰好 1 个逆序对。
    • 结论：冒泡排序将序列排成完全升序所需的最小交换次数，严格等于该序列中包含的逆序对总数！
  • 归并两个有序数组的最坏比较次数：
    • 将两个长度分别为 $n$ 和 $m$ 的有序数组合并为一个有序数组，在最坏情况下（两数组元素交替出现）需要比较的次数为： $$\text{最坏比较次数} = n + m - 1$$
    • 若两个数组长度均为 $n$，则最坏比较 $2n - 1$ 次。

第二部分：下午精选真题实战（1~18题）

  1. 序列 ${1, 7, 2, 3, 5, 4}$ 中包含的逆序对总数是（ ）。 A. 4 B. 5 C. 6 D. 7

  2. 将两个长度均为 $n$ 的递增有序数组合并成一个长度为 $2n$ 的递增有序数组，在最坏情况下至少需要进行的关键字比较次数是（ ）。 A. $n^2$ B. $n \log n$ C. $2n$ D. $2n - 1$

  3. 下列排序算法中，完全不依赖于元素关键字之间大小比较的是（ ）。 A. 基数排序 B. 冒泡排序 C. 堆排序 D. 插入排序

  4. 在包含 $N$ 个互不相同的元素的无序数组中，同时找出最大值和最小值，在最优策略下至少需要进行的比较次数是（ ）。 A. $\lceil 3N/2 \rceil - 2$ B. $\lfloor 3N/2 \rfloor - 2$ C. $2N - 2$ D. $2N - 4$

  5. 对包含 $n$ 个元素的序列进行冒泡排序，在最好情况下（即序列本身已经完全有序）需要进行的比较次数是（ ）。 A. $n^2$ B. $n - 2$ C. $n - 1$ D. $n$

  6. 下列排序算法中，平均时间复杂度为 $O(n \log n)$ 的是（ ）。 A. 快速排序 B. 简单插入排序 C. 冒泡排序 D. 计数排序

  7. 将完全逆序序列 ${5, 4, 3, 2, 1}$ 采用冒泡排序算法调整为升序序列，总共需要执行（ ）次相邻元素交换。 A. 0 B. 5 C. 10 D. 15

  8. 体育课上排队，同学们逐个将未排好的同学引导并插入到已排好队列的合适位置，这种排队方法与下列哪种排序算法的思想最为类似？（ ） A. 快速排序 B. 插入排序 C. 冒泡排序 D. 归并排序

  9. 基于两两关键字比较的排序算法，在最坏情况下的时间复杂度下界是（ ）。 A. $O(n)$ B. $O(n \log n)$ C. $O(\log n)$ D. $O(n^2)$

  10. 快速排序算法在最坏情况下的渐进时间复杂度是（ ）。 A. $O(\log n)$ B. $O(n)$ C. $O(n \log n)$ D. $O(n^2)$

  11. 下列排序算法中，属于不稳定排序算法的是（ ）。 A. 冒泡排序 B. 插入排序 C. 归并排序 D. 快速排序

  12. 要将无序数组 ${8, 23, 4, 16, 77, -5, 53, 100}$ 从大到小排序，通过任意两元素两两交换的方式，最少需要交换（ ）次。 A. 4 B. 5 C. 6 D. 7

  13. 在一个包含 $n$ 个元素的无序序列中寻找最大值，最少需要进行的比较次数是（ ）。 A. $n$ B. $n - 1$ C. $n + 1$ D. $\lceil n / 2 \rceil$

  14. 下列关于各类排序算法稳定性的描述中，错误的是（ ）。 A. 冒泡排序是稳定排序算法 B. 简单选择排序是稳定排序算法 C. 插入排序是稳定排序算法 D. 归并排序是稳定排序算法

  15. 使用冒泡排序算法将数组 ${6, 1, 5, 2, 4}$ 调整为升序序列，总共需要进行的相邻元素交换次数是（ ）。 A. 5 B. 6 C. 7 D. 8

  16. 对一组包含 1000 个数据的序列进行归并排序，其在最坏情况下的时间复杂度为（ ）。 A. $O(n)$ B. $O(n \log n)$ C. $O(n^2)$ D. $O(\log n)$

  17. 下列关于计数排序的说法中，正确的是（ ）。 A. 计数排序适用于数据值域极大但数据量极小的场景 B. 计数排序需要对元素两两进行大小比较 C. 计数排序是一种稳定的排序算法 D. 计数排序的空间复杂度与输入元素的个数无关

  18. 归并排序在合并两个长度为 $N$ 的子序列时，必须借助一个额外辅助数组，这决定了其空间复杂度为（ ）。 A. $O(1)$ B. $O(\log N)$ C. $O(N)$ D. $O(N \log N)$

第三部分：下午真题解析与答案速查

  1. 【答案】B
    【解析】 手动枚举序列 ${1, 7, 2, 3, 5, 4}$ 中的逆序对：
  2. $7$ 后面比它小的有：$2, 3, 5, 4$（共 4 个：$(7,2), (7,3), (7,5), (7,4)$）；
  3. $5$ 后面比它小的有：$4$（共 1 个：$(5,4)$）；
    其余数字后均无逆序，逆序对总数 $= 4 + 1 = 5$ 个。
  4. 【答案】D
    【解析】 双指针合并两有序数组，每次比较选出较小者放入新数组。最坏情况下两数组元素大小交替排列，直到最后一个元素无需比较直接放入，比较次数为 $n + n - 1 = 2n - 1$。
  5. 【答案】A
    【解析】 基数排序属于分配收集型非比较排序，完全无需对关键字进行两两大小比较；冒泡、堆排、插入均属于比较排序。
  6. 【答案】A
    【解析】 成对分组比较法：将元素两两配对比较 $\lfloor N/2 \rfloor$ 次分出较大组和较小组；在较大组中找最大值比 $\lceil N/2 \rceil - 1$ 次，在较小组中找最小值比 $\lceil N/2 \rceil - 1$ 次。总比较次数为 $\lceil 3N/2 \rceil - 2$ 次。
  7. 【答案】C
    【解析】 带有提早退出标志的冒泡排序，在第一趟扫描中比较相邻元素 $n - 1$ 次，发现未发生任何交换即可判定已有序并直接退出。
  8. 【答案】A
    【解析】 快速排序的平均时间复杂度为 $O(n \log n)$；插入和冒泡平均为 $O(n^2)$；计数排序为线性时间 $O(n+k)$。
  9. 【答案】C
    【解析】 完全倒序序列包含的逆序对数为 $\frac{n(n-1)}{2} = \frac{5 \times 4}{2} = 10$。冒泡排序每次交换消除 1 个逆序对，因此必须交换 10 次。
  10. 【答案】B
    【解析】 逐个将待排元素插入到前面已经有序的子序列中，这是标准插入排序的核心定义。
  11. 【答案】B
    【解析】 根据决策树模型，包含 $n$ 个元素的排列有 $n!$ 种可能，基于比较的排序决策树高度至少为 $\log_2(n!) = \Omega(n \log n)$。
  12. 【答案】D
    【解析】 快速排序在最坏情况（如每次划分选取的基准都是当前区间的最大或最小值）下，问题规模每次仅减 1，递归树退化为单链，时间复杂度退化为 $O(n^2)$。
  13. 【答案】D
    【解析】 快速排序在跨越分区交换元素时可能会改变相同大小元素的相对顺序，属于不稳定排序；口诀“快选堆希不稳定”。
  14. 【答案】B
    【解析】 置换环分解法：目标降序为 ${100, 77, 53, 23, 16, 8, 4, -5}$。将原位置与目标位置连边可分解为独立置换环。总元素数减去置换环个数：$8 - 3 = 5$ 次交换。
  15. 【答案】B
    【解析】 寻找最大值通过打擂台法，首个元素作为初始擂主，其余 $n-1$ 个元素依次与擂主比较 1 次，共需 $n-1$ 次比较。
  16. 【答案】B
    【解析】 简单选择排序是不稳定的（例如序列 ${2_a, 2_b, 1}$，第一轮选择最小值 1 与 $2_a$ 交换后变为 ${1, 2_b, 2_a}$，$2_a$ 跑到了 $2_b$ 后面）。
  17. 【答案】B
    【解析】 统计数组 ${6, 1, 5, 2, 4}$ 中的逆序对：$(6,1), (6,5), (6,2), (6,4), (5,2), (5,4)$ 共 6 个，故冒泡排序相邻交换次数为 6 次。
  18. 【答案】B
    【解析】 归并排序无论最好、最坏还是平均情况下，划分与合并过程完全固定，时间复杂度恒为 $O(n \log n)$。
  19. 【答案】C
    【解析】 计数排序从后向前将元素回填至目标数组，能保证相等元素的相对顺序不变，属于稳定排序；其空间复杂度取决于数值范围 $O(k)$。
  20. 【答案】C
    【解析】 归并排序在合并阶段需要开辟一个与待合并序列总长度相等的临时辅助数组用于暂存有序结果，因此空间复杂度为 $O(N)$。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com