2019 CSP-J 第一轮（入门级）参考答案与逐题解析（43 题全）

【参考答案与解析】 本文给出 2019 CSP-J 第一轮（入门级）全部 43 题的参考答案与关键推导。题目原文见本站《2019 CSP-J 第一轮（入门级）真题完整版（43 题）》。

⚠️ 答案为个人整理结果，非官方发布；若与 CCF 官方公布不一致，以官方为准。

一、参考答案速查表

分段小结：单选 1–15：A D C A A / D C C B C / C A C B A；阅读程序(1) × √ × √ B B；(2) √ × × × A A；(3) × √ A D D B；完善程序(1) C D B B B；(2) B D C A B。

二、单项选择题 1–15

1 A 中国国家顶级域名是 .cn。

2 D 逐位相与： 11101110010111 & 01011011101011 → 01001010000011，分组即 01 0010 1000 0011。

3 C 32 位 = 4 字节（1 字节 = 8 位）。

4 A 循环执行 c 次，每次 s 减 1 → s = a − c。

5 A 折半查找最大比较次数 = ⌈log₂(n+1)⌉ = ⌈log₂101⌉ = 7。

6 D 链表不能随机访问，只能顺序遍历。

7 C 这是「整数 8 拆成最多 5 个部分」的划分数：总划分 p(8) = 22，去掉部分数超过 5 的 4 种 → 18。

8 C 按图上二叉树的最深/最右结点位置编号，最大下标至少为 15（顺序存储要按「完全二叉树」位置开数组）。

9 B 100 以内最大素数 = 97（91 = 7×13 不是素数）。

10 C 辗转相除：377 − 319 = 58；319 = 5×58 + 29；58 = 2×29 → gcd = 29。

11 C 方案一 100 千卡/公里、方案二 120 千卡/公里，优先方案二：3 次方案二（15 km, 1800）+ 2 次方案一（6 km, 600）→ 合计 2400 千卡，且 21 km 不超限。

12 A 抽屉原理：13 张分到 4 种花色 → 至少 ⌈13/4⌉ = 4 张同花色。

13 C 第 1 位与第 5 位、第 2 位与第 4 位必须互为颠倒，可选 (0,0)、(1,1)、(8,8)、(6,9)、(9,6) 共 5 种；中间位只能取 0、1、8 共 3 种。5 × 5 × 3 = 75。

14 B 后序最后一个 A 为根，中序分成 DBGEHJ | A | CIF；左子树根为 B（D | B | GEHJ），依次展开得前序 ABDEGHJCFI。

15 A 计算机科学最高奖是图灵奖。

三、阅读程序 16–33

程序（1）：按约数位置改写字符（16–21）

功能：扫描位置 i = 1 ~ n，若 i 是 n 的约数，就把第 i−1 个字符（下标从 0 起）从小写改成大写。

• 16 ×：程序没有做任何字符合法性检查，输入什么字符都能跑，说「只能由字母组成」是错的。
• 17 √：改成 i = 0 后要计算 n % 0，除零错误。
• 18 ×：i * i < n 只能枚举到 √n 附近的 i，会漏掉 √n ~ n 之间的约数，结果会变。
• 19 √：全大写时 c >= 'a' 恒不成立，不做任何修改，输出与输入相同。
• 20 B：n = 18 时约数位置有 1、2、3、6、9、18 共 6 个 → 至多 6 个字符不同。
• 21 B：约数个数等于 36 的数，100000 = 2⁵×5⁵ 的约数个数 = 6×6 = 36，故选 100000。

程序（2）：双数组配对（22–27）

功能：a[x] = y 与 b[y] = x 互为反向索引，读入 (x, y) 时先拆掉旧配对再建新配对，最后统计 a、b 中为 0 的位置总数。

⚠️ 网上误抄提醒：第 13 行流通版本多写作 if (a[x] < b[y])，但 0 < 0 恒假会让程序永远不配对，与官方答案（2n−2m、2n−2）矛盾。本文按自洽版本 if (a[x] >= b[y]) 采用。

• 22 √：m > 0 时至少有一对位置被占用，ans = 2n − 2×(配对数) < 2n。
• 23 ×：每次 ++ans 之后没有配 parity 约束，ans 可以是奇数。
• 24 ×：a[i] 与 b[i] 是两条独立索引，完全可以同时大于 0。
• 25 ×：x < y 与是否执行第 15 行无关，第 15 行取决于 a[x] > 0。
• 26 A：x、y 都两两不同 → 恰好 m 对配对，ans = 2n − 2m。
• 27 A：y 全部相等 → 最终只保留 1 对配对，ans = 2n − 2。

程序（3）：最小值分治递归（28–33）

功能：在区间里找 a 的最小值位置 mink 作为根，左右递归，代价累加 depth * b[mink]——本质是笛卡尔树的构造与加权深度和。

• 28 ×：a 有重复只影响取哪个最小值位置，不会运行错误。
• 29 √：b 全为 0，所有 depth × b[mink] 都是 0 → 输出 0。
• 30 A：最坏情况是 a 单调（树退化成链），比较次数 ≈ n(n+1)/2 = 5050 → 最接近 5000。
• 31 D：最好情况是平衡树，比较次数 ≈ n log₂n ≈ 600。
• 32 D：n = 10、b[i] = i+1 时，让最大的 b 落在最深处 → 最大值 385。
• 33 B：n = 100、b[i] = 1 时，输出等于树的所有结点深度和，平衡时最小 → 580。

四、完善程序 34–43

程序（1）：矩阵变幻（34–38）

思路：分形递归。把当前 2ⁿ×2ⁿ 区域分成四个 2ⁿ⁻¹×2ⁿ⁻¹ 子块，左上、右上、左下沿用当前值 t，右下取反 !t；递归到 n = 0 时写入 t。

程序（2）：双关键字计数排序（39–43）

思路：先按第二关键字 b 做一趟计数排序（结果存入 ord），再按第一关键字 a 做第二趟（从后往前保证稳定性，结果存入 res）。

五、写在最后

2019 年是 CSP-J 的首届，卷子风格与后来几年差别明显：

1. 常识题占比高——国家域名、字节换算、图灵奖、链表特点，纯记忆题就有近 5 道；
2. 数学味浓——整数划分（第 7 题）、抽屉原理（第 12 题）、颠倒车牌计数（第 13 题）都是数学建模题；
3. 阅读程序偏「读代码」而非「读算法」——程序（1）就是考约数枚举，把循环条件看准就能做。

复盘建议：重点弄懂程序（3）的笛卡尔树模型（它一次性决定了 30–33 四道题），以及双关键字计数排序的两趟流程（这是后续所有排序类完善程序的母题）。

本站提供该年分三卷的 Hydro 客观题包（单选 / 阅读程序 / 完善程序），导入 OJ 即可自测判分。

来源说明：题目整理自网络流传的 CCF《2019 CCF 非专业级别软件能力认证第一轮（CSP-J1）入门级 C++ 语言试题》版本；答案与解析为本站原创整理，关键题目（第 2、5、10、11、12、13、14、21、30–33 题等）已通过计算与程序验证。若与 CCF 官方公布不一致，以官方为准，仅供学习交流。