一、单项选择题解析

1. C ｜ continue 会跳过当前循环本轮剩余语句，进入下一轮循环。

2. B ｜ $75_8 = 7 \times 8 + 5 = 61$，$1011_2 = 1 \times 8 + 0 \times 4 + 1 \times 2 + 1 = 11$，和为 $61 + 11 = 72$。

3. C ｜ 数组下标从0开始，a[2] 是第三个元素，值为3。

4. B ｜ 队列先进先出，弹出1后，队首为2。

5. B ｜ 下标为 $x$ 的结点父结点为 $\lfloor x/2 \rfloor$，左儿子为 $2x$。所以父结点为 $\lfloor 12/2 \rfloor = 6$，左儿子为 $12 \times 2 = 24$。

6. D ｜ 无向图度数和等于边数的2倍，即 $12 \times 2 = 24$。

7. B ｜ 拓扑排序要求每条边的起点都在终点之前。边 (1,3) 要求1在3前，边 (2,3) 要求2在3前，边 (3,4) 要求3在4前，边 (2,5) 要求2在5前。只有选项 B (2, 1, 5, 3, 4) 满足所有条件。

8. A ｜ 中缀表达式 $(a + b) \times (c - d)$ 的前缀表达式为 *+ab-cd。

9. C ｜ 总排列数为 $\frac{5!}{2!} = \frac{120}{2} = 60$。

10. C ｜ 依次计算得 $f(2) = f(1) + 2f(0) = 1 + 2 = 3$，$f(3) = f(2) + 2f(1) = 3 + 2 = 5$，$f(4) = f(3) + 2f(2) = 5 + 6 = 11$，$f(5) = f(4) + 2f(3) = 11 + 10 = 21$。

11. C ｜ p 指向 x，(*p)++ 会使 x 增加1，所以输出4。

12. C ｜ 外层循环执行 $O(\log n)$ 次（每次 $i$ 乘以2），内层每次执行 $O(n)$，总复杂度为 $O(n \log n)$。

13. A ｜ 插入后得到一棵完全形态的二叉搜索树：

        4
       / \
      2   6
     / \ / \
    1  3 5  7

后序遍历为 1, 3, 2, 5, 7, 6, 4。

14. B ｜ s + s[0] 表示在字符串末尾追加字符 s[0]（即 'a'），结果为 "abca"。

15. C ｜ class 是C++关键字，不能作为变量名。

---

二、阅读程序解析

阅读程序（一）

程序中 f 是欧几里得算法，计算最大公约数；g 计算最小公倍数。由于最小公倍数为 $\frac{x}{\gcd(x,y)} \times y$，所以不会超过 $x \times y$。

16. A（正确） ｜ 输入 12 18：$\gcd(12, 18) = 6$，$\text{lcm}(12, 18) = 12 / 6 \times 18 = 36$，输出 "6 36"。

17. A（正确） ｜ 欧几里得算法满足交换律，$\gcd(x, y) = \gcd(y, x)$。

18. A（正确） ｜ $\text{lcm}(x, y) = \frac{x \times y}{\gcd(x, y)}$，由于 $\gcd(x, y) \geq 1$，所以 $\text{lcm}(x, y) \leq x \times y$。

19. B ｜ 输入 21 6：$\gcd(21, 6) = 3$，$\text{lcm}(21, 6) = 21 / 3 \times 6 = 42$，输出 "3 42"。

20. C ｜ 欧几里得算法的时间复杂度为 $O(\log \max(x, y))$。

---

阅读程序（二）

程序把每一段连续相同字符压缩为"字符+出现次数"的形式。由于每一段都会输出2个字符（1个字符+1个数字），所以输出长度一定是偶数。

21. A（正确） ｜ 输入 "aaabbc"：aaa→a3，bb→b2，c→c1，输出 "a3b2c1"。

22. A（正确） ｜ 每一段连续相同字符输出2个字符（字符+数字），所以总长度一定是偶数。

23. A（正确） ｜ 如果无相邻相同字符，每个字符单独成段，输出"字符1"共2个字符，总长度为输入长度的2倍。

24. A ｜ 输入 "abcccdd"：a→a1，b→b1，ccc→c3，dd→d2，输出 "a1b1c3d2"。

25. B ｜ 输入 "aaabbbba"：aaa→a3，bbbb→b4，a→a1，输出 "a3b4a1"。

26. C ｜ 程序遍历字符串一次，时间复杂度为 $O(n)$。

---

阅读程序（三）

数组 $s$ 是前缀和，$s_i$ 表示前 $i$ 个数的和。区间 $[l, r]$ 的和为 $s_r - s_{l-1}$。负数并不会影响前缀和的正确性。

27. A（正确） ｜ 前缀和数组 $s$ 满足 $s_i = s_{i-1} + a_i$，区间和 $= s_r - s_{l-1}$。

28. A（正确） ｜ $s$ 是全局数组，$s[0]$ 初始为0。当 $l = 1$ 时，$s[l-1] = s[0] = 0$，计算正确。

29. B（错误） ｜ 负数不会影响前缀和的正确性，$s_r - s_{l-1}$ 仍然等于区间 $[l, r]$ 的和。

30. B ｜

• 数组：1, 2, 3, 4, 5
• 前缀和：0, 1, 3, 6, 10, 15
• 询问 1 3：$s_3 - s_0 = 6 - 0 = 6$
• 询问 2 5：$s_5 - s_1 = 15 - 1 = 14$
• 输出 6 和 14

31. B ｜

• 数组：-1, 5, -2, 4
• 前缀和：0, -1, 4, 2, 6
• 询问 1 4：$s_4 - s_0 = 6 - 0 = 6$

32. C ｜ 预处理前缀和 $O(n)$，每次询问 $O(1)$，共 $q$ 次询问，总时间复杂度 $O(n + q)$。

---

三、完善程序解析

完善程序（一）

这是典型的左闭右开二分查找。若 $a_m < x$，说明答案在右侧，令 $l = m + 1$；否则答案可能是 $m$，令 $r = m$。循环结束后 $l$ 即为第一个大于等于 $x$ 的位置。

33. B ｜ 判断条件为 a[m] < x，如果成立说明目标在右半部分。

34. C ｜ 当 a[m] < x 时，答案在右侧，令 l = m + 1。

35. B ｜ 当 a[m] >= x 时，答案可能是 $m$ 或在左侧，令 r = m。

36. B ｜ 循环结束时 $l = r$，返回 $l$ 即为第一个大于等于 $x$ 的位置。

37. C ｜ 如果 $pos = n$，说明所有元素都小于 $x$，输出 -1。

---

完善程序（二）

原矩阵位置 $(i, j)$ 顺时针旋转 $90^\circ$ 后会移动到 $(j, n - 1 - i)$。因此转移语句为 b[j][n - 1 - i] = a[i][j]。

38. B ｜ 外层循环遍历所有行，$i$ 从 0 到 $n-1$，条件为 i < n。

39. D ｜ 内层循环遍历所有列，$j$ 从 0 到 $n-1$，条件为 j < n。

40. B ｜ 旋转后行号变为原来的列号 $j$。

41. C ｜ 旋转后列号变为 $n - 1 - i$。

42. A ｜ 赋值为原矩阵位置 $(i, j)$ 的元素 a[i][j]。