参考答案与详细解析

一、 单项选择题

1. B。 解析：

   • 数字部分：前 4 位是数字（0-9），其中奇数有 5 个（1,3,5,7,9），偶数有 5 个（0,2,4,6,8）。
     • 题目要求“恰好有 2 个数字为奇数”。
     • 从 4 个位置中选 2 个放奇数：$C_4^2 = 6$ 种。
     • 这 2 个位置填奇数：$5 \times 5 = 25$ 种。
     • 剩下 2 个位置填偶数：$5 \times 5 = 25$ 种。
     • 数字部分总方案数：$6 \times 25 \times 25 = 3750$。
   • 字母部分：后 2 位是大写字母（A-Z），排除 I, O，剩 24 个字母。可重复。
     • 方案数：$24 \times 24 = 576$。
   • 总方案数：$3750 \times 576 = 2,160,000$。

2. B。 解析：归并排序将区间 $[left, right]$ 分为 $[left, mid]$ 和 $[mid+1, right]$。第一行递归处理了左半部分，第二行应处理右半部分，即 merge_sort(a, mid + 1, right)。

3. A。 解析：

   • 总人数 15（8男7女）。
   • 先选 2 名宣传委员（无区别，至少 1 女）：
     • 总选法 $C_{15}^2 = 105$。
     • 全男选法 $C_8^2 = 28$。
     • 合法选法 $105 - 28 = 77$。
   • 剩余 13 人，选队长和副队长（有区别）：
     • $P_{13}^2 = 13 \times 12 = 156$。
   • 总选法：$77 \times 156 = 12012$。

4. C。 解析：

   • 通项公式 $T_{r+1} = C_8^r (2x)^{8-r} (-y)^r$。
   • 我们需要 $x^5 y^3$，即 $8-r=5 \Rightarrow r=3$。
   • 系数为 $C_8^3 \cdot 2^5 \cdot (-1)^3 = 56 \cdot 32 \cdot (-1) = -1792$。

5. B。 解析：Dijkstra 算法的松弛操作。如果通过 $u$ 到达 $j$ 的距离 dis[u] + graph[u][j] 小于当前记录的 dis[j]，则更新。即 if (dis[j] > dis[u] + graph[u][j])。

6. C。 解析：LCS 动态规划。当字符不相等时，$dp[i][j]$ 继承自上方或左方的最大值，即 max(dp[i-1][j], dp[i][j-1])。

7. B。 解析：两点间距离公式 $\sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$。C++ 中平方用 pow(x, 2) 或 x*x，开方用 sqrt。选项 B 正确。选项 A 中 ^ 是异或运算。

8. B。 解析：int &b = a 声明 b 为 a 的引用（别名）。修改 b 即修改 a。b=20 后 a 变为 20。

9. C。 解析：

   • 外层循环 $i$ 从 1 到 $n$。
   • 内层循环 $j$ 满足 $j^2 \le i$，即 $j \le \sqrt{i}$。
   • 总次数 $\sum_{i=1}^n \sqrt{i} \approx \int_0^n \sqrt{x} dx = O(n^{1.5}) = O(n\sqrt{n})$。

10. C。 解析：线性筛（欧拉筛）的核心。当 i 是 primes[j] 的倍数时（i % primes[j] == 0），说明 primes[j] 是 i 的最小质因子。此时 i * primes[j] 的最小质因子也是 primes[j]。如果继续枚举更大的质数，会导致合数被非最小质因子筛去，破坏线性复杂度，因此必须 break。

11. C。 解析：

    • A 错：派生类不能直接访问基类 private。
    • B 错：私有继承下，基类 protected 在派生类中变 private。
    • C 对：构造顺序：基类 -> 派生类。
    • D 错：析构顺序：派生类 -> 基类。

12. B。 解析：

    • $f(1)=1, f(2)=2, f(3)=3$。
    • $f(4) = f(3)+f(2)+2f(1) = 3+2+2 = 7$。
    • $f(5) = f(4)+f(3)+2f(2) = 7+3+4 = 14$。
    • $f(6) = f(5)+f(4)+2f(3) = 14+7+6 = 27$。

13. A。 解析：

    • 考虑 000 到 999 的 3 位字符串（排除 000）。
    • 恰好一个 '5'。
    • 位置选择：3 种（百、十、个位）。
    • 该位置填 5：1 种。
    • 其余两位置填非 5 数字（0-9 除 5）：$9 \times 9 = 81$ 种。
    • 总数：$3 \times 81 = 243$。
    • 000 不含 5，不在计数内，故 1-999 范围内结果准确。

14. C。 解析：

    • 代码逻辑 x -= x & -x 是清除二进制最低位的 1。ans++ 计数。
    • 该程序计算 $x$ 的二进制表示中 1 的个数（Popcount）。
    • $2023 = 11111100111_2$。
    • 数一下 1 的个数：6 个 1 (111111) + 3 个 1 (111) = 9 个。

15. B。 解析：Kruskal 算法构建最小生成树。如果边 $(u, v)$ 的两个端点已经在同一个连通块中，说明加入这条边会形成环。根据 MST 性质，应舍弃这条边。

二、 判断题

16. A (正确)。这是加法原理的定义。
17. A (正确)。C++ 引用必须在定义时初始化，且之后不能重新绑定到其他变量。
18. A (正确)。快排平均 $O(n \log n)$，不稳定；归并稳定。
19. A (正确)。sqrt 函数返回 double 类型。
20. A (正确)。杨辉三角第 $n$ 行对应 $(a+b)^n$ 的系数，令 $a=b=1$ 即得和为 $2^n$。
21. A (正确)。堆优化 Dijkstra 复杂度为 $O(E \log V)$。在稠密图中 $E \approx V^2$，复杂度约为 $O(V^2 \log V)$，比朴素算法 $O(V^2)$ 慢。
22. B (错误)。出栈序列数对应卡特兰数，集合划分对应贝尔数，两者不相等。
23. B (错误)。快速排序最坏时间复杂度是 $O(n^2)$。随机化可以避免绝大多数退化情况，使期望复杂度为 $O(n \log n)$，但不能从逻辑上“完全避免”（例如随机数生成器一直选到极值）。且题目第一句“最坏情况...为 $O(n \log n)$”本身就是错的。
24. B (错误)。析构函数不能重载，一个类只能有一个析构函数。
25. B (错误)。滚动数组优化空间时，会覆盖掉之前的状态，导致无法回溯路径，因此只能求长度，不能还原序列。