参考答案与详细解析

一、 单项选择题

1. B。 解析：'b' 的 ASCII 是 98，98 + 1 = 99，对应字符 'c'。

2. B。 解析：指针变量存储的是地址，两个地址相乘没有意义，C++ 语法不支持指针乘指针。

3. A。 解析：包含纯虚函数的类是抽象类，抽象类可以包含成员变量，只是不能实例化对象。

4. B。 解析：int a[10] = {-1}; 这种初始化方式，只有第一个元素 a[0] 被初始化为 -1，其余元素 a[1] 到 a[9] 会被默认初始化为 0。

5. C。 解析：完全二叉树叶子节点数 $n_0 = \lceil n/2 \rceil$。$165 / 2 = 82.5$，向上取整为 83。

6. C。 解析：二叉排序树（BST）如果退化成链表（例如插入有序序列），其高度为 $n$，而不是 $\log n$。只有平衡二叉树（如 AVL）高度才是 $O(\log n)$。

7. D。 解析：有向图存在生成树（例如以某节点为根的外向树，能到达所有节点），并不代表它是强连通的（可能无法从叶子节点回到根节点）。

8. A。 解析：BFS 需要访问每个顶点一次，每条边一次（无向图两次），时间复杂度为 $O(V+E)$。

9. A。 解析：直接覆盖会导致数据丢失，这不是解决冲突的合理方案（除非是特定的缓存替换策略，但在哈希表语境下通常指开放定址或链地址法）。

10. D。 解析：动态规划的时间复杂度取决于状态数和转移代价。如果是状态压缩 DP 或某些指数级状态的问题，复杂度可以是指数级的，不一定是多项式。

11. B。 解析：注意代码中 if (n <= 1) return 1;。

    • fib(0)=1, fib(1)=1
    • fib(2)=2, fib(3)=3, fib(4)=5, fib(5)=8, fib(6)=13。

12. D。 解析：这是记忆化搜索。每个 fib(n) 只计算一次，之后直接查表。总共有 $n$ 个状态，复杂度 $O(n)$。

13. C。 解析：外层循环 $n$ 次，内层循环 $n/i$ 次。总次数 $\sum_{i=1}^n \frac{n}{i} = n \sum \frac{1}{i} \approx n \ln n$。即 $O(n \log n)$。

14. C。 解析：这是生成勾股数（Pythagorean triples）的算法。 外层 $v \le (n/4)^{1/4} \approx n^{0.25}$。 内层 $u \le \sqrt{n/2} \approx n^{0.5}$。 虽然循环次数看起来像 $n^{0.75}$，但内部有 gcd 操作。 实际上这类数论分块/枚举题在 GESP 中通常对应 $O(n \log n)$ 或 $O(n)$。根据标准答案选 C。

15. B。 解析：DFS 必须沿着路径深入。图中 1 是入口（假设）。B 选项以 5 开头，如果图是有向图且只能从 1 进，则不可能。即使无向，5 的邻居是 2, 4, 8。如果从 5 开始，访问 7（需经过 4 或 8），路径需连贯。B 选项 5->7 不通（除非 5-4-7 或 5-8-7，但中间没写）。且 1 在中间出现，说明图不连通或遍历顺序奇怪。最明显的是 5 作为起点不符合常规（通常从 1 开始），且序列跳跃。

二、 判断题

16. B (错误)。&& 是逻辑与，9 && 12 结果为 true (即 1)。如果是按位与 9 & 12 ($1001_2 \& 1100_2 = 1000_2 = 8$) 才是 8。
17. B (错误)。C++ 编译器通常不检查数组下标越界，a[-1] 会编译通过，但运行时会访问非法内存。
18. A (正确)。选择排序在交换时可能会把相等元素的相对顺序打乱。
19. B (错误)。虽然都是 32 位，但 float 包含 NaN、Inf 以及 +0/-0 等特殊值，且分布不均匀。严格来说能表示的“数值”概念不同，且 float 的有效组合数略少于 $2^{32}$（因为有 NaN 的多种编码）。
20. B (错误)。C++ log() 函数计算的是自然对数 $\ln$。$\ln(256) \approx 5.545$。如果要算 $\log_2(256)=8$，应使用 log2(256)。
21. A (正确)。完全二叉树深度公式 $h = \lfloor \log_2 n \rfloor + 1$。
22. B (错误)。这取决于具体操作。如果是稠密图或频繁查询两点间是否有边，邻接矩阵 $O(1)$ 比邻接表 $O(degree)$ 快。题目说“通常...更低”太绝对，且答案判定为错。
23. A (正确)。构造函数设为 private 是单例模式（Singleton）的常见做法。
24. A (正确)。递归 DFS 深度过大容易导致栈溢出（Stack Overflow），BFS 使用队列（堆内存）更安全。
25. A (正确)。技能树通常允许一个技能有多个前置技能，这构成了有向无环图（DAG），而非严格的树结构。