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

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

一、参考答案速查表

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

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

二、单项选择题 1–15

第 1 题　A

32 位无符号整数取值范围 0 ~ 2³²−1 = 4294967295 ≈ 4.29 × 10⁹，最接近 4 × 10⁹。

考点：整数表示范围。易错点：把 2³² 记成 2 × 10⁹（那是有符号 int 的上界量级）。

第 2 题　B

x & (x-1) 的作用是把最低位的 1 清零。x = 255 = 11111111₂，x−1 = 254 = 11111110₂，按位与得 11111110₂ = 254。

考点：位运算技巧（判 2 的幂、统计 1 的个数都靠它）。

第 3 题　B

递归展开：

  • calc(2) = calc(1) + 1 = 2
  • calc(3) = calc(2) + calc(1) = 2 + 1 = 3
  • calc(4) = calc(2) + 1 = 3
  • calc(5) = calc(4) + calc(3) = 3 + 3 = 6

考点：递归求值。陷阱：容易漏掉 calc(1) = 1 这个边界，或把 calc(4) 算成 calc(2)+1 之外的结果。

第 4 题　B

哈夫曼构造（每次取最小的两个合并）：10+12 = 22 → {15, 20, 22, 25}；15+20 = 35 → {22, 25, 35}；22+25 = 47 → {35, 47}；35+47 = 82。

WPL = 所有合并值之和 = 22 + 35 + 47 + 82 = 186。

考点：哈夫曼树与带权路径长度。技巧：WPL 等于每次合并的权值总和，不必真的画树算深度。

第 5 题　B

有向图中每条边贡献 1 个出度和 1 个入度，故入度总和 = 出度总和 = 边数。

考点：有向图度数性质（对比无向图：度数和 = 2 × 边数）。

第 6 题　C

总选法 C(9,4) = 126，减去「全男生」C(5,4) = 5 与「全女生」C(4,4) = 1：126 − 5 − 1 = 120。

考点：组合计数与补集思想。易错点：忘了减「全女生」得 121（选项 B 就是这个坑）。

第 7 题　C

原式 = a && (b || !c)（提取公因子 a）。

  • A：a && (b || !c) 显然相等；
  • B：(a||!c) && (b||!c) = (a&&b) || !c，再 && (a||a)=a → a && ((a&&b)||!c) = (a&&b) || (a&&!c) 相等；
  • D：!(!a||!b) = a&&b，故整体 = (a&&b) || (a&&!c) 相等；
  • C：a && (!b || c) = a && !(b && !c)，与原式不等（取 a=1, b=1, c=0：原式 = 1，C = 0）。

考点：布尔代数化简（德摩根律、分配律）。

第 8 题　D

模 7 的斐波那契序列存在周期，前 16 项为 1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0，第 17 项回到 1，周期为 16。2025 ÷ 16 余 9，f[2025] = f[9] = 6。

考点：取模递推的周期性（找循环节）。

第 9 题　B

  • A 错：string 长度可变（append、+= 等）；
  • B 对：string + char 有重载，合法；
  • C 错：length() 与 size() 完全等价；
  • D 错：C++11 起 string 内部以 ‘\0’ 结尾，但该字符不计入 length()。

考点：string 的基本性质。

第 10 题　C

注意参数：a 是引用、b 是值传递。进入时 a=5, b=10：

  • a = a + b → a = 15（x 变成 15）；
  • b = a - b → b = 5（只改局部副本）；
  • a = a - b → a = 10（x 变成 10）。

main 中 y 从未被修改，仍为 10 → 输出 10, 10。

考点：引用传递 vs 值传递。陷阱：这函数本意是交换两个数，但 b 不是引用，交换失败。

第 11 题　B

从 (1,1) 到 (4,5) 需向下 3 步、向右 4 步，共 7 步，路径数 = C(7,3) = 35。

考点：组合数学路径计数。

第 12 题　B

冒泡排序的交换次数 = 数组的逆序对个数。{6,1,5,2,4} 的逆序对：(6,1)、(6,5)、(6,2)、(6,4)、(5,2)、(5,4) 共 6 个。

考点：冒泡排序与逆序对。技巧：不用一步步模拟冒泡，直接数逆序对。

第 13 题　A

270₈ = 2×64 + 7×8 + 0 = 184；720 + 184 = 904；904 = 3×256 + 8×16 + 8 = 388₁₆。

考点：进制转换。

第 14 题　C

完全二叉树叶子数 = n − ⌊n/2⌋ = 1000 − 500 = 500。

考点：完全二叉树性质。

第 15 题　A

逐步模拟（栈 S 后进先出）：

输入 奇偶 动作 栈 S 队列 P
7 奇 入栈 [7] []
5 奇 入栈 [7,5] []
8 偶 弹出 5 [7] [5]
3 奇 入栈 [7,3] [5]
1 奇 入栈 [7,3,1] [5]
4 偶 弹出 1 [7,3] [5,1]
2 偶 弹出 3 [7] [5,1,3]

队列 P = 5, 1, 3。

考点：栈与队列的手工模拟。易错点：选项 C 是「3,1,5」，那是从栈底取的结果——栈必须取栈顶。

三、阅读程序 16–33

程序（1）：gcd 两两互质三元组（16–21）

功能：三重循环枚举 1 ≤ i < j < k ≤ n，统计三个数两两互质的三元组个数。gcd 是标准辗转相除。

  • 16 √：n = 2 时 k 从 j+1 = 3 开始，循环体一次都不进，第 16 行判断确实不会执行。
  • 17 ×：删掉 gcd(i,k)==1 后，只要 i、j 互质且 j、k 互质就计数，条件放宽，答案会变大。
  • 18 √：n ≥ 3 时三元组 (1,2,3) 一定满足（1 与任何数互质、2 与 3 互质），故输出至少为 1。
  • 19 B：改成 gcd(a, a % b) 后，递归第一参数恒为 a，最终返回的一定是 a 本身（b 递减到 0 时返回 a）。于是 gcd(i,j)==1 基本只在 i=1 时成立 —— 实测 n=8：原答案 25，改动后 0，明显变小（网传有版本答 A「变大」，是错的）。
  • 20 D：n = 8 时枚举得 25（实测）。
  • 21 A：gcd(36, 42) = 6（辗转相除：36%42 = 36 → gcd(42,36) → gcd(36,6) → gcd(6,0) = 6）。

程序（2）：排序去重后的分段贪心（22–27）

功能：把数组排序去重，然后用双指针把「差值不超过 k」的元素尽可能划进同一段，求最少段数。j 是单调左指针，a[i] - a[j+1] > k 时右移。

  • 22 √：输入 3 1 3 2 1 → n=3, k=1，排序去重后 a = [1,2,3]。模拟：i=1 时 ans[1]=1；i=2 时 2−1=1 不 >1，j 不动，ans[2]=ans[0]+1=1；i=3 时 3−1=2 >1 → j=1，再看 3−2=1 不 >1，ans[3]=ans[1]+1=2。正确。
  • 23 √：段数不超过元素个数 n，且至少为 1。
  • 24 ×：这道题网上争议最大。去重后重复元素被移除；若不去重，重复元素差值为 0 ≤ k，必然落在同一段，对 ans[i] = ans[j] + 1 的递推不产生新段。我用随机 3000 组数据对比「有/无 unique」的输出，0 组不同，故判断为 ×（不会出现不同结果）。
  • 25 B：第 18 行执行时，j ≤ i、j ≤ n、a[j] < a[i] 都恒成立；而 a[i] - a[j] > k 不一定成立（当 j == i 时左边为 0）。题目问「不包括」，选 B。
  • 26 A：n=100, k=2, a = 1..100，每段最多容纳差值 ≤ 2 的连续数（即 3 个数），100 个数需要 ⌈100/3⌉ = 34 段。
  • 27 B：删掉排序后，双指针的单调性失效，j 会被推得更远，导致分出来的段数变少（实测随机 3000 组，答案变小或不变，从不变大）。

程序（3）：最长公共子序列 LCS（28–33）

功能：标准 O(n²) LCS 动态规划。第 18 行是状态转移中的「继承上/左」，a[i]==b[j] 时再尝试「左上 +1」。

  • 28 √：LCS([1,2,3,4], [1,3,2,2]) = 2（如取 1,3 或 1,2）。
  • 29 √：f[i][j] 是前缀 LCS，随 i、j 单调不减，故任意 f[i][j] ≤ f[n][n]。
  • 30 ×：删掉第 18 行就失去了「不选当前字符」的转移，只有完全匹配才更新，答案会变小，结果一定受影响。
  • 31 D：LCS ≤ n、≥ 0、且可以为 0（两数组无公共元素）→ 「以上均是」。
  • 32 A：排序后两序列都变为升序，LCS 变成 ∑ min(cnt_a(x), cnt_b(x))，这是相同元素组成下可能达到的最大值，故答案只可能变大或不变（实测随机 2000 组验证）。
  • 33 B：当 a = {1,2,…,n}（严格递增且每个数恰一次）时，与 b 的 LCS 等价于求 b 的最长上升子序列 LIS（实测 500 组随机数据完全一致）。

四、完善程序 34–43

程序（1）：字符串解码（行程长度编码）34–38

思路：扫描压缩串 z。若当前字符后紧跟数字，说明是「字符 + 重复次数」，读出完整数字后重复输出；否则该字符只出现一次，直接追加并前进一位。

空 答案 说明
① C i + 1 < z.length() 必须先保证 z[i+1] 不越界，否则访问越界；i < z.length() 由外层循环已保证，不足以防止 z[i+1] 越界
② B count * 10 + (z[i] - '0') 多位数字要按位累加（如 A12 要读成 12，不是 1+2）
③ B count 重复 count 次输出字符
④ B ch 单字符情形直接追加当前字符
⑤ C i++ 前进一位；不前进会死循环

小提示：⑤ 若不执行 i++，i 永远不变，程序将陷入死循环——这也是排除 D 的理由。

程序（2）：精明与糊涂（多数派候选）39–43

思路：这是「Boyer-Moore 多数投票」的变体。candidate 是当前候选，count 是它的净支持数。扫描每个人 i：

  • 若 count 归零，说明前面的抵消完了，把 i 立为新候选；
  • 否则让候选者与新来者互相判断：只要有一方说对方糊涂，说明两人中至少有一个是糊涂人，可以同时淘汰（count–）；
  • 若都说对方精明，则两人同类，count++。

由于精明人严格过半，最终剩下的 candidate 必定是精明人。

空 答案 说明
① B 1 初始时 0 号作为候选，支持数为 1
② C count == 0 支持数归零才更换候选
③ D query(candidate,i)==false \|\| query(i,candidate)==false 任一方指认对方糊涂即可同时淘汰；用 &&（选项 C）会漏掉单方指认的情形
④ A count-- 淘汰一对，支持数减一
⑤ C candidate 输出最终候选者，即找到的精明人

五、写在最后：这套卷子的特点

与 2026 年那套相比，2025 年 CSP-J 第一轮有几个明显不同的味道：

  1. 代码阅读量大、模拟题少——阅读程序三组分别是 gcd 计数、双指针分段、LCS，都是「看懂算法本质就能秒答、看不懂就全蒙」的类型；
  2. 数学与数据结构并重——哈夫曼树、逆序对、组合计数、模周期，考点比单纯的「背概念」深一层；
  3. 完善程序偏工程——行程长度解码是经典字符串处理，「精明与糊涂」考的是把生活化描述抽象成投票算法的能力。

复盘建议：重点重做 第 19 题（改 gcd 递归参数会怎样）、第 24 题（unique 到底有没有用）、第 33 题（LCS 与 LIS 的等价性）——这三题最能把「看懂代码」和「猜答案」区分开。

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