参考答案与详细解析

一、 单项选择题

1. B。 解析：总选法 $C_{12}^4 = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = 495$。 全选算法书：$C_7^4 = 35$。 全选数学书：$C_5^4 = 5$。 符合要求的选法 = 总选法 - 全选算法 - 全选数学 = $495 - 35 - 5 = 455$。

2. B。 解析：使用插空法或排除法。 排除法：6 人全排列 $A_6^6 = 720$。甲乙相邻（捆绑法）视为 1 个元素，与其余 4 人排列 $A_5^5 \times 2 = 120 \times 2 = 240$。 不相邻排法 = $720 - 240 = 480$。

3. C。 解析：二项式通项 $T_{r+1} = C_6^r (x^2)^{6-r} (-x^{-1})^r = C_6^r (-1)^r x^{12-3r}$。 令 $12-3r=0 \Rightarrow r=4$。 系数为 $C_6^4 (-1)^4 = C_6^2 = 15$。

4. A。 解析：这是杨辉三角（组合数）的递推公式：$C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$。对应代码 c[i][j] = c[i-1][j-1] + c[i-1][j]。

5. C。 解析：计算 $3^{20} \pmod{17}$。 根据费马小定理，$3^{16} \equiv 1 \pmod{17}$。 $3^{20} = 3^{16} \cdot 3^4 \equiv 1 \cdot 81 \equiv 81 \pmod{17}$。 $81 = 17 \times 4 + 13$，故余数为 13。

6. D。 解析：归并排序的时间复杂度递归式为 $T(n) = 2T(n/2) + O(n)$，解得 $T(n) = O(n \log n)$。

7. A。 解析：利用向量叉乘或鞋带公式。 $\vec{AB} = (4, 1)$, $\vec{AC} = (2, 5)$。 面积 $S = \frac{1}{2} |x_1 y_2 - x_2 y_1| = \frac{1}{2} |4 \times 5 - 1 \times 2| = \frac{1}{2} |20 - 2| = 9$。

8. A。 解析：圆心在原点，半径为 $r$ 的圆方程为 $x^2 + y^2 \le r^2$。这里 $r=5$，即 $x^2 + y^2 \le 25$。

9. D。 解析：使用 Kruskal 算法。 边按权值排序：$(2,3,1), (1,3,2), (4,5,2), (1,2,4), (2,4,5), (3,4,8), (3,5,10)$。

   1. 选 $(2,3)$，权值 1。
   2. 选 $(1,3)$，权值 2。
   3. 选 $(4,5)$，权值 2。
   4. 选 $(1,2)$，1 和 2 已连通（通过 3），跳过。
   5. 选 $(2,4)$，连接两个连通块，权值 5。 此时所有点连通。总权值 $1+2+2+5=10$。

10. A。 解析：Dijkstra 算法。

    • $dist[1]=0$
    • 更新邻居：$dist[2]=3, dist[3]=10$。
    • 选 $2$ (最小)，更新邻居：$dist[4] = dist[2]+4=7, dist[3] = \min(10, 3+2)=5$。
    • 选 $3$ (最小，值为5)，更新邻居：$dist[4] = \min(7, 5+1)=6$。
    • 选 $4$ (值为6)。 最短距离为 6。路径 $1 \to 2 \to 3 \to 4$。

11. C。 解析：外层循环 $i$ 从 1 到 $n$，执行 $n$ 次。内层循环 $j$ 满足 $j^2 \le n$，即 $j \le \sqrt{n}$，执行 $\sqrt{n}$ 次。总复杂度 $O(n \sqrt{n})$。

12. B。 解析：二分答案需要进行 $\log_2 M$ 次判定，每次判定耗时 $O(n)$，总复杂度 $O(n \log M)$。

13. B。 解析：这是线性筛（欧拉筛）的核心。当 i % p == 0 时，说明 $p$ 是 $i$ 的最小质因子。此时 $i \times p$ 的最小质因子是 $p$。如果继续枚举更大的质数 $p'$，则 $i \times p'$ 的最小质因子仍然是 $p$（因为 $i$ 含有因子 $p$），这会导致 $i \times p'$ 被非最小质因子筛去，破坏线性复杂度。因此必须 break，保证每个合数只被其最小质因子筛去。

14. C。 解析： A 错：派生类不能直接访问基类 private 成员。 B 错：私有继承下，基类 protected 成员在派生类中变为 private。 C 对：构造顺序是先基类后派生类。 D 错：析构顺序是先派生类后基类。

15. D。 解析： A: 进1出1, 进2出2... 可行。 B: 进1, 进2, 出2, 出1, 进3, 进4, 出4, 出3. 可行。 C: 进1, 进2, 进3, 出3, 出2, 出1, 进4, 出4. 可行。 D: 要第一个出 3，必须进 1, 2, 3。此时栈内从底到顶为 1, 2, 3。出 3 后，栈顶是 2。下一个出的必须是 2，不可能是 1。故 D 不可能。

二、 判断题

16. A (正确)。这是加法原理的定义。
17. A (正确)。这是圆排列的公式。$n$ 个不同元素围成一圈，旋转相同视为一种，方案数为 $(n-1)!$。
18. B (错误)。可重复组合（多重集组合）的公式是 $C(n+k-1, k)$，而不是 $C(n+k, k)$。
19. B (错误)。杨辉三角递推公式为 $C(n, k) = C(n-1, k-1) + C(n-1, k)$。
20. A (正确)。快速幂利用二进制拆分，将乘法次数从 $b$ 降为 $\log b$。
21. B (错误)。Dijkstra 算法基于贪心策略，要求边权非负。如果存在负权边，即使没有负环，Dijkstra 也可能得出错误结果（因为一旦节点被标记为“已处理”，其距离不再更新，但负权边可能导致后续发现更短路径）。
22. A (正确)。如果所有边权不同，Kruskal 或 Prim 算法在每一步的选择都是唯一的，因此 MST 唯一。
23. A (正确)。比较距离平方可以避免开方运算带来的浮点误差和性能损耗。
24. B (错误)。二分答案的前提是答案具有单调性（或三段性，如求极值）。如果 check(x) 没有单调性，二分法无法保证收敛到最优解。
25. A (正确)。归并排序在合并时，若遇到相等元素，优先取前一个序列的，从而保证稳定性。时间复杂度稳定为 $O(n \log n)$。