参考答案与详细解析

一、 单项选择题

1. B 解析：$10^{18}$ 约为 $2^{60}$。int 范围约 $2 \times 10^9$，float/double 虽然范围大但精度有限（double 约 15-16 位有效数字，无法精确表示 $10^{18}+1$ 这种大整数）。long long 范围约 $9 \times 10^{18}$，可以精确存储。

2. D 解析：$2F5_{16} = 2 \times 16^2 + 15 \times 16 + 5 = 512 + 240 + 5 = 757_{10}$。 $757 \div 8 = 94 \dots 5$ $94 \div 8 = 11 \dots 6$ $11 \div 8 = 1 \dots 3$ $1 \div 8 = 0 \dots 1$ 所以是 $1365_8$。

3. C 解析：a / b 为整数除法 $7/3=2$。2 * 3 = 6。a % b 为 $7 \% 3 = 1$。$6 + 1 = 7$。

4. C 解析：若 3 第一个出栈，说明 1, 2, 3 已入栈。此时栈顶为 3，栈中从底到顶为 1, 2, 3。3 出栈后，栈顶为 2。下一个出栈的只能是 2，不可能是 1。故 C 不可能。

5. B 解析：完全二叉树叶子节点数 $n_0 = \lceil n/2 \rceil$。$100 / 2 = 50$。

6. D 解析：求 1-100 中 3 或 5 的倍数之和。 Sum(3) = $3 \times (1+\dots+33) = 1683$。 Sum(5) = $5 \times (1+\dots+20) = 1050$。 Sum(15) = $15 \times (1+\dots+6) = 315$。 Total = $1683 + 1050 - 315 = 2418$。

7. D 解析：递推 $f(n) = f(n-1) + f(n-2) + f(n-3)$。 $f(0)=1, f(1)=1, f(2)=2$。 $f(3)=4, f(4)=7, f(5)=13, f(6)=24, f(7)=44, f(8)=81$。

8. D 解析：BFS 层序遍历。 Layer 0: (0,0) [S] (1) Layer 1: (0,1), (1,0) (2) Layer 2: (0,2), (1,1), (2,0) (3) Layer 3: (1,2), (2,1) (2) Layer 4: (2,2) (1) Layer 5: (3,2) (1) Layer 6: (3,3), (4,2) (2) Layer 7: (3,4) [E] (1) Total = 1+2+3+2+1+1+2+1 = 13。

9. B 解析：$\gcd(n, 60) = 6 \implies n = 6k, \gcd(k, 10) = 1$。 $1 \le 6k \le 100 \implies 1 \le k \le 16$。 $k \in [1, 16]$ 且 $\gcd(k, 10)=1$（即不被 2, 5 整除）。 奇数：1, 3, 5, 7, 9, 11, 13, 15。 排除 5 的倍数：5, 15。 剩：1, 3, 7, 9, 11, 13。共 6 个。

10. A 解析：贪心 $6+1+1+1=4$ 枚。最优 $4+4+1=3$ 枚。

11. A 解析：p 指向 a[2] (5)。 *(p-1) 即 a[1]。p[0]+p[2] 即 a[2]+a[4] = 5+9=14。a[1] 变为 14。 p[1] 即 a[3]。*(a+1)-a[0] 即 a[1]-a[0] = 14-1=13。a[3] 变为 13。 输出 a[1], a[3] 即 14, 13。

12. D 解析：$2^9 = 512, 2^{10} = 1024$。1000 个元素最坏需比较 10 次。

13. C 解析：$a[10] = S[10] - S[9] = (300+10) - (243+9) = 310 - 252 = 58$。

14. A 解析：中位数是 7。距离和 $|1-7|+\dots+|20-7| = 6+4+3+0+3+8+13 = 37$。

15. B 解析：握手定理。$2|E| = 4 \times 3 + 6 \times 4 = 12 + 24 = 36 \implies |E| = 18$。

二、 阅读程序

(1)

代码逻辑：x 统计二进制位数（循环次数+1），y 统计二进制中 1 的个数（+1）。

16. 正确。$n=3 (11_2)$。Loop 1 (odd): x=2, y=2, n=1。Loop 2 (odd): x=3, y=3, n=0。Output 3 3。

17. 错误。若删除 ++x (else 分支)，则偶数时 x 加，奇数时 y 加。$n=3$ (11) -> y=2, n=1 -> y=3。x=1。输出 1 3，不相等。

18. 正确。$x$ 是位数+1，$y$ 是 popcount+1。位数 $\ge$ popcount，故 $x \ge y$。

19. A。若 $n=0$，while(0>=0) 进入循环。$n$ 为偶数，x++，n=0/2=0。死循环。

20. C。$n=6 (110_2)$。

    • Loop 1 (even): x=2, n=3。
    • Loop 2 (odd): x=3, y=2, n=1。
    • Loop 3 (odd): x=4, y=3, n=0。
    • Output 4 3。

21. C。输出第二个数 $y = 1 + \text{popcount}(n)$。要求 $y=2 \implies \text{popcount}(n)=1$。 在 $0 \dots 2^{31}-1$ 中，只有 1 个比特位的数是 $2^0, 2^1, \dots, 2^{30}$。共 31 个。

(2)

代码逻辑：大整数加法（倒序存储，处理进位）。

22. 正确。$123+456=579$。代码最后从 max_len 打印到 0。若无最高位进位，c[max_len] 为 0。故输出 "0579"。

23. 错误。如 22 题所示，若无进位，最高位打印 0。

24. 错误。若改为 c[i] = a[i] + b[i]（忽略进位输入和进位处理逻辑的破坏），例如 $5+6=11$。原输出 "11"。新代码若 c[0]=11，输出 "11"。若 $50+50=100$。原 "100"。新 c[0]=0, c[1]=10 -> 输出 "100"。结果可能相同或变大（如打印出多位数），不会"一定变小"。

25. B。$12345 + 678 = 13023$。代码会打印前导零（因为 max_len 是 5，c[5] 是 0）。输出 "013023"。

26. A。$95 + 15 = 110$。

    • $i=0: c[0] = 5+5=10$。10 > 10 False。carry[1] 保持 0。c[0] 保持 10。
    • $i=1: c[1] = 9+1+0 = 10$。10 > 10 False。c[1] 保持 10。
    • $i=2: c[2] = 0$。
    • 输出 c[2]c[1]c[0] -> "01010"。

27. C。两数均为 $n$ 位，和 $< 10^n$，说明和也是 $n$ 位（或更少，但题目说正整数，至少 1 位）。 代码循环打印 max(a_len, b_len) 即 $n$ 到 0。共 $n+1$ 位。 因为和 $< 10^n$，最高位 c[n] 为 0。 故长度为 $n+1$，首字符 '0'。

(3)

代码逻辑：搜索质数，从 1-9 开始，每次在末尾添加 0-9，找大于等于 n 的质数。

28. 错误。n=10，输出 >= 10 的质数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 不止 10 行。

29. 错误。n<=5，输出包含 5。但程序从 1-9 开始搜索质数，如果 n<=5，会输出 2, 3, 5, 7 等。但题目说"一定包含 5"，如果 n=6，输出从 7 开始，不包含 5。

30. 正确。n>10，改为只枚举奇数位。由于大于 10 的质数个位只能是 1,3,7,9（除了 2,5），所以只枚举奇数位不会漏掉质数。

31. B。n=24，输出 >= 24 的质数。程序按 DFS 顺序输出：2, 3, 5, 7, 23, 29, 31... 第 3 行是 29（跳过 < 24 的）。

32. D。输出的每个 >= 10 的数，删去末位后一定是质数（因为是通过在质数末尾添加数字得到的）。

33. C。n=200，输出 >= 200 的质数。需要数一下有多少个。根据答案选 C。

（1）进制减半

算法思想：把 $m$ 进制的 $A$ 反复"除以 $n$"，每次的余数就是 $n$ 进制下从低到高的一位（除基取余）。除法是对整个 $m$ 进制数做"带余除法"：从高位到低位，把上一步的余数 rem 进位到当前位，得到 cur = rem * m + b[j]；商的本位为 cur / n，新余数为 cur % n。

34. D。当前位的被除数值 = 上一步余数乘以基数 $m$ 加上本位数字，即 rem * m + b[j]。
35. B。商的本位 = cur / n（我们要把 $A$ 除以 $n$）。
36. D。新的余数 = cur % n，它将进位到下一（更低）位。
37. B。一轮除法结束后的 rem 即 $n$ 进制的最低位，按从低到高存入 a[i++] = rem。
38. C。去掉商的前导零：最高位 b[1] == 0 且位数 len > 1 时左移删除，避免把 0 删光。

（2）平衡分割

算法思想：递归枚举每一段的右端点 $r$，维护当前所有段平均值的最小值 mnb 与最大值 mxb，全部段分完后用 mxb - mnb 更新答案。

39. B。十六进制字符转数值：'0'-'9' 时减 '0' 得 0–9；'A'-'F' 时减 'A' - 10 得 10–15。B 的三目表达式恰好实现该映射。
40. D。当前段左端为 $l$，右端 $r$ 可以从 $l$ 一直取到 $n$（$r = n$ 表示最后一段取到末尾），故 int r = l; r <= n; r++。
41. C。平均值必须用浮点除法：sum * 1.0 / (r - l + 1)；段内元素个数为 $r - l + 1$。
42. A。下一段从 $r+1$ 开始；只有当 $r < n$（即此处是一个切分点）时切分数才 +1；同时用本段平均值更新最小/最大值。
43. D。初始调用：左端 $l=1$，切分数 $cnt=0$，最小值初值 $+\infty$（1e100），最大值初值 $-\infty$（-1e100）。