GESP 客观题评测系统

2020 CCF CSP-J 第一轮（入门级 C++）

CSPJ-2020-R1

试卷解析总览，可直接查看每题答案与解析。

一、单项选择题

第 1 题（单选题，2 分）

在内存储器中每个存储单元都被赋予一个唯一的序号，称为（）。

地址

序号

下标

编号

正确答案A

解析详情

【答案】A

【考点】内存地址

【解析】内存按存储单元组织，每个单元的唯一序号用于定位读写位置，这个序号称为地址。

【易错点】不要把日常所说的“编号”与计算机体系中的专用术语“地址”混淆。

第 2 题（单选题，2 分）

编译器的主要功能是（）。

将源程序翻译成机器指令代码

将源程序重新组合

将低级语言翻译成高级语言

将一种高级语言翻译成另一种高级语言

正确答案A

解析详情

【答案】A

【考点】编译器功能

【解析】编译器把高级语言编写的源程序翻译为计算机可执行或可进一步链接的目标代码，即机器指令代码。

【易错点】编译不是重新排列源程序，也不是把低级语言翻译为高级语言。

第 3 题（单选题，2 分）

设 $x=\text{true}$ ， $y=\text{true}$ ， $z=\text{false}$ ，以下逻辑运算表达式值为真的是（）。

(y \lor z) \land x \land z

x \land (z \lor y) \land z

(x \land y) \land z

(x \land y) \lor (z \lor x)

正确答案D

解析详情

【答案】D

【考点】布尔逻辑运算

【解析】代入 x=true、y=true、z=false，D 中 x∧y=true，z∨x=true，两者再做或运算仍为 true。其余三个表达式都含有必须成立的“∧z”，因此为 false。

【易错点】看到“或”不能只算局部，需按括号先求各子表达式的真假。

第 4 题（单选题，2 分）

现有一张分辨率为 $2048 \times 1024$ 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？( )。

16MB

4MB

8MB

32MB

正确答案C

解析详情

【答案】C

【考点】图像存储容量

【解析】所需位数为 2048×1024×32 bit，除以 8 得 8,388,608 Byte，即 8 MB（按 1 MB=1024² Byte 计算）。

【易错点】 32 位表示每像素 32 bit，换算为字节时还要除以 8。

第 5 题（单选题，2 分）

冒泡排序算法的伪代码如下:

输入：数组 L，n ≥ 1。输出：按非递减顺序排序的 L。

算法 BubbleSort:

FLAG ← n //标记被交换的最后元素位置
while FLAG > 1 do
k ← FLAG -1
FLAG ← 1
for j = 1 to k do
if L(j) > L(j+1) then do
L(j) ↔ L(j+1)
FLAG ← j

对 n 个数用以上冒泡排序算法进行排序，最少需要比较多少次？( )。

n^{2}

n-2

n-1

正确答案C

解析详情

【答案】C

【考点】冒泡排序比较次数

【解析】最好情况下数组已经有序，第一趟需要比较相邻元素 n-1 次，且没有发生交换，FLAG 保持为 1，外层循环随即结束。

【易错点】即使数组原本有序，也必须完成第一趟比较后才能确认无需继续排序。

第 6 题（单选题，2 分）

设 A 是 n 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])

if n=1 then return A[1]
else temp ← XYZ (A[1..n-1])
if temp < A[n]
then return temp
else return A[n]

请问算法 XYZ 的输出是什么？（）。

A 数组的平均

A 数组的最小值

A 数组的中值

A 数组的最大值

正确答案B

解析详情

【答案】B

【考点】递归算法与最值

【解析】递归先求 A[1..n-1] 的最小值 temp，再返回 temp 与 A[n] 中较小者。由递归归纳可知，最终返回整个数组的最小值。

【易错点】条件 temp<A[n] 时返回的是 temp，因此求的是最小值而非最大值。

第 7 题（单选题，2 分）

链表不具有的特点是（）。

可随机访问任一元素

不必事先估计存储空间

插入删除不需要移动元素

所需空间与线性表长度成正比

正确答案A

解析详情

【答案】A

【考点】链表特性

【解析】链表结点通过指针相连，访问第 k 个元素通常要从表头依次遍历，不能像数组那样按下标随机访问。链表插入、删除时一般无需整体移动元素。

【易错点】链表的结点可分散存储，不等于能够按地址直接随机访问第 k 个结点。

第 8 题（单选题，2 分）

有 10 个顶点的无向图至少应该有（）条边才能确保是一个连通图。

正确答案A

解析详情

【答案】A

【考点】无向连通图

【解析】 n 个顶点的连通图至少有 n-1 条边，此时图是一棵树。代入 n=10，最少需要 10-1=9 条边。

【易错点】这里求连通图的最少边数，不是完全图的边数 n(n-1)/2。

第 9 题（单选题，2 分）

二进制数 1011 转换成十进制数是（）。

正确答案A

解析详情

【答案】A

【考点】二进制转换

【解析】 (1011)₂=1×2³+0×2²+1×2¹+1×2⁰=8+2+1=11。

【易错点】二进制各位权值从右到左依次是 2⁰、2¹、2²、2³。

第 10 题（单选题，2 分）

五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（）种不同排列方法？

正确答案A

解析详情

【答案】A

【考点】相邻排列

【解析】把双胞胎看成一个整体，与另外 3 人共 4 个对象，可排列 4! 种；双胞胎内部还有 2 种次序，所以共有 4!×2=48 种。

【易错点】合并双胞胎计算排列后，不要漏掉二人内部交换的 2 种顺序。

第 11 题（单选题，2 分）

下图中所使用的数据结构是（）。

栈

队列

二叉树

哈希表

正确答案A

解析详情

【答案】A

【考点】栈的结构特征

【解析】图示结构的数据从同一端进入和离开，遵循后进先出（LIFO），因此是栈；具体进出方向需结合题图确认。

【易错点】队列是两端操作、先进先出，不要只凭容器外形判断。

第 12 题（单选题，2 分）

独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（）。

正确答案D

解析详情

【答案】D

【考点】完全二叉树高度

【解析】高度为 h 的完全二叉树最多有 2^h-1 个结点。2^5-1=31<61≤63=2^6-1，所以 61 个结点的完全二叉树高度为 6。

【易错点】题目规定独根树高度为 1，因此高度按层数计算。

第 13 题（单选题，2 分）

干支纪年法是中国传统的纪年方法，由 10 个天干和 12 个地支组合成 60 个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。

天干=（公历年份）除以10所得余数

地支=（公历年份）除以12所得余数

天干 | 甲 | 乙 | 丙 | 丁 | 戊 | 己 | 庚 | 辛 | 壬 | 癸 |  | 
 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 |  | 
地支 | 子 | 丑 | 寅 | 卯 | 辰 | 巳 | 午 | 未 | 申 | 酉 | 戌 | 亥
 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3

例如，今年是2020年，2020除以10余数为0，查表为“庚”；2020除以12，余数为4，查表为“子”，所以今年是庚子年。

请问 1949 年的天干地支是（）

己酉

己亥

己丑

己卯

正确答案C

解析详情

【答案】C

【考点】取模与周期映射

【解析】 1949÷10 余 9，查天干表得“己”；1949÷12 余 5，查地支表得“丑”。组合为己丑。

【易错点】天干和地支分别按模 10、模 12 查表，不能直接按 60 年周期下标混算。

第 14 题（单选题，2 分）

10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（）种不同的分配方案。

504

正确答案A

解析详情

【答案】A

【考点】隔板法

【解析】设 7 个班所得名额为正整数 x₁,…,x₇，满足和为 10。用隔板法在 9 个间隙中选 6 个，方案数为 C(9,6)=84。

【易错点】每班至少 1 个名额，对应的是正整数解而不是非负整数解。

第 15 题（单选题，2 分）

有五副不同颜色的手套（共10只手套，每副手套左右手各1只），一次性从中取6只手套，请问恰好能配成两副手套的不同取法有（）种。

120

180

150

正确答案A

解析详情

【答案】A

【考点】组合计数

【解析】先选恰好配成的 2 副手套，有 C(5,2)=10 种；其余 2 只要来自剩下 3 种颜色中的不同两种，有 C(3,2)×2²=12 种。总数为 10×12=120。

【易错点】剩余两只若取自同一颜色会组成第三副，不符合“恰好两副”。

二、阅读程序（1）

#include <cstdlib>
#include <iostream>
using namespace std;

char encoder[26] = {'C', 'S', 'P', 0};
char decoder[26];
string st;

int main() {
    int k = 0;
    for (int i = 0; i < 26; ++i)
        if (encoder[i] != 0) ++k;
    for (char x = 'A'; x <= 'Z'; ++x) {
        bool flag = true;
        for (int i = 0; i < 26; ++i)
            if (encoder[i] == x) {
                flag = false;
                break;
            }
        if (flag) {
            encoder[k] = x;
            ++k;
        }
    }
    for (int i = 0; i < 26; ++i)
        decoder[encoder[i] - 'A'] = i + 'A';
    cin >> st;
    for (int i = 0; i < st.length(); ++i)
        st[i] = decoder[st[i] - 'A'];
    cout << st;
    return 0;
}

第 16 题（判断题，1.5 分）

输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。

( )

正确答案正确

解析详情

【答案】正确

【考点】数组下标安全

【解析】程序用 st[i]-'A' 作为 decoder 的下标。只有大写字母才能保证下标落在 0～25；其他字符可能产生负数或大于 25，导致越界访问。

【易错点】 cin 能读入非空字符串并不代表其中字符一定满足数组下标范围。

第 17 题（判断题，1.5 分）

若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。（）

正确答案错误

解析详情

【答案】错误

【考点】字符映射

【解析】构造完成后，T～Z 在 encoder 中的位置与字母序号相同，因此 decoder 对这些字母的映射不变。例如输入“T”，输出仍为“T”。

【易错点】替换表不是对 26 个字母都改变，后部字母存在固定点。

第 18 题（判断题，1.5 分）

将第 12 行的“i < 26”改为“i < 16”，程序运行结果不会改变。

正确答案正确

解析详情

【答案】正确

【考点】替换表构造

【解析】构造 encoder 时真正需要排除的是预置的 C、S、P，它们都位于数组前 3 项。把查重范围缩为前 16 项仍能识别这三个字母；后来追加的字母按递增顺序处理，不会再次出现。

【易错点】查重循环的作用是排除预置字符，不是每次都必须扫描完整数组。

第 19 题（判断题，1.5 分）

将第 26 行的“i < 26”改为“i < 16”，程序运行结果不会改变。

正确答案错误

解析详情

【答案】错误

【考点】解码表初始化

【解析】 decoder 需要根据 encoder 的 26 个位置完整赋值。若只处理前 16 项，O、Q、R、T～Z 等字符对应的 decoder 项不会被正确设置，含这些字符的输入会改变结果。

【易错点】全局数组未显式赋值的项会是 0，并不等于保留原字母映射。

第 20 题（单选题，3 分）

若输出的字符串为“ABCABCABCA”，则下列说法正确的是（）。

输入的字符串中既有 S 又有 P

输入的字符串中既有 S 又有 B

输入的字符串中既有 A 又有 P

输入的字符串中既有 A 又有 B

正确答案A

解析详情

【答案】A

【考点】逆向字符映射

【解析】 decoder 的映射中，输入 C、S、P 分别输出 A、B、C。因此输出“ABCABCABCA”对应的输入按“CSP”循环，必然同时含有 S 和 P。

【易错点】题目给的是输出串，应使用 decoder 的逆对应关系还原输入字符。

第 21 题（单选题，3 分）

若输出的字符串为“CSPCSPCSPCSP”，则下列说法正确的是（）。

输入的字符串中既有 P 又有 K

输入的字符串中既有 J 又有 R

输入的字符串中既有 J 又有 K

输入的字符串中既有 P 又有 R

正确答案D

解析详情

【答案】D

【考点】逆向字符映射

【解析】由 encoder 可得，输出 C、S、P 分别来自输入 P、R、N。因此输出“CSP”重复时，输入包含 P 和 R，符合 D。

【易错点】不要把输出中的 C、S、P 直接当成输入字符。

二、阅读程序（2）

#include <iostream>

using namespace std;

long long n, ans;
int k, len;
long long d[1000000];

int main() {
cin >> n >> k;
d[0] = 0;
len = 1;
ans = 0;
for (long long i = 0; i < n; ++i) {
++d[0];
for (int j = 0; j + 1 < len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len - 1] == k) {
d[len - 1] = 0;
d[len] = 1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}

假设输入的 n 是不超过 $2^{62}$ 的正整数，k 都是不超过 10000 的正整数，完成下面的判断题和单选题：

第 22 题（判断题，1.5 分）

若 k=1，则输出 ans 时，len=n。（）

正确答案错误

解析详情

【答案】错误

【考点】循环模拟与边界值

【解析】当 k=1，第一次将 d[0] 加到 1 后就触发进位，使 len 变为 2；此后更高位会累加到大于 1，len 并不会随 n 同步增长，因此 len=n 并非恒成立。

【易错点】 k=1 不是正常的进位制，不能套用常规位数公式。

第 23 题（判断题，1.5 分）

若 k>1，则输出 ans 时，len 一定小于 n。（）

正确答案错误

解析详情

【答案】错误

【考点】进位制位数

【解析】取 n=1、k=2，循环结束时计数器只有一位，即 len=1，与 n 相等而不是小于 n，所以“一定小于”不成立。

【易错点】判断全称结论时要检查 n=1 这样的最小边界。

第 24 题（判断题，1.5 分）

若 k>1，则输出 ans 时，k^{len} 一定大于 n。（）

正确答案正确

解析详情

【答案】正确

【考点】k 进制表示

【解析】当 k>1 时，数组 d 保存 n 的 k 进制各位，len 是所需位数。len 位所能表示的 n 满足 n<k^len，因此循环结束时 k^len 一定大于 n。

【易错点】当 n 恰为 k 的幂时会新增一位，此时不应把 len 少算 1。

第 25 题（单选题，3 分）

若输入的 n 等于 $10^{15}$ ，输入的 k 为 1，则输出等于（）。

(10^{30}-10^{15})/2

(10^{30}+10^{15})/2

10^{15}

正确答案D

解析详情

【答案】D

【考点】特殊进位模拟

【解析】当 k=1，每次执行 ++d[0] 都会使 d[0]==k，并恰好让 ans 增加 1。循环共执行 n=10^15 次，所以输出 ans=10^15。

【易错点】虽然高位数组状态不再像正常进位制，但 ans 仍按每轮一次进位累计。

第 26 题（单选题，3 分）

若输入的 n 等于 205,891,132,094,649（即 $3^{30}$ ），输入的 k 为 3，则输出等于（）。

3^{30}

(3^{30}-1)/2

3^{30}-1

(3^{30}+1)/2

正确答案B

解析详情

【答案】B

【考点】进位次数统计

【解析】从 0 累加到 n 时，第 j 位产生的进位次数为 ⌊n/3^j⌋。当 n=3^30，总进位数为 3^29+3^28+…+1=(3^30-1)/2。

【易错点】 ans 统计所有数位的进位总次数，不只是最高位扩展次数。

第 27 题（单选题，3 分）

若输入的 n 等于 100,010,002,000,090，输入的 k 为 10，则输出等于（）。

11,112,222,444,543

11,122,222,444,453

11,122,222,444,543

11,112,222,444,453

正确答案D

解析详情

【答案】D

【考点】十进制进位次数

【解析】对 k=10，总进位次数为 Σ⌊n/10^j⌋。代入 n=100010002000090，依次累加各级整除结果，得到 11,112,222,444,453。

【易错点】每次加一可能连续产生多级进位，这些进位都要计入 ans。

二、阅读程序（3）

#include <algorithm>
#include <iostream>
using namespace std;

int n;
int d[50][2];
int ans;

void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans);
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i - 1][0], b = d[i - 1][1];
int x = d[i][0], y = d[i][1];
d[i - 1][0] = a + x;
d[i - 1][1] = b + y;
for (int j = i; j < n - 1; ++j) {
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b - y);
dfs(n - 1, sum + s);
for (int j = n - 1; j > i; --j) {
d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
d[i - 1][0] = a, d[i - 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}

int main() {
cin >> n;
for (int i = 0; i < n; ++i) {

cin >> d[i][0];
for (int i = 0; i < n; ++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}

假设输入的 n 是不超过 50 的正整数， $d[i][0]$ 、 $d[i][1]$ 都是不超过 10000 的正整数，完成下面的判断题和单选题：

第 28 题（判断题，1.5 分）

若输入 n 为 $\theta$ ，此程序可能会死循环或发生运行错误。（）

正确答案错误

解析详情

【答案】错误

【考点】递归边界

【解析】题面中的 θ 表示 0。调用 dfs(0,0) 时不满足 n==1，但 for 循环条件 1<n 立即为假，函数直接返回，随后输出初值 ans=0，不会继续递归。

【易错点】没有命中递归基并不必然死循环，还要看递归调用所在的循环是否会执行。

第 29 题（判断题，1.5 分）

若输入 n 为 20，接下来的输入全为 0，则输出为 0。（）

正确答案正确

解析详情

【答案】正确

【考点】递归合并模拟

【解析】所有 d[i][0]、d[i][1] 都为 0 时，每次合并的增量 s=a+x+|b-y| 也为 0。任意合并顺序的累计 sum 都是 0，最终输出 0。

【易错点】 abs(b-y) 在 b、y 同为 0 时不会产生额外贡献。

第 30 题（判断题，1.5 分）

输出的数一定不小于输入的 d[i][0] 和 d[i][1] 的任意一个。（）

正确答案错误

解析详情

【答案】错误

【考点】反例构造

【解析】当 n=1 时，dfs(1,0) 直接用 sum=0 更新 ans，输出为 0；而题设允许输入的 d[0][0]、d[0][1] 为正数，所以输出可以小于输入元素。

【易错点】 “一定”成立需要覆盖 n=1，此时程序没有执行任何合并。

第 31 题（单选题，3 分）

若输入的 n 为 20，接下来的输入是 20 个 9 和 20 个 0，则输出为（）。

1890

1881

1908

1917

正确答案B

解析详情

【答案】B

【考点】递归合并贡献

【解析】每个元素为 (9,0)，把大小分别为 p、q 的两组合并，贡献为 9(p+q)。最大值由逐次把一个新元素并入已有组取得，组大小依次为 2～20，因此结果为 9×(2+3+…+20)=1881。

【易错点】每次贡献使用合并后整组的第一维和，不是固定加 9。

第 32 题（单选题，3 分）

若输入的 n 为 30，接下来的输入是 30 个 0 和 30 个 5，则输出为（）。

2000

2010

2030

2020

正确答案C

解析详情

【答案】C

【考点】递归合并与绝对值

【解析】元素均为 (0,5)，大小为 p、q 的两组合并时贡献为 5|p-q|。采用链式合并时各次贡献为 5×(0+1+…+28)，总和为 5×406=2030。

【易错点】两组第一维都是 0，贡献来自第二维组和之差，而不是第二维之和。

第 33 题（单选题，4 分）

若输入的n为15，接下来的输入是15到1，以及15到1，则输出为（）。

2440

2220

2240

2420

正确答案C

解析详情

【答案】C

【考点】递归合并计算

【解析】每个元素两维相等，合并和为 L、R 的两组时贡献为 L+R+|L-R|=2max(L,R)。按程序取到的最大累计值为 2×(15+29+42+…+119)=2240。

【易错点】绝对值中的 b、y 是当前两组的累计和，不能只代入最初的单个数。

三、完善程序（1）质因数分解

（质因数分解）给出正整数 n，请输出将 n 质因数分解的结果，结果从小到大输出。

例如：输入 n=120，程序应该输出 2 2 2 3 5，表示 $120=2\times2\times2\times3\times5$ 。输入保证 $2\leq n\leq10^9$ 。提示：先从小到大枚举变量 i，然后用 i 不停试除 n 来寻找所有的质因子。

试补全程序。

#include <stdio>
using namespace std;

int n, i;

int main() {
scanf("%d", &n);
for(i = ①; ② <= n; i++) {
③ {
printf("%d ", i);
n = n / i;
}
}
if(④)
printf("%d ", ⑤);
return 0;
}

第 34 题（单选题，3 分）

①处应填（）

1

n - 1

2

0

正确答案C

解析详情

【答案】C

【考点】质因数分解

【解析】最小质因数是 2，试除应从 i=2 开始。若从 1 开始，n/1 不会减小，还会导致循环无法结束。

【易错点】 1 不是质数，也不能作为质因数输出。

第 35 题（单选题，3 分）

②处应填（）

n / i

n / (i * i)

i * i

i * i * i

正确答案C

解析详情

【答案】C

【考点】试除法边界

【解析】只需枚举到平方根：若 n 仍有两个大于 1 的因子，其中至少一个不超过 √n。因此循环条件应为 i*i<=n，即②填 i*i。

【易错点】 n 会在试除过程中不断缩小，条件中的 n 是当前剩余值。

第 36 题（单选题，3 分）

③处应填（）

if (n % i == 0)

if (i * i <= n)

while (n % i == 0)

while (i * i <= n)

正确答案C

解析详情

【答案】C

【考点】重复质因子

【解析】同一个质因子可能出现多次，例如 120 含三个 2。只要 n%i==0，就应反复输出 i 并令 n/=i，所以必须使用 while。

【易错点】使用 if 只会除去一个 i，无法处理质因子的重复幂次。

第 37 题（单选题，3 分）

④处应填（）

n > 1

n <= 1

i < n / i

i + i <= n

正确答案A

解析详情

【答案】A

【考点】试除法剩余因子

【解析】循环结束后若 n>1，剩余的 n 必为尚未输出的质因数，需要再输出一次；若 n==1 则已经分解完毕。

【易错点】不能无条件输出剩余 n，否则完全除尽时会错误输出 1。

第 38 题（单选题，3 分）

⑤处应填（）

2

n / i

n

i

正确答案C

解析详情

【答案】C

【考点】质因数分解输出

【解析】 ④判断 n>1 后，要输出的正是试除后剩余的质因数 n，因此⑤填 n。

【易错点】此时 i 只是循环变量，不一定等于最终剩余的质因数。

三、完善程序（2）最小区间覆盖

（最小区间覆盖)给出 n 个区间，第 i 个区间的左右端点是 $[a_i, b_i]$ 。现在要在这些区间中选出若干个，使得区间 $[0, m]$ 被所选区间的并覆盖（即每一个 $\theta \leq i \leq m$ 都在某个所选的区间中）。保证答案存在，求所选区间个数的最小值。

输入第一行包含两个整数 n 和 m （ $1 \leqslant n \leqslant 5000, 1 \leqslant m \leqslant 10^{9}$ ）。

接下来 n 行，每行两个整数 $a_i$ ， $b_i$ （ $\theta \leqslant a_i$ ， $b_i \leqslant m$ ）。

提示：使用贪心法解决这个问题。先用 $\theta(n^{2})$ 的时间复杂度排序，然后贪心选择这些区间。

试补全程序。

#include <iostream>
using namespace std;

const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];

void sort() {
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①) {
                segment t = A[j];
                ②
            }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p = 1;
    for (int i = 1; i < n; i++)
        if (③)
            A[p++] = A[i];
    n = p;
    int ans = 0, r = 0;
    int q = 0;
    while (r < m) {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

第 39 题（单选题，3 分）

①处应填（）

A[j].b > A[j - 1].b

A[j].a < A[j - 1].a

A[j].a > A[j - 1].a

A[j].b < A[j - 1].b

正确答案B

解析详情

【答案】B

【考点】冒泡排序条件

【解析】后续贪心需要区间按左端点 a 非递减排列。冒泡排序发现 A[j].a<A[j-1].a 时应交换相邻区间，因此①填该条件。

【易错点】排序依据是左端点 a，不是区间右端点 b。

第 40 题（单选题，3 分）

②处应填（）

$A[j + 1] = A[j]$; $A[j] = t$;

$A[j - 1] = A[j]$; $A[j] = t$;

$A[j] = A[j + 1]$; $A[j + 1] = t$;

$A[j] = A[j - 1]$; $A[j - 1] = t$;

正确答案D

解析详情

【答案】D

【考点】相邻元素交换

【解析】已有 t=A[j]，交换 A[j-1] 与 A[j] 时，应先令 A[j]=A[j-1]，再令 A[j-1]=t，正好对应 D。

【易错点】临时变量保存的是 A[j]，赋值方向写反会覆盖原来的 A[j-1]。

第 41 题（单选题，3 分）

③处应填（）

A[i].b > A[p - 1].b

A[i].b < A[i - 1].b

A[i].b > A[i - 1].b

A[i].b < A[p - 1].b

正确答案A

解析详情

【答案】A

【考点】区间去冗余

【解析】左端点已递增，A[p-1] 是最后保留的区间。只有 A[i].b>A[p-1].b 时，新区间才能把覆盖范围向右推进，才应写入 A[p++]；否则它被前一区间包含。

【易错点】比较对象应是最后一个保留区间 A[p-1]，而不一定是原数组的 A[i-1]。

第 42 题（单选题，3 分）

④处应填（）

q + 1 < n \&\& A[q + 1].a <= r

q + 1 < n \&\& A[q + 1].b <= r

q < n \&\& A[q].a <= r

q < n \&\& A[q].b <= r

正确答案A

解析详情

【答案】A

【考点】区间覆盖贪心

【解析】当前已覆盖到 r，应继续考察所有左端点不超过 r 的候选区间。q 的下一个位置必须存在且满足 A[q+1].a<=r，所以条件为 q+1<n && A[q+1].a<=r。

【易错点】判断能否衔接当前覆盖范围看左端点 a，而不是右端点 b。

第 43 题（单选题，3 分）

⑤处应填（）

r = \max(r, A[q + 1].b)

r = \max(r, A[q].b)

r = \max(r, A[q + 1].a)

q++

正确答案B

解析详情

【答案】B

【考点】最小区间覆盖贪心

【解析】内层循环结束后，A[0..q] 的左端点都不超过 r；经过前面的去冗余处理，A[q] 的右端点最远。选择它后应更新 r=max(r,A[q].b)。

【易错点】 q 已经指向当前可选的最右候选，使用 A[q+1] 会越过候选范围。