2025 CSP-J 答案解析（仅供参考）

~~感谢伟大的DeepSeek~~
~~试卷试卷试卷~~

一、单项选择题

1. 答案：A

解析：32 位无符号整数最大值为 $2^{32}$ −1 ≈ 4.29× $10^9$ ，最接近 $4\times10^9$ 。

2. 答案：B

解析：255 的二进制为11111111，254的二进制为11111110，执行&运算后变为 11111110，即 254。

3. 答案：B

解析：递归计算 calc(5)：

calc(5) → calc(4) + calc(3)
calc(4) → calc(2) + 1 → calc(1) + 1 + 1 = 3
calc(3) → calc(2) + calc(1) → 2 + 1 = 3
总和：3 + 3 = 6

4. 答案：B

解析：构造哈夫曼树，带权路径长度计算如下：

合并 10 和 12 → 22
合并 15 和 20 → 35
合并 22 和 25 → 47
合并 35 和 47 → 82
最终合并结果如下：

     82
    /   \
  35     47
 /  \    / \
15   20  22  25
         /  \
        10  12

路径长度(WPL)计算：10×3 + 12×3 + 15×2 + 20×2 + 25×2 = 186

5. 答案：B

解析：有向图中所有顶点的入度之和等于出度之和，且等于边数。

6. 答案：C

解析：

总选法： $C_9^4 = 126$ ，减去全男 $C_5^4 = 5$ 和全女 $C_4^4 = 1$ ，得 $126 - 5 - 1 = 120$

7. 答案：C

解析：原式：(a && b) || (!c && a)

设b为false，c为true，a为true，原式结果为false;
C 选项a && (!b || c) 与结果为true，与原式不符。

8. 答案：D

解析：

步骤1：计算序列前几项（模7）：

f(0) = 1
f(1) = 1
f(2) = (f(1) + f(0)) mod 7 = (1+1) = 2
f(3) = (f(2) + f(1)) mod 7 = (2+1) = 3
f(4) = (f(3) + f(2)) mod 7 = (3+2) = 5
f(5) = (f(4) + f(3)) mod 7 = (5+3) = 8 ≡ 1
f(6) = (f(5) + f(4)) mod 7 = (1+5) = 6
f(7) = (f(6) + f(5)) mod 7 = (6+1) = 7 ≡ 0
f(8) = (f(7) + f(6)) mod 7 = (0+6) = 6
f(9) = (f(8) + f(7)) mod 7 = (6+0) = 6
f(10) = (f(9) + f(8)) mod 7 = (6+6) = 12 ≡ 5
f(11) = (f(10) + f(9)) mod 7 = (5+6) = 11 ≡ 4
f(12) = (f(11) + f(10)) mod 7 = (4+5) = 9 ≡ 2
f(13) = (f(12) + f(11)) mod 7 = (2+4) = 6
f(14) = (f(13) + f(12)) mod 7 = (6+2) = 8 ≡ 1
f(15) = (f(14) + f(13)) mod 7 = (1+6) = 7 ≡ 0
f(16) = (f(15) + f(14)) mod 7 = (0+1) = 1
f(17) = (f(16) + f(15)) mod 7 = (1+0) = 1`

此时f(16)=1, f(17)=1，与f(0)、f(1)相同，因此序列从n=0开始周期为16（即周期T=16）。

步骤2：求f(2025)：
计算2025除以16的余数：
2025 ÷ 16 = 126 * 16 = 2016，余数2025 - 2016 = 9。
因此f(2025) = f(9) = 6。

9. 答案：B

解析：C++ 中 string 对象可以使用 + 连接 string 和 char。

10. 答案：C

解析：函数 solve 使用引用传递 a因此运行结果会直接影响到x的值，但 b 是值传递，因此运行结果不会影响y的值，solve运行结束后，a的值为10，直接影响到x上，因此x变成10，y不变。

11. 答案：B

解析：从 (1,1) 到 (4,5) 需向右走 3 步，向下走 4 步，路径数为 $C_7^3$ =35，也可以通过网格路径方式模拟。

12. 答案：B

解析：该数列中存在6个逆序对，因此需要交换的次数为6 次（也可模拟过程求证）。

13. 答案：A

解析：
$720 _{ 10}$ = $1011010000_2$
$270_8$ = $10111000_2$ (3位一体： $2_8$ -> $10_2$ ， $7_8$ -> $111_2$ ， $0_8$ -> $000 _2$ )
求和得： $1011010000_2$ + $10111000_2$ = $1110001000_2$
结果转16进制：4位1体
$11_2$ -> $3 _{16}$
$1000_2$ -> $8_{16}$
$1000_2$ -> $8_{16}$
即： $388_{16}$

14. 答案：C

解析：

题目：一棵包含 1000 个结点的完全二叉树，其叶子结点的数量是多少？

完全二叉树的性质：

叶子结点只能出现在最下层和次下层。
最下层的叶子结点都集中在该层最左边的若干位置。
对于具有 n 个结点的完全二叉树，叶子结点数 = n - ⌊n/2⌋。

推导：

设叶子结点数为 L，度为 1 的结点数为 $N_1$ ，度为 2 的结点数为` $N_2$ 。
总结点数 n = L + $N_1$ + $N_2$ 。
在二叉树中，边数 = n - 1 = N1 + 2* $N_2$ 。
联立得：L + $N_1$ + $N_2$ - 1 = $N_1$ + 2* $N_2$ ⇒ L = $N_2$ + 1。
对于完全二叉树，N_1只能为 0 或 1：
- 当 n 为偶数时， $N_1$ = 1（因为 n = L + $N_1$ + $N_2$ = ( $N_2$ +1) + $N_1$ + $N_2$ = 2 $N_2$ + $N_1$ + 1，n为偶数则 $N_1$ =1）。
- 当 n 为奇数时， $N_1$ = 0。

本题 n=1000（偶数），所以 $N_1$ =1。
则 L = $N_2$ + 1。
又 n = L + $N_1$ + $N_2$ = ( $N_2$ +1) + 1 + $N_2$ = 2 $N_2$ + 2 = 1000。
解得：2 $N_2$ = 998 ⇒ $N_2$ = 499。
因此 L = 499 + 1 = 500。

或者直接利用公式：叶子结点数 L = ⌈n/2⌉ = ⌈1000/2⌉ = 500。

答案：500

15. 答案：A

解析：模拟过程：

7（奇）→ 压栈 S：[7]
5（奇）→ 压栈 S：[7,5]
8（偶，栈非空）→ 弹出 5 加入 P：[5]
3（奇）→ 压栈 S：[7,3]
1（奇）→ 压栈 S：[7,3,1]
4（偶，栈非空）→ 弹出 1 加入 P：[5,1]
2（偶，栈非空）→ 弹出 3 加入 P：[5,1,3]
最终 P：5,1,3

二、阅读程序

(1) 程序分析

这个程序的作用是：计算在1到n的范围内，有多少个三元组(i, j, k)满足：

i < j < k（因为循环中i从1到n，j从i+1到n，k从j+1到n）
两两互质（即gcd(i,j)=1, gcd(j,k)=1, gcd(i,k)=1）

简单来说： 程序统计了1到n中所有两两互质的三元组的数量。

16. √
输入为 2 时，第三层循环 k 从 j+1=3 开始，但 n=2，不执行。

17. ×
删去 gcd(i,k)==1 会影响结果，因为三对互质（两两互质）必须全部满足。

18. √
当 n≥3 时，至少存在一组互质三元组，输出正整数。

19. B
修正：本题官方答案是直接给分
修改后，gcd函数错误（总是返回第一个参数a，而不是真正的gcd），导致一些原本互质的三元组被误判为不互质，因此计数减少，输出答案小于原答案。

20. D
8以内互质的三元组有：
1 2 3、1 2 5、1 2 7、1 3 4、1 3 5、1 3 7、1 3 8、1 4 5、1 4 7、1 5 6
1 5 7、1 5 8、1 6 7、1 7 8、2 3 5、2 3 7、2 5 7、3 4 5、3 4 7、3 5 7
3 5 8、3 7 8、4 5 7、5 6 7、5 7 8
共25组。

21. A
gcd(36,42) 计算36和42的最大公约数，结果为6

(2) 程序分析

该程序的作用是：给定一个整数数组，先对数组进行去重和排序，然后计算在满足任意两个相邻元素之差不超过k的条件下，最少可以将数组划分成多少个连续子序列（或者说，最少需要多少个这样的子序列来覆盖所有元素）。

22. √
输入为 3 1 3 2 1，去重后为[1,2,3]，k=1，输出为 2。

23. √
答案一定在 [1, n]范围内。

24. ×
删去去重操作后，重复元素不会影响结果。

25. B
执行第 18 行时，a[i] - a[j+1] <= k，所以 a[i] - a[j] > k 不一定成立。

26. A
输入为 1~100，k=2，输出为 34（分组最多间隔为 2）。

27. B
根据程序的作用描述，程序中不排序的话，a数组可能会出现乱序或者降序的情况，那么按照连续的前提下，计算出的子序列结果只会更少。

(3) 程序分析

这段程序的作用是：计算两个序列a和b的最长公共子序列（LCS）的长度。
28. √
输入为 4 1 2 3 4 1 3 2 2

两个序列序列长度为4：
a序列：1 2 3 4
b序列：1 3 2 2
最长公共子序列为 2。

29. √
f[i][j]是推导过程中的中间状态
f[n][n]表示两个序列a和b的最长公共子序列（LCS）的长度的最终结果
因此：f[i][j] <= f[n][n]

30. ×
删去第 18 行会影响动态规划状态转移。

31. D
答案满足最大为n，最小为0，选项均满足。

32. A
若原本数组有序，则不变，原本数组无序，则会变大。

33（~~官方试题好像删去了）~~

三、完善程序

(1) 字符串解码

33. C
①处应填 i + 1 < z.length()，用于检查下一个字符是否在合法范围内。

34. B
②处应填 count * 10 + (z[i] - '0')，用于将连续数字字符拼接成一个数字，相每次整体乘10，新数字补上个位。

35. B
③处应填 count，表示重复次数，要将count个字符拼接到字符串s中。

36. B
④处应填 ch，表示没有后续数字，拼接当前字符。

37. C
⑤处应填 i++，移动到下一个字符。

(2) 精明与糊涂

38. B
这里初始化count，对于候选人0，初始count应该表示“支持”或“信任”的程度。在投票算法中，通常初始count=1（因为自己支持自己）。

39. C

当当前count为0时，说明当前candidate不可能是名人，需要更换候选人。

40. D

query(i, candidate) == false，表示 i 认为 candidate 是糊涂的。
query(candidate, i) == false，表示candidate 认为i 是糊涂的。
有一方被认为是糊涂的

41. A

当③条件满足时，应该减少count。

42. C
⑤处应填 candidate，输出最终确定的精明人编号。

如果觉得文章对你有用，请随意赞赏