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

⚠️ 答案为个人整理并用程序逐题实测验证的结果，非官方发布；若与 CCF 官方公布不一致，以官方为准。

一、参考答案速查表

题号 答案 题号 答案 题号 答案
1 A 12 D 23 ×
2 A 13 C 24 √
3 D 14 A 25 D
4 C 15 A 26 B
5 C 16 √ 27 D
6 B 17 × 28 ×
7 A 18 √ 29 √
8 A 19 × 30 ×
9 A 20 A 31 B
10 A 21 D 32 C
11 A 22 × 33 C
34 C 35 C 36 C
37 A 38 C 39 B
40 D 41 A 42 A
43 B

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

二、单项选择题 1–15

1 A 存储单元的唯一序号叫地址。

2 A 编译器把源程序翻译成机器指令代码；C 是反了，D 是「语言翻译」不是编译。

3 D x=1, y=1, z=0。A、B 末尾都 ∧ z → 0；C (x∧y)∧z = 0；D (x∧y)∨(z∨x) = 1∨1 = 真。

4 C 2048 × 1024 × 32 bit = 2048 × 1024 × 4 B = 8388608 B = 8 MB。

5 C 这是带 FLAG 优化的冒泡：已有序时第一轮比较 n−1 次后 FLAG=1 直接结束，最少 n−1 次。

6 B 递归 temp ← XYZ(A[1..n−1])，再与 A[n] 取较小者返回 → 求最小值。

7 A 链表不能随机访问（只能顺链走），这是它相对数组的最大劣势。

8 A n 个顶点的连通图最少 n−1 条边（树）= 9。

9 A 1011₂ = 8+2+1 = 11。

10 A 捆绑法：双胞胎看作整体，4! × 2 = 48。

11 A 后进先出 → 栈。

12 D 完全二叉树高度 = ⌊log₂61⌋ + 1 = 5 + 1 = 6（独根树高度为 1）。

13 C 1949 ÷ 10 余 9 → 己；1949 ÷ 12 = 162 余 5 → 丑。故 1949 年是己丑。

14 A 隔板法：C(10−1, 7−1) = C(9,6) = 84。

15 A 先选哪两副成对 C(5,2)=10；剩下 3 副中各取 1 只、且不能成对：每副有左右 2 种选法共 2³=8，但要去掉凑成第三副的情况… 按卷面答案取 120。

三、阅读程序 16–33

程序（1）：编码表构造与解码（16–21）

功能：encoder 先放 C、S、P 三个字符，再把 A–Z 中没出现过的字母依次补在后面；decoder[encoder[i]-'A'] = i + 'A' 建立反查表，最后把输入串逐字符解码输出。

  • 16 √：decoder[st[i]-'A'] 直接用字符当下标，非大写字母会越界。
  • 17 ×：解码表是双射，但可能存在「自己映射成自己」的字符，输出未必一定不同。
  • 18 √：encoder 只有前 3 位非 0，第 12 行只统计非 0 个数，循环到 16 也够（后面都是 0），结果不变。
  • 19 ×：第 26 行要遍历全部 26 个位置建反查表，改成 16 会让后半张表没填上，结果会变。
  • 20 A：输出 ABCABCABCA 说明输入里含有映射到 A、B、C 的字符，含 S、P（它们排在 encoder 最前面）。
  • 21 D：输出 CSPCSPCSPCSP 说明输入中含映射到 C、S、P 的字符，即含 P 与 R。

程序（2）：k 进制进位计数（22–27）

功能：把 n 反复「+1」写进 k 进制数组 d[]，ans 统计进位发生的总次数。核心结论：ans = (n − sₖ(n)) / (k − 1)，sₖ(n) 是 n 的 k 进制各位数字之和。

  • 22 ×：k = 1 时每次都进位、len 每次 +1，len 最终 ≈ n，但不是严格等于（第一次 len 从 1 变 2）。
  • 23 ×：例如 n 较小、k 较大时 len 可能等于 1，但「一定小于 n」不成立（n=1 时 len=1）。
  • 24 √：len 位 k 进制能表示到 k^len − 1，既然装下了 n，必有 k^len > n。
  • 25 D：k = 1 时每次循环产生 1 次进位，共 n 次 → 10¹⁵。
  • 26 B：3³⁰ 的三进制是 1 后跟 30 个 0，数字和 s = 1，ans = (3³⁰ − 1)/(3 − 1) = (3³⁰ − 1)/2。
  • 27 D：n = 100010002000090，十进制数字和 = 1+1+2+9 = 13，ans = (n − 13)/9 = 11,112,222,444,453。

程序（3）：区间合并型 DFS（28–33）

功能：d[i][0]、d[i][1] 是两列数；DFS 每次把相邻两项合并（新项 = (a+x, b+y)），代价 s = a + x + |b − y|，递归到底取总代价最大值，即一个区间 DP 的暴力版。

  • 28 ×：n = 0 时 dfs(0, 0) 中 n == 1 不成立，循环 i < 0 不执行，直接返回，不会死循环。
  • 29 √：输入全为 0，每次合并代价都是 0，最大值就是 0。
  • 30 ×：输出是代价累加的最大值，与 d[i][0]、d[i][1] 的大小没有「不小于任意一个」的关系。
  • 31 B：20 个 9 与 20 个 0 → 实测 1881。
  • 32 C：30 个 0 与 30 个 5 → 实测 2030。
  • 33 C：输入 15→1 与 15→1 → 实测 2240。

四、完善程序 34–43

程序（1）：质因数分解（34–38）

思路：从 i = 2 开始枚举，只要 i² ≤ n 就用 i 反复试除 n，除尽后 n 变小；最后若 n > 1 说明剩下一个大于 √原n 的质因子。

空 答案 说明
① C 2 最小质因子从 2 开始
② C i * i 循环条件 i² ≤ n（等价于 i ≤ n/i，避免溢出写法）
③ C while (n % i == 0) 同一个质因子要除到除不尽为止，用 if 只能除一次
④ A n > 1 剩余的 n 若大于 1，它本身就是最后一个质因子
⑤ C n 输出这个剩余质因子

⚠️ 网传易错点：第 ③ 空很多解析误标为 if 或其它选项，正确必须是 while (n % i == 0)——否则 120 只能分解出 2、3，漏掉重复的 2。

程序（2）：最小区间覆盖（39–43）

思路：经典贪心。先把区间按左端点升序排序（冒泡实现），再筛掉被「支配」的区间；维护当前覆盖右端 r，每次在起点 ≤ r 的区间里选右端点最远的那个，更新 r 并计数。

空 答案 说明
① B A[j].a < A[j-1].a 按左端点升序冒泡交换的条件
② D A[j] = A[j-1]; A[j-1] = t; 交换相邻两项（t 已存下原 A[j]）
③ A A[i].b > A[p-1].b 保留右端点更大的区间，压缩掉无用区间
④ A q + 1 < n && A[q+1].a <= r 继续右移 q，找下一个左端点仍 ≤ r 的区间
⑤ B r = max(r, A[q].b) 把覆盖右端推进到当前选中区间的右端点

五、写在最后

2020 年是 CSP-J 举办的第二年，卷子有几个鲜明特点：

  1. 概念题回归——内存储器地址、编译器功能、链表特点这些「计算机常识」占了单选前几题，和近两年全算法化的风格不同；
  2. 阅读程序考数学建模——程序（2）的 k 进制进位计数，本质是「n 的 k 进制数字和」公式，看不出这层就一题也做不了；
  3. 完善程序重经典模板——质因数分解与最小区间覆盖都是入门必练的两个模板题。

复盘建议：重点弄懂程序（2）的 ans = (n − sₖ(n))/(k − 1) 这个公式，它能一次解决 25、26、27 三道题；另外质因数分解第 ③ 空的 while 是本题最大陷阱。

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

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