GESP 客观题评测系统

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

CSPJ-2019-R1

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

一、单项选择题

第 1 题（单选题，2 分）

中国的国家顶级域名是（）

.ch

.china

.cn

.chn

正确答案C

解析详情

【答案】C

【考点】国家顶级域名

【解析】中国的国家代码顶级域名是 .cn；.ch 是瑞士的国家代码顶级域名。

【易错点】不要按国家英文名称自行拼接域名后缀，国家代码顶级域名以正式分配为准。

第 2 题（单选题，2 分）

二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑与运算的结果是（）。

01 0010 1000 1011

01 0010 1000 0001

01 0010 1000 0011

01 0010 1001 0011

正确答案C

解析详情

【答案】C

【考点】二进制逻辑与

【解析】逐位计算 AND，只有对应位都为 1 时结果才为 1：11 & 01 = 01，1011 & 0110 = 0010，1001 & 1110 = 1000，0111 & 1011 = 0011。因此结果为 01 0010 1000 0011。

【易错点】逻辑与必须按位对齐计算，不能把它当作普通乘法或逻辑或。

第 3 题（单选题，2 分）

一个 32 位整型变量占用（）个字节。

128

正确答案B

解析详情

【答案】B

【考点】位与字节的换算

【解析】 1 字节等于 8 位，所以 32 位整型变量占用 32 ÷ 8 = 4 字节。

【易错点】题目给的是位数，不能直接把 32 当作字节数。

第 4 题（单选题，2 分）

若有如下程序段，其中 s、a、b、c 均已定义为整型变量，且 a、c 均已赋值（c 大于 0）

s = a;

for (b = 1; b <= c; b++) s = s - 1;

则与上述程序段功能等价的赋值语句是（）

s = a - c;

s = b - c;

s = a - b;

s = s - c;

正确答案A

解析详情

【答案】A

【考点】循环等价变换

【解析】循环中 b 从 1 到 c，共执行 c 次，每次令 s 减 1。由于初值 s = a，循环结束后 s = a - c。

【易错点】循环结束时 b 为 c + 1，但 s 的变化次数是 c 次。

第 5 题（单选题，2 分）

设有 100 个已排好序的数据元素，采用折半查找时，最大比较次数为（）

正确答案D

解析详情

【答案】D

【考点】折半查找复杂度

【解析】最坏比较次数为 ⌊log₂100⌋ + 1。因为 2⁶ < 100 < 2⁷，所以最多比较 7 次。

【易错点】不要只取 ⌊log₂n⌋ 而漏掉最后一次比较。

第 6 题（单选题，2 分）

链表不具有的特点是（）

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

插入删除不需要移动元素

可随机访问任一元素

不必事先估计存储空间

正确答案C

解析详情

【答案】C

【考点】链表的访问方式

【解析】链表结点通过指针相连，访问第 i 个元素必须从表头沿链逐个查找，不能像数组一样按下标随机访问。插入、删除时通常只需调整指针。

【易错点】链表的动态存储不等于支持随机访问。

第 7 题（单选题，2 分）

把 8 个同样的球放在 5 个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的分法？（）提示：如果 8 个球都放在一个袋子里，无论是哪个袋子，都只算同一种分法

正确答案B

解析详情

【答案】B

【考点】整数拆分

【解析】同样的球和袋子只由各袋球数决定，问题等价于把 8 拆成至多 5 个正整数之和。8 的全部整数拆分有 22 种，其中使用 6、7、8 个非空袋的共有 4 种，故答案为 22 - 4 = 18。

【易错点】袋子相同，交换两个袋子的球数不会产生新分法。

第 8 题（单选题，2 分）

一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二叉树中的结点（根结点的下标为1，若某结点的下标为i，则其左孩子位于下标2i处、右孩子位于下标2i+1处），则该数组的最大下标至少为（）。

正确答案A

解析详情

【答案】A

【考点】二叉树顺序存储

【解析】结合图中结构，从根结点下标 1 出发，右孩子为 3；其右孩子为 7，7 的右孩子为 15。图中最深结点占用下标 15，因此数组最大下标至少为 15。

【易错点】顺序存储的最大下标由结点位置决定，不等于二叉树的结点总数。

第 9 题（单选题，2 分）

100以内最大的素数是（）。

正确答案D

解析详情

【答案】D

【考点】素数判定

【解析】 97 不被 2、3、5、7 中任何一个素数整除，而判断 97 是否为素数只需检查到 √97。因此 97 是素数，也是 100 以内最大的素数。

【易错点】 91 = 7 × 13、93 = 3 × 31，都不是素数。

第 10 题（单选题，2 分）

319 和 377 的最大公约数是（）。

正确答案A

解析详情

【答案】A

【考点】最大公约数

【解析】 319 = 11 × 29，377 = 13 × 29，除 29 外两边剩余因子互质，所以最大公约数为 29。

【易错点】找到公因数后还要确认它是最大公约数。

第 11 题（单选题，2 分）

新学期开学了，小胖想减肥，健身教练给小胖制定了两个训练方案。方案一：每次连续跑 3 公里可以消耗 300 千卡（耗时半小时）；方案二：每次连续跑 5 公里可以消耗 600 千卡（耗时 1 小时）。小胖每周周一到周四能抽出半小时跑步，周五到周日能抽出一小时跑步。另外，教练建议小胖每周最多跑 21 公里，否则会损伤膝盖。请问如果小胖想严格执行教练的训练方案，并且不想损伤膝盖，每周最多通过跑步消耗多少千卡？（）

3000

2400

2500

2520

正确答案B

解析详情

【答案】B

【考点】整数规划与最优选择

【解析】 5 公里方案每公里消耗 120 千卡，优于 3 公里方案的 100 千卡，应优先安排周五至周日的 3 次 5 公里。此时还可跑 6 公里，即安排 2 次 3 公里，总消耗为 3 × 600 + 2 × 300 = 2400 千卡。

【易错点】既要满足每天可用时间，也不能让总里程超过 21 公里。

第 12 题（单选题，2 分）

一副纸牌除掉大小王有 52 张牌，四种花色，每种花色 13 张。假设从这 52 张牌中随机抽取 13 张纸牌，则至少（）张牌的花色一致。

正确答案A

解析详情

【答案】A

【考点】抽屉原理

【解析】把 13 张牌按 4 种花色分组。若每种花色至多 3 张，总数至多为 4 × 3 = 12，因此必有一种花色至少出现 4 张。

【易错点】 “至少”问题应使用向上取整，即 ⌈13 ÷ 4⌉ = 4。

第 13 题（单选题，2 分）

一些数字可以颠倒过来看，例如 0、1、8 颠倒过来还是本身，6 颠倒过来是 9，9 颠倒过来看还是 6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 106 颠倒过来是 901。假设某个城市的车牌只由 5 位数字组成，每一位都可以取 0 到 9。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）

125

100

正确答案D

解析详情

【答案】D

【考点】翻转对称计数

【解析】第 1、2 位可各从 0、1、6、8、9 中选取，并唯一决定第 5、4 位；中间位只能是翻转后不变的 0、1、8。因此共有 5 × 5 × 3 = 75 个车牌。

【易错点】 6 与 9 翻转后互换，不能作为五位数的中间位。

第 14 题（单选题，2 分）

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为（）。

ABDEGJHCFI

ABDEGHJFIC

ABCDEFGHIJ

ABDEGHJCFI

正确答案D

解析详情

【答案】D

【考点】二叉树遍历序列还原

【解析】后序序列末尾 A 是根；由中序序列分得左子树 DBGEHJ、右子树 CIF。递归还原后，左子树前序为 BDEGHJ，右子树前序为 CFI，故整棵树前序为 ABDEGHJCFI。

【易错点】后序的根在末尾，而中序中根的左右两侧才分别对应左右子树。

第 15 题（单选题，2 分）

以下哪个奖项是计算机科学领域的最高奖? ()

鲁班奖

普利策奖

图灵奖

诺贝尔奖

正确答案C

解析详情

【答案】C

【考点】计算机科学奖项

【解析】图灵奖由 ACM 颁发，用于表彰对计算机事业作出持久而重大的技术贡献，被公认为计算机科学领域的最高奖项。

【易错点】诺贝尔奖没有设置计算机科学奖项。

二、阅读程序（1）

#include <cstdio>
#include <cstring>
using namespace std;
char st[100];
int main() {
    scanf("%s", st);
    int n = strlen(st);
    for (int i = 1; i <= n; ++i) {
        if (n % i == 0) {
            char c = st[i - 1];
            if (c >= 'a')
                st[i - 1] = c - 'a' + 'A';
        }
    }
    printf("%s", st);
    return 0;
}

第 16 题（判断题，1.5 分）

输入的字符串只能由小写字母或大写字母组成。（）

正确答案错误

解析详情

【答案】错误

【考点】scanf 字符串输入

【解析】 scanf("%s", st) 会读取一段非空白字符，并未限制字符必须是英文字母，因此输入也可以包含数字或其他非空白字符。

【易错点】程序对字符做大小写处理，不代表输入已被校验为字母。

第 17 题（判断题，1.5 分）

若将第8行的“i = 1”改为“i = 0”，程序运行时会发生错误。

正确答案正确

解析详情

【答案】正确

【考点】除零错误

【解析】当 i = 0 时，循环第一次就会计算 n % i，即对 0 取模；整数除数为 0 会产生运行错误。

【易错点】循环体中的取模运算要求 i 不能为 0。

第 18 题（判断题，1.5 分）

若将第8行的“i <= n”改为“i * i <= n”，程序运行结果不会改变。（）

正确答案错误

解析详情

【答案】错误

【考点】约数枚举

【解析】原循环处理 n 的所有约数 i 对应的第 i 个字符；改为 i × i <= n 后只枚举到 √n，会漏掉大于 √n 的约数，例如必定存在的约数 n，因此输出可能改变。

【易错点】只枚举到平方根时，还必须同步处理成对约数 n / i。

第 19 题（判断题，1.5 分）

若输入的字符串全部由大写字母组成，那么输出的字符串就跟输入的字符串一样。（）

正确答案正确

解析详情

【答案】正确

【考点】ASCII 大小写转换

【解析】程序仅在 c >= 'a' 时执行转换；大写英文字母的编码都小于 'a'，所以全大写输入中的字符均保持不变。

【易错点】条件 c >= 'a' 并不是“字符为大写字母”的判断。

第 20 题（单选题，3 分）

若输入的字符串长度为 18，那么输入的字符串跟输出的字符串相比，至多有（）个字符不同。

正确答案C

解析详情

【答案】C

【考点】约数个数

【解析】只有 i 是 18 的约数时，第 i 个字符才可能被改写。18 的正约数为 1、2、3、6、9、18，共 6 个；令这些位置原来都是小写字母即可达到 6 个不同字符。

【易错点】统计的是 18 的约数数量，不是循环执行的总次数。

第 21 题（单选题，3 分）

若输入的字符串长度为（），那么输入的字符串跟输出的字符串相比，至多有36个字符不同。

128

100000

正确答案D

解析详情

【答案】D

【考点】质因数分解与约数计数

【解析】最多改变的字符数等于字符串长度 n 的正约数个数。100000 = 2⁵ × 5⁵，所以约数个数为 (5 + 1)(5 + 1) = 36；按题目考察的约数计数应选 D，但该长度实际超过 st[100] 的安全容量。

【易错点】约数个数由各质因数指数加 1 后相乘，不能直接由数值大小判断。

二、阅读程序（2）

#include <cstdio>
using namespace std;
int n, m;
int a[100], b[100];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        a[i] = b[i] = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (a[x] < y && b[y] < x) {
            if (a[x] > 0)
                b[a[x]] = 0;
            if (b[y] > 0)
                a[b[y]] = 0;
            a[x] = y;
            b[y] = x;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == 0)
            ++ans;
        if (b[i] == 0)
            ++ans;
    }
    printf("%d\n", ans);
    return 0;
}

假设输入的 n 和 m 都是正整数，x 和 y 都是在 [1, n] 的范围内的整数，完成下面的判断题和单选题：

第 22 题（判断题，1.5 分）

当 $m \geq 0$ 时，输出的值一定小于 $2n$ （）

正确答案正确

解析详情

【答案】正确

【考点】数组配对状态统计

【解析】题设保证 m 为正整数，第一组 (x, y) 读入时 a[x] = b[y] = 0，条件必成立，因而至少有一个 a 元素和一个 b 元素非零。零元素总数至多为 2n - 2，必小于 2n。

【易错点】不能忽略题设中 m 为正整数这一前提。

第 23 题（判断题，1.5 分）

执行完第 27 行的 “++ans” 时，ans 一定是偶数。（）

正确答案错误

解析详情

【答案】错误

【考点】计数变量的奇偶性

【解析】每次执行 ++ans 都只增加 1，若增加前 ans 为偶数，执行后就变为奇数，因此执行到某一个 ++ans 时不能保证 ans 一定为偶数。

【易错点】虽然最终非零项常成对出现，但两个 if 中的递增是分开执行的。

第 24 题（判断题，1.5 分）

a[i]和b[i]不可能同时大于0。（）

正确答案错误

解析详情

【答案】错误

【考点】双向配对数组

【解析】 a[i] > 0 表示 i 作为 x 已配到某个 y，b[i] > 0 表示 i 作为 y 已配到某个 x。同一个编号 i 可以在不同输入对中分别承担这两个角色，所以二者可以同时大于 0。

【易错点】不要把 a[i] 与 b[i] 误认为同一对关系的两个互斥状态。

第 25 题（判断题，1.5 分）

若程序执行到第 13 行时，x 总是小于 y，那么第 15 行不会被执行。()

正确答案错误

解析详情

【答案】错误

【考点】条件分支判断

【解析】 x < y 只比较本次输入的两个编号，并不能推出 a[x] = 0。若 x 此前已经配对，使 a[x] > 0，且外层条件成立，清除旧配对的第 15 行仍会执行。

【易错点】输入值 x、y 的大小关系与数组状态 a[x] 没有直接等价关系。

第 26 题（单选题，3 分）

若 m 个 x 两两不同，且 m 个 y 两两不同，则输出的值为（）

2n+2

2n-2m

2n-2

正确答案C

解析详情

【答案】C

【考点】一一配对计数

【解析】各 x、各 y 均不重复时，每组输入到来时都有 a[x] = 0、b[y] = 0，因此 m 组全部建立配对。a、b 中各有 m 个非零元素，零元素总数为 (n - m) + (n - m) = 2n - 2m。

【易错点】输出统计的是两个数组中值为 0 的元素总数。

第 27 题（单选题，3 分）

若 m 个 x 两两不同，且 m 个 y 都相等，则输出的值为（）

2n-2

2m

2n-2m

2n

正确答案A

解析详情

【答案】A

【考点】冲突配对更新

【解析】所有 y 相同，因此任意时刻该 y 至多与一个 x 配对；遇到更大的 x 时程序会清除旧配对并换成新配对。最终 a、b 各恰有一个非零元素，故输出为 2n - 2。

【易错点】不同 x 竞争同一个 y，不会形成 m 组同时存在的配对。

二、阅读程序（3）

#include <iostream>
using namespace std;
const int maxn = 10000;
int n;
int a[maxn];
int b[maxn];
int f(int l, int r, int depth) {
    if (l > r)
        return 0;
    int min = maxn, mink;
    for (int i = l; i <= r; ++i) {
        if (min > a[i]) {
            min = a[i];
            mink = i;
        }
    }
    int lres = f(l, mink - 1, depth + 1);
    int rres = f(mink + 1, r, depth + 1);
    return lres + rres + depth * b[mink];
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    cout << f(0, n - 1, 1) << endl;
    return 0;
}
判断题

第 28 题（判断题，1.5 分）

如果 a 数组有重复的数字，则程序运行时会发生错误。（）

正确答案错误

解析详情

【答案】错误

【考点】递归分治与最小值选择

【解析】 a 中有重复值时，严格比较 min > a[i] 会选取区间内最先出现的最小值作为 mink。左右递归区间仍会缩小并最终结束，不会因此发生运行错误。

【易错点】重复最小值只影响选中哪一个位置，不会让递归区间保持不变。

第 29 题（判断题，1.5 分）

如果 b 数组全为 0，则输出为 0。（）

正确答案正确

解析详情

【答案】正确

【考点】递归返回值

【解析】每个非空递归区间新增的项都是 depth × b[mink]。当所有 b[i] = 0 时，这些项全部为 0，左右子树返回值相加后仍为 0。

【易错点】 a 数组只决定递归结构，实际累加权值来自 b 数组。

第 30 题（单选题，3 分）

当 n=100 时，最坏情况下，与第 12 行的比较运算执行的次数最接近的是：（）。

100

5000

600

正确答案C

解析详情

【答案】C

【考点】递归最坏时间复杂度

【解析】若每次最小值都位于区间一端，扫描区间长度依次为 100、99、…、1。比较总次数为 100 × 101 ÷ 2 = 5050，最接近 5000。

【易错点】极端划分会退化成单链，不能按 O(n log n) 估算。

第 31 题（单选题，3 分）

当n=100时，最好情况下，与第12行的比较运算执行的次数最接近的是：()。

5000

100

600

正确答案D

解析详情

【答案】D

【考点】递归最好时间复杂度

【解析】每次最小值位于中间时划分最均衡，100 个结点可按近似完全二叉树分布。深度 1 至 6 放满 63 个结点，余下 37 个在深度 7，总比较次数为 580，最接近 600。

【易错点】最好情况仍要在每个递归区间线性寻找最小值，不是只比较约 log₂n 次。

第 32 题（单选题，3 分）

当n=10时，若b数组满足，对任意 $0\leq i<n$ ，都有 $b[i]=i+1$ ，那么输出最大为（）。

385

383

384

386

正确答案A

解析详情

【答案】A

【考点】加权递归深度

【解析】让每次最小值依次出现在下标 0、1、…、9，可形成深度为 1、2、…、10 的递归链，并使 b[i] = i + 1 与深度同向排列。输出最大值为 1² + 2² + … + 10² = 385。

【易错点】输出不是 b[i] 的简单求和，还要乘以对应结点的递归深度。

第 33 题（单选题，4 分）

当n=100时，若b数组满足，对任意 $0\leq i<n$ ，都有 $b[i]=1$ ，那么输出最小为（）。

582

579

581

580

正确答案D

解析详情

【答案】D

【考点】二叉树最小深度和

【解析】当 b[i] = 1 时，输出就是 100 个结点的深度之和；递归树越平衡，该和越小。深度 1 至 6 的 63 个位置放满，另 37 个结点位于深度 7，深度和为 1 + 4 + 12 + 32 + 80 + 192 + 259 = 580。

【易错点】程序根结点的 depth 从 1 开始，不是从 0 开始。

三、完善程序（1）矩阵变幻

（矩阵变幻）有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字0变成矩阵 $\begin{bmatrix}0 & 0 \\ 0 & 1\end{bmatrix}$ ，数字1变成矩阵 $\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}$ 。最初该矩阵只有一个元素0，变幻n次后，矩阵会变成什么样？

例如，矩阵最初为： $[0]$ ；矩阵变幻1次后： $\begin{bmatrix}0 & 0 \\ 0 & 1\end{bmatrix}$ ；矩阵变幻2次后：

$ $\begin{bmatrix}{{{0}}}&{{{0}}}&{{{0}}}&{{{0}}} \\{{{0}}}&{{{1}}}&{{{0}}}&{{{1}}} \\{{{0}}}&{{{0}}}&{{{1}}}&{{{1}}} \\{{{0}}}&{{{1}}}&{{{1}}}&{{{0}}}\end{bmatrix}。$ $输入一行一个不超过 10 的正整数 n。输出变幻 n 次后的矩阵。

试补全程序。

提示：

“<<”表示二进制左移运算符，例如 $(11)_2<<2=(1100)_2$ ;

而 “^” 表示二进制异或运算符，它将两个参与运算的数中的每个对应的二进制位一一进行比较，若两个二进制位相同，则运算结果的对应二进制位为 0，反之为 1。

#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size];
void recursive(int x, int y, int n, int t) {
    if (n == 0) {
        res[x][y] = ①;
        return;
    }
    int step = 1 << (n - 1);
    recursive(②, n - 1, t);
    recursive(x, y + step, n - 1, t);
    recursive(x + step, y, n - 1, t);
    recursive(③, n - 1, !t);
}
int main() {
    scanf("%d", &n);
    recursive(0, 0, ④);
    int size = ⑤;
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j)
            printf("%d", res[i][j]);
        puts("");
    }
    return 0;
}

第 34 题（单选题，3 分）

①处应填（）

1

n% 2

t

0

正确答案C

解析详情

【答案】C

【考点】递归边界赋值

【解析】参数 t 表示当前子矩阵应生成的基础数字。当 n = 0 时子矩阵只剩一个单元，必须把该单元赋为 t，即 res[x][y] = t。

【易错点】边界值由当前状态 t 决定，不能固定写成 0 或 1。

第 35 题（单选题，3 分）

②处应填（）

x - step, y

x, y - step

x - step, y - step

x, y

正确答案D

解析详情

【答案】D

【考点】矩阵递归分块

【解析】当前矩阵左上角坐标为 (x, y)，边长减半后，左上子矩阵的起点仍是 (x, y)，因此应调用 recursive(x, y, n - 1, t)。

【易错点】只有跨到右侧或下侧子矩阵时才需要加 step。

第 36 题（单选题，3 分）

③处应填（）

x + step, y + step

x, y - step

x - step, y

x - step, y - step

正确答案A

解析详情

【答案】A

【考点】矩阵坐标偏移

【解析】右下子矩阵相对当前左上角在行、列方向都偏移 step，所以起点是 (x + step, y + step)；该象限同时把状态翻转为 !t。

【易错点】右下象限需要同时增加行坐标和列坐标。

第 37 题（单选题，3 分）

④处应填（）

n - 1, 0

n - 1, n % 2

n, 0

n, n % 2

正确答案C

解析详情

【答案】C

【考点】递归初始参数

【解析】题目要求从单个数字 0 开始并变幻 n 次，因此初始状态 t = 0，递归层数就是 n。调用应为 recursive(0, 0, n, 0)。

【易错点】 n 表示变幻次数，不能预先减 1。

第 38 题（单选题，3 分）

⑤处应填（）

n + 1

1 << n

1 << (n - 1)

1 << (n + 1)

正确答案B

解析详情

【答案】B

【考点】位移与矩阵规模

【解析】每变幻一次，矩阵的行数和列数都扩大为原来的 2 倍；从边长 1 开始，n 次后边长为 2ⁿ，即 1 << n。

【易错点】矩阵元素总数是 4ⁿ，但循环所需的 size 是边长 2ⁿ。

三、完善程序（2）计数排序

（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将 n 对 10000 以内的整数，从小到大排序。

例如有三对整数（3, 4）、（2, 4）、（3, 3），那么排序之后应该是（2, 4）、（3, 3）、（3, 4）。输入第一行为 n，接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。从小到大排序后输出。

数据范围 $1 \leq n \leq 10^{7}, 1 \leq a[i], b[i] \leq 10^{4}$ 。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord[] 存储第二关键字排序的结果，数组 res[] 存储双关键字排序的结果。试补全程序。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn], res[maxn], ord[maxn];
unsigned cnt[maxs + 1];

int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
scanf("%d%d", &a[i], &b[i]);
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
①; // 利用 cnt 数组统计数量
for (int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i];
for (int i = 0; i < n; ++i)
②; // 记录初步排序结果

memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < n; ++i)
③; // 利用 cnt 数组统计数量
for (int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i];
for (int i = n - 1; i >= 0; --i)
④; // 记录最终排序结果
for (int i = 0; i < n; ++i)
printf("%d %d\\n", ⑤);
return 0;
}

第 39 题（单选题，3 分）

①处应填（）

++cnt[a[i]]

++cnt[i]

++cnt[a[i] * maxs + b[i]]

++cnt[b[i]]

正确答案D

解析详情

【答案】D

【考点】计数排序频次统计

【解析】程序先按第二关键字 b 排序，因此第一轮必须统计每个 b[i] 的出现次数，写作 ++cnt[b[i]]。

【易错点】双关键字稳定排序要先处理次关键字 b，再处理主关键字 a。

第 40 题（单选题，3 分）

②处应填（）

ord[--cnt[b[i]]] = a[i]

ord[--cnt[a[i]]] = b[i]

ord[--cnt[b[i]]] = i

ord[--cnt[a[i]]] = i

正确答案C

解析详情

【答案】C

【考点】计数排序位置映射

【解析】前缀和 cnt[b[i]] 表示键值不大于 b[i] 的元素个数，先递减即可得到当前元素的目标下标。ord 应保存原数组下标 i，故为 ord[--cnt[b[i]]] = i。

【易错点】 ord 存的是元素下标，不是 a[i] 或 b[i] 的数值。

第 41 题（单选题，3 分）

③处应填（）

++cnt[a[i] * maxs + b[i]]

++cnt[a[i]]

++cnt[b[i]]

++cnt[i]

正确答案B

解析详情

【答案】B

【考点】双关键字计数排序

【解析】第二轮按第一关键字 a 排序，所以要重新清零 cnt，并用 ++cnt[a[i]] 统计各个 a 值的频次。

【易错点】第二轮的计数键应切换为 a，不能继续统计 b。

第 42 题（单选题，3 分）

④处应填（）

res[--cnt[a[ord[i]]] = ord[i]

res[--cnt[b[ord[i]]] = ord[i]

res[--cnt[a[i]]] = ord[i]

res[--cnt[b[i]]] = ord[i]

正确答案A

解析详情

【答案】A

【考点】稳定计数排序

【解析】 ord[i] 是已按 b 排序的原元素下标，第二轮应按其主关键字 a[ord[i]] 定位。逆序扫描并写入 res[--cnt[a[ord[i]]]] = ord[i]，可在 a 相同时保持 b 的次序。

【易错点】主关键字必须通过 ord[i] 找到原元素，不能直接使用 a[i]。

第 43 题（单选题，3 分）

⑤处应填（）

a[res[ord[i]]], b[res[ord[i]]]

a[res[i]], b[res[i]]

a[ord[res[i]]], b[ord[res[i]]]

a[i], b[i]

正确答案B

解析详情

【答案】B

【考点】排序结果下标输出

【解析】 res[i] 保存双关键字排序后第 i 个元素在原数组中的下标，因此应输出 a[res[i]] 和 b[res[i]]。

【易错点】 res 已是最终顺序，不需要再与 ord 进行一次嵌套索引。