参考答案与详细解析

一、 单项选择题

1. C。 解析：'b' 的 ASCII 码是 98 ($01100010_2$)。4 是 $00000100_2$。异或运算 ^：$01100010 \oplus 00000100 = 01100110_2 = 102$。ASCII 102 对应字符 'f'。

2. C。 解析：p + a 是一个算术表达式的结果（右值），不能被赋值。指针变量 p 可以被赋值（如 D），指针指向的内容 *p 可以被赋值（如 A, B）。

3. B。 解析：构造派生类对象时，会先调用基类的构造函数，再调用派生类的构造函数。

4. D。 解析：arr 大小为 5（下标 0-4）。p = arr + 2 指向 arr[2]。p[3] 相当于 *(p+3) 即 arr[5]。数组越界访问，属于未定义行为，可能输出垃圾值或导致运行时异常。

5. A。 解析：完全二叉树深度公式为 $\lfloor \log_2 N \rfloor + 1$。

6. D。 解析：根据图示结构（A为根，B、C为第二层，D、E为第三层，且看起来是层序排列），广度优先遍历（层序遍历）顺序为 A -> B -> C -> D -> E。

7. A。 解析：深度优先搜索（DFS）通常借助栈（或递归调用栈）实现，广度优先搜索（BFS）才借助队列。

8. B。 解析：$n$ 个顶点的简单有向图最多有 $n(n-1)$ 条边。

   • $n=5: 5 \times 4 = 20 < 28$。
   • $n=6: 6 \times 5 = 30 \ge 28$。 所以至少 6 个顶点。

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

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

11. A。 解析：这是记忆化搜索求斐波那契数列。 $f(0)=0, f(1)=1$。 $f(2)=1, f(3)=2, f(4)=3, f(5)=5, f(6)=8$。

12. D。 解析：由于使用了数组 rec_fib 进行记忆化，每个 fib(n) 只计算一次，总时间复杂度为 $O(n)$。

13. C。 解析：这是标准的二分查找算法，时间复杂度为 $O(\log n)$。

14. A。 解析：这是线性筛（欧拉筛）算法，每个合数只被其最小质因子筛去一次，时间复杂度为 $O(n)$。

15. B。 解析：BFS 必须按层级访问。

    • 第一层：1。
    • 第二层：2, 4（1的邻居）。
    • 第三层：3, 5, 7（2和4的邻居）。 选项 B 中 1, 2, 5...，5 是第三层节点，4 是第二层节点。BFS 不可能在访问完第二层的 2 之后直接访问第三层的 5，而跳过同层的 4。

二、 判断题

16. A (正确)。$9 (1001_2) \text{ \& } 12 (1100_2) = 8 (1000_2)$。类型为 int。
17. A (正确)。指针可能指向非法内存（野指针、空指针解引用等）。
18. B (错误)。快速排序最差情况（数组已有序且 pivot 选择不当）时间复杂度为 $O(n^2)$。
19. A (正确)。long long 通常 8 字节，float 通常 4 字节。
20. B (错误)。pow 函数返回 double 类型，不是 int。
21. A (正确)。二叉排序树（BST）的中序遍历结果是递增有序序列。
22. A (正确)。根据鸽巢原理，元素数量超过哈希表容量（或负载因子限制）时必然发生冲突。
23. B (错误)。构造函数不能声明为虚函数（因为构造时虚表指针尚未完全建立），析构函数可以且推荐声明为虚函数。
24. B (错误)。动态规划可以使用**递推（迭代）**实现，不一定非要递归。
25. B (错误)。导航通常需要带权图（表示距离或时间），且两个城市间可能有多条路（重边），简单图无法完全满足需求。