一、单项选择题解析

1. B ｜ 函数 f 中定义的是局部变量 x，不会改变全局变量 x，所以输出 5。

2. C ｜ $2F_{16} = 47$，$101101_2 = 45$，两者之和为 92。

3. C ｜ p 指向数组首元素，*(p+2) 等价于 a[2]，值为 6。

4. D ｜ 队列先进先出，两次 pop 分别弹出 4 和 7，最后队列为 9, 1。

5. B ｜ 每个非叶子结点都有 2 个孩子的二叉树满足总结点数为 $2L - 1$，其中 $L$ 为叶子数，所以答案为 19。

6. C ｜ 无向简单图最多有 $C_7^2 = 21$ 条边。

7. C ｜ 需要满足 1 在 3 前，2 在 3 和 4 前，共有 5 种拓扑排序。

8. A ｜ 后缀表达式按栈计算，先算 $b \times c$，再加 $a$，最后减 $d$。

9. B ｜ 选 3 个互不相邻的数，方案为 {1, 3, 5}, {1, 3, 6}, {1, 4, 6}, {2, 4, 6}，共 4 种。

10. C ｜ 依次计算 $f(3) = 3$, $f(4) = 5$, $f(5) = 8$, $f(6) = 13$。

11. B ｜ r 是 x 的引用，执行 r = y 相当于执行 x = y。

12. B ｜ 内层循环执行次数为 $\lfloor n/i \rfloor$，总次数约为 $n(1 + \frac{1}{2} + \cdots + \frac{1}{n})$，复杂度为 $O(n \log n)$。

13. B ｜ 二分查找通常用于具有单调性的序列或答案空间。

14. D ｜ 哈夫曼合并过程为 4 + 6 = 10，8 + 10 = 18，12 + 18 = 30，20 + 30 = 50，频率为 4 的字符深度为 4。

15. C ｜ set 可以维护有序集合，并支持查找元素是否存在。

二、阅读程序解析

阅读程序（一）

程序实现高精度加法。程序先把两个字符串反转，从低位到高位逐位相加并处理进位，得到的结果最初是逆序的，因此最后必须再反转一次。

16. A（正确） ｜ 输入 99 和 1，高精度加法结果为 100。

17. A（正确） ｜ 题目假设输入除数字0外没有前导零，程序正确处理进位，输出不会含有前导零。

18. B（错误） ｜ 删去最后一次 reverse 后，结果会是逆序的，无法正确输出两数之和。

19. C ｜ 12345 + 6789 = 19134。

20. C ｜ 循环次数取决于较长的字符串长度，时间复杂度为 $O(\max(n, m))$。

阅读程序（二）

程序使用邻接矩阵和队列进行广度优先搜索（BFS）。由于 BFS 按照距离从小到大扩展，所以第一次到达某个点时得到的就是从 1 号点到它的最少边数。

21. A（正确） ｜ 若存在边 (1, n)，则从 1 号点一步即可到达 n 号点，输出 1。

22. B（错误） ｜ 程序输出的是从 1 号点到 n 号点经过的最少边数，但如果无法到达则输出 -1，题目表述不够准确。

23. A（正确） ｜ 如果 1 号点无法到达 n 号点，d[n] 保持初始值 -1，程序输出 -1。

24. B ｜ 从 1 到 5 的最短路径为 1→2→5，经过 2 条边。

25. C ｜ 从 1 到 6 的最短路径为 1→2→3→4→5→6，经过 5 条边。

26. D ｜ 使用邻接矩阵存储，每个点出队时需要遍历所有 n 个点检查是否有边，时间复杂度为 $O(n^2)$。

阅读程序（三）

程序实现最长严格上升子序列的朴素动态规划。$dp_i$ 表示以第 $i$ 个数结尾的最长严格上升子序列长度，而不是前 $i$ 个数整体的答案；整体答案需要用 ans 维护。

27. A（正确） ｜ 输入 1 2 3 4 5 是严格上升序列，最长上升子序列长度为 5。

28. B（错误） ｜ $dp_i$ 表示以第 $i$ 个数结尾的最长上升子序列长度，不是前 $i$ 个数整体的答案。

29. A（正确） ｜ 条件是 a[j] < a[i]，严格小于，所以相等的元素不能同时出现在同一个上升子序列中。

30. B ｜ 序列 3 1 2 1 8 5 的最长上升子序列为 1 2 8 或 1 2 5，长度为 3。

31. B ｜ 序列 5 1 6 2 7 3 8 4 的最长上升子序列为 1 2 3 4 或 1 2 3 8 等，长度为 4。

32. C ｜ 序列 2 1 4 3 5 7 6 8 的最长上升子序列为 1 3 5 7 8 或 1 3 5 6 8，长度为 5。

三、完善程序解析

完善程序（一）

程序实现归并排序。递归处理左右两段后，用双指针将两个有序段合并到辅助数组 b 中，再复制回原数组 a。

33. A ｜ 递归终止条件是 l >= r，即区间长度为 1 或无效时直接返回。

34. B ｜ 右半部分从 m + 1 开始，所以填 m + 1。

35. C ｜ 合并时两个指针都要在有效范围内，条件是 i <= m && j <= r。

36. A ｜ 将左半部分剩余元素复制到辅助数组，填 b[k++] = a[i++]。

37. B ｜ 将辅助数组 b 中的有序结果复制回原数组 a，填 a[i] = b[i]。

完善程序（二）

程序实现拓扑排序。读入边 $u \to v$ 时，$v$ 的入度加 1；先将所有入度为 0 的点入队。每弹出一个点，就删除它发出的边，使对应终点入度减 1。若最终输出点数不足 $n$，说明图中存在环。

38. A ｜ 读入边 $u \to v$ 后，需要增加 $v$ 的入度，填 d[v]++。

39. C ｜ 拓扑排序从入度为 0 的点开始，填 d[i] == 0。

40. B ｜ 从队列头部取出元素，填 q[hd++]。

41. A ｜ 删除边后，终点的入度减 1，填 d[v]--。

42. D ｜ 若输出的点数不足 $n$，说明存在环，填 tot < n。