参考答案与详细解析

一、 单项选择题

1. B。 解析：sqrt(50) 约为 7.07，log2(8) 为 3。和为 10.07。强制转换为 int 后截断为 10。

2. A。 解析： A. sqrt 返回 double，可以参与浮点运算。正确。 B. log2 返回 double。 C. pow 返回 double。 D. sin 参数为弧度制。

3. C。 解析： A. 值传递不共享内存。 B. 值传递修改形参不影响实参。 C. 引用传递本质是别名，修改形参会修改实参。正确。 D. 指针传递可以通过解引用修改实参指向的数据。

4. D。 解析： 权重：3, 4, 7, 8, 9。

   1. 合并 3, 4 -> 7。新集合：7, 7, 8, 9。
   2. 合并 7, 7 -> 14。新集合：8, 9, 14。
   3. 合并 8, 9 -> 17。新集合：14, 17。
   4. 合并 14, 17 -> 31。 WPL = 所有非叶子节点权值之和 = 7 + 14 + 17 + 31 = 69。 或者计算路径长度： 3 (深度3), 4 (深度3), 7 (深度2), 8 (深度2), 9 (深度2)。 WPL = $3\times3 + 4\times3 + 7\times2 + 8\times2 + 9\times2 = 9 + 12 + 14 + 16 + 18 = 69$。

5. C。 解析：到达 (i, j) 只能从上方 (i-1, j) 或左方 (i, j-1) 过来。取最大值加上当前点的值。即 dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1])。

6. C。 解析：这是经典的“打家劫舍”问题模型（不相邻最大和）。 $f[0] = 0$ $f[1] = 2$ (题目给定，虽然公式算出来也是 max(0, 0+2)=2) $f[2] = \max(f[1], f[0] + a[2]) = \max(2, 0+7) = 7$ $f[3] = \max(f[2], f[1] + a[3]) = \max(7, 2+9) = 11$ $f[4] = \max(f[3], f[2] + a[4]) = \max(11, 7+3) = 11$ $f[5] = \max(f[4], f[3] + a[5]) = \max(11, 11+1) = 12$

7. D。 解析：0/1 背包一维数组优化，必须逆序遍历容量。状态转移方程为 dp[c] = max(dp[c], dp[c - w[i]] + v[i])。

8. A。 解析：代码通过 DFS 遍历连通块，标记访问过的点 vis，这是典型的泛洪算法（Flood Fill）或连通块搜索。

9. A。 解析： A. 冒泡排序只交换相邻逆序对，相等元素不会交换，是稳定的。正确。 B. 选择排序可能会把后面的元素交换到前面，不稳定。 C. 快速排序分区时可能会改变相等元素顺序，不稳定。 D. 稳定排序的定义是不改变相等元素的相对顺序。

10. C。 解析：

    • 初始队列：[1]
    • 弹出 1，邻居 2, 3 入队。队列：[2, 3]
    • 弹出 2，邻居 1(已访), 4 入队。队列：[3, 4]
    • 此时 4 第一次入队。队列内容为 3, 4。

11. D。 解析：表长 11。

    • 22 % 11 = 0 -> 放 0
    • 33 % 11 = 0 -> 冲突，放 1
    • 4 % 11 = 4 -> 放 4
    • 15 % 11 = 4 -> 冲突，放 5
    • 26 % 11 = 4 -> 冲突，5被占，放 6。

12. B。 解析： A. 线性探测会找下一个空位。 B. 链地址法（拉链法）用链表/桶存储冲突元素。正确。 C. 即使表长是素数，哈希值相同仍会冲突。 D. 开放定址法查找时必须处理冲突路径。

13. B。 解析：枚举 $n$ 次，每次二分查找 $O(\log n)$。总复杂度 $O(n \log n)$。

14. B。 解析：a[mid] < x，说明 mid 及其左边的数都小于 $x$，不可能满足“大于等于 $x$”。所以目标在右边，左边界 left 变为 mid + 1。

15. D。 解析：动态规划计数。

    • (0,0)~(0,4): 1, 1, 1, 1, 1
    • (1,0): 1. (1,1): 0(障碍). (1,2): 1(来自上). (1,3): 0(障碍). (1,4): 1(来自上).
    • (2,0): 1. (2,1): 1(来自左). (2,2): 2. (2,3): 2. (2,4): 3.
    • (3,0): 0(障碍). (3,1): 1(来自上). (3,2): 0(障碍). (3,3): 2(来自上). (3,4): 5.
    • (4,0): 0. (4,1): 1. (4,2): 1. (4,3): 3. (4,4): 8. 最终结果 8。

二、 判断题

16. B (错误)。C++ 数学库三角函数使用弧度制。
17. B (错误)。pow 返回 double 类型。
18. B (错误)。0/1 背包必须从大到小枚举容量，从小到大是完全背包。
19. A (正确)。哈希冲突是不可避免的（ pigeonhole principle），只能减少。
20. B (错误)。DFS 的访问顺序严重依赖于邻接点的遍历顺序（例如是从左到右还是从右到左）。
21. A (正确)。递归深度过大确实会导致栈溢出（Stack Overflow）。
22. A (正确)。哈夫曼树是正则二叉树（Strict Binary Tree），只有度为 0 和 2 的节点。
23. B (错误)。选择排序是不稳定的。
24. A (正确)。BFS 的性质：第一次访问到某点时的层数即为最短路径长度（边权为1时）。
25. A (正确)。DP 的核心原则：计算当前状态前，依赖的子状态必须已计算完毕。