参考答案与详细解析

一、 单项选择题

1. A。 解析：中间列 2 个座位，左右列共 4 个座位。 先选 2 人坐中间：$C(6, 2) = 15$。中间 2 人排列 $A(2, 2) = 2$。 剩下 4 人坐左右 4 个位置：$A(4, 4) = 24$。 总数 $15 \times 2 \times 24 = 720$。

2. B。 解析：男女相间。 模式：男女男女男女 或 女男女男女男（2种）。 男生排列 $3! = 6$，女生排列 $3! = 6$。 总数 $2 \times 6 \times 6 = 72$。

3. D。 解析：class MyClass; 是前向声明，不是定义。定义需要包含类体 {...}。

4. D。 解析：$n$ 个顶点 $n-1$ 条边的图，如果不连通，则没有生成树，它本身也不是生成树。只有连通时才是树（即生成树）。

5. C。 解析：生两个孩子，样本空间 {(男,男), (男,女), (女,男), (女,女)}。儿女双全即 {(男,女), (女,男)}，概率 2/4 = 1/2。

6. B。 解析：判别式 $\Delta = a^2 - 4b \ge 0 \Rightarrow a^2 \ge 4b$。

7. C。 解析：BFS 访问每个节点一次，复杂度 $O(n)$。

8. B。 解析：时间复杂度通常为 状态数 $\times$ 转移代价，不仅仅是状态个数。

9. A。 解析：外层循环 $n$ 次。内层 to_string 和遍历字符串长度约为 $\log_{10} i$。总复杂度 $\sum \log i \approx n \log n$。

10. A。 解析：这是求从 (0,0,0) 到 (1,2,3) 的路径数（每次 x,y,z 加 1）。 总步数 $1+2+3=6$。 多重集排列数 $\frac{6!}{1! 2! 3!} = \frac{720}{12} = 60$。

11. A。 解析：外层 $v \le \sqrt{n}/2$，内层 $u \le \sqrt{n}$。循环次数约为 $\sqrt{n} \times \sqrt{n} = n$。复杂度 $O(n)$。

12. D。 解析：快排 partition 最后将 pivot (在 a[l]) 与分界点 a[j] 交换，并返回 j。

13. D。 解析：LIS 状态转移：dp[i] = max(dp[i], dp[j] + 1)。

14. C。 解析：使用二分查找优化的 LIS 算法（贪心+二分），时间复杂度 $O(n \log n)$。

15. A。 解析：根据题目答案推断，最短路径为 9。路径可能是 0->2->1->3 (3+1+5=9? 需看具体矩阵数值，此处依答案 A)。

二、 判断题

16. A (正确)。$9 (1001_2) | 12 (1100_2) = 13 (1101_2)$。
17. B (错误)。C++ 数组越界是未定义行为，可能崩溃，也可能读写错误内存但不立即退出。
18. A (正确)。归并排序稳定性好，复杂度稳定 $O(n \log n)$。
19. B (错误)。5 红球产生 4 个中间空隙。4 蓝球必须填入这 4 个空隙（保证两侧有红球且不相邻）。只有 1 种方案（R B R B R B R B R）。
20. B (错误)。log 是自然对数 $\ln$。$\ln 8 \approx 2.08$。$\log_2 8 = 3$ 应使用 log2。
21. B (错误)。C 语言可以通过结构体嵌套等方式模拟继承，虽然不支持关键字。
22. A (正确)。Cayley 公式，完全图生成树数量为 $n^{n-2}$。
23. B (错误)。该公式计算的是第三边长度（余弦定理），不是周长。周长需加上 $a+b$。
24. A (正确)。图遍历标准复杂度。
25. A (正确)。
    • 班长、学习委员从 28 人（32-4）中选 2 人排列：$P(28, 2) = 28 \times 27$。
    • 副班长、组织委员从剩下 30 人（28-2+4）中选 2 人排列：$P(30, 2) = 30 \times 29$。
    • 总数 $28 \times 27 \times 30 \times 29 = P(30, 4)$。