一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

---

1. 阅读下面代码，输出结果是？

bool x = false;
cout << x;

{{ select(1) }}

• 0
• 1
• false
• 程序无法通过编译

---

2. 二进制数 $101011_2$ 与八进制数 $36_8$ 的和对应的十进制值是？

{{ select(2) }}

• 71
• 72
• 73
• 74

---

3. 阅读下面代码，输出结果是？

int a = 3, b = 4;
cout << (a += b) << " " << a;

{{ select(3) }}

• 7 7
• 7 3
• 3 7
• 3 3

---

4. 一个空栈依次将 $1, 2, 3, 4, 5$ 入栈，下面哪个序列不可能作为出栈序列？

{{ select(4) }}

• $2, 1, 5, 4, 3$
• $3, 5, 4, 2, 1$
• $4, 2, 3, 1, 5$
• $1, 3, 2, 5, 4$

---

5. 在单向链表中，若指针 p 指向某个结点，且 p->next 存在。若要删除 p 后面的直接后继结点，通常应执行哪条语句？

{{ select(5) }}

• p = p->next;
• p->next = p->next->next;
• p->next = p;
• p = p->next->next;

---

6. 一棵二叉树有 13 个结点，并且每个结点的孩子数只能是 0 或 2，则这棵树有多少个叶子结点？

{{ select(6) }}

• 5
• 6
• 7
• 8

---

7. 有向无环图中有边 $(1,3), (1,4), (2,4), (3,5)$。下面哪个序列是合法的拓扑排序？

{{ select(7) }}

• $1, 2, 3, 4, 5$
• $3, 1, 2, 4, 5$
• $1, 4, 2, 3, 5$
• $2, 1, 5, 3, 4$

---

8. 中缀表达式 $a + (b - c) \times d$ 对应的后缀表达式是？

{{ select(8) }}

• abc-+d*
• ab-cd*+
• abc-d*+
• a+bc-d*

---

9. 有 4 个字符，其出现频率分别为 $2, 4, 7, 9$。若使用哈夫曼编码，则频率为 2 的字符编码长度为？

{{ select(9) }}

• 1
• 2
• 3
• 4

---

10. 已知一棵二叉树的前序遍历为 A B D C E，中序遍历为 D B A E C，则其后序遍历为？

{{ select(10) }}

• D E B C A
• D B E C A
• B D E C A
• D B C E A

---

11. 对含有 1025 个元素的有序数组进行二分查找，最坏情况下最多需要比较多少次？

{{ select(11) }}

• 9
• 10
• 11
• 12

---

12. 下面代码片段的时间复杂度是？

for (int i = 1; i <= n; i *= 2)
    for (int j = 1; j <= n; j += i)
        cout << i + j << endl;

{{ select(12) }}

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O((\log n)^2)$

---

13. 有 5 名男生和 4 名女生，从中选出 3 人组成小组，要求至少有 2 名女生，共有多少种选法？

{{ select(13) }}

• 30
• 34
• 40
• 44

---

14. 递归函数定义如下：

f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)+1  (n>=3)

{{ select(14) }}

• 7
• 8
• 12
• 13

---

15. 下面哪个不能作为 C++ 变量名？

{{ select(15) }}

• sum
• num2026
• return
• _cnt

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ×；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）

阅读程序（一）

#include <iostream>
using namespace std;

int f(int x) {
    int s = 0;

    while (x) {
        s += x & 1;
        x >>= 1;
    }

    return s;
}

int g(int x) {
    int r = 1;

    while (r * 2 <= x)
        r *= 2;

    return r;
}

int main() {
    int n;
    cin >> n;

    cout << f(n) << " " << g(n) << endl;
    return 0;
}

假设输入的 $n$ 是不超过 1000000 的正整数。

判断题

---

16. 当输入为 10 时，程序输出为 2 8。

{{ select(16) }}

• 正确
• 错误

---

17. 若输入的 $n$ 是 2 的正整数次幂，则 $f(n)$ 的返回值为 $1$。

{{ select(17) }}

• 正确
• 错误

---

18. 对任意合法输入 $n$，$g(n)$ 的返回值一定是不超过 $n$ 的最大的 2 的幂。

{{ select(18) }}

• 正确
• 错误

单项选择题

---

19. 当输入为 2026 时，程序输出为？

{{ select(19) }}

• 7 1024
• 8 1024
• 8 2048
• 9 1024

---

20. 该程序的时间复杂度最准确地表示为？

{{ select(20) }}

• $O(1)$
• $O(n)$
• $O(\log n)$
• $O(n \log n)$

阅读程序（二）

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int f(string a, string b) {
    int ans = 0;

    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            int k = 0;

            while (i + k < a.size() && j + k < b.size()
                   && a[i + k] == b[j + k]) {
                k++;
            }

            ans = max(ans, k);
        }
    }

    return ans;
}

bool g(string s) {
    for (int i = 0; i < s.size() / 2; i++) {
        if (s[i] != s[s.size() - 1 - i])
            return false;
    }

    return true;
}

int main() {
    string x, y;
    cin >> x >> y;

    cout << f(x, y) << " " << g(x + y) << endl;
    return 0;
}

假设输入的两个字符串只包含小写字母，且长度均不超过 100。

判断题

---

21. 函数 f 返回两个字符串的最长公共子串长度。

{{ select(21) }}

• 正确
• 错误

---

22. 若两个输入字符串完全相同，则函数 f 的返回值等于该字符串的长度。

{{ select(22) }}

• 正确
• 错误

---

23. 函数 g 用于判断字符串是否为回文串。

{{ select(23) }}

• 正确
• 错误

单项选择题

---

24. 当输入为：

abca bcab

{{ select(24) }}

• 2 0
• 3 0
• 3 1
• 4 0

---

25. 当输入为：

abc cba

{{ select(25) }}

• 1 0
• 2 0
• 1 1
• 3 1

---

26. 设两个输入字符串长度分别为 $n, m$，该程序中函数 f 最坏情况下的时间复杂度为？

{{ select(26) }}

• $O(n + m)$
• $O(nm)$
• $O(nm \log(n + m))$
• $O(nm \min(n, m))$

阅读程序（三）

#include <iostream>
#include <algorithm>
using namespace std;

int a[105], dp[105];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        dp[i] = 1;

        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }

        ans = max(ans, dp[i]);
    }

    cout << ans << endl;
    return 0;
}

假设 $1 \le n \le 100$，输入的所有整数均在 int 范围内。

判断题

---

27. 该程序求的是最长严格上升子序列长度。

{{ select(27) }}

• 正确
• 错误

---

28. 若输入的所有数都相等，则程序输出 $n$。

{{ select(28) }}

• 正确
• 错误

---

29. 程序中的 $dp_i$ 表示以第 $i$ 个数结尾的最长不下降子序列长度。

{{ select(29) }}

• 正确
• 错误

单项选择题

---

30. 若输入为：

6
3 1 2 2 1 4

{{ select(30) }}

• 2
• 3
• 4
• 5

---

31. 若输入为：

7
5 4 3 2 1 1 1

{{ select(31) }}

• 2
• 3
• 4
• 5

---

32. 若输入为：

8
2 1 3 2 4 3 5 4

{{ select(32) }}

• 3
• 4
• 5
• 6

三、完善程序（单选题，每题 3 分，共计 30 分）

完善程序（一）

下面程序将两个升序数组合并成一个升序数组，请补全程序。

#include <iostream>
using namespace std;

int a[1005], b[1005], c[2010];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= m; i++)
        cin >> b[i];

    int i = 1, j = 1, k = 0;

    while (①) {
        if (②)
            ③;
        else
            c[++k] = b[j++];
    }

    while (i <= n)
        c[++k] = a[i++];

    while (④)
        ⑤;

    for (int t = 1; t <= k; t++)
        cout << c[t] << " ";

    return 0;
}

---

33. ① 处应填？

{{ select(33) }}

• i <= n || j <= m
• i < n && j < m
• i <= n && j <= m
• i == n && j == m

---

34. ② 处应填？

{{ select(34) }}

• a[i] <= b[j]
• a[i] >= b[j]
• i <= j
• n <= m

---

35. ③ 处应填？

{{ select(35) }}

• c[++k] = b[j++]
• c[++k] = a[i++]
• a[++k] = c[i++]
• b[++k] = c[j++]

---

36. ④ 处应填？

{{ select(36) }}

• i <= n
• i <= m
• j <= m
• j <= n

---

37. ⑤ 处应填？

{{ select(37) }}

• c[++k] = a[i++]
• c[++k] = b[i++]
• c[++k] = a[j++]
• c[++k] = b[j++]

完善程序（二）

下面程序求两个字符串的最长公共子序列长度，请补全程序。

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int dp[105][105];

int main() {
    string a, b;
    cin >> a >> b;

    int n = a.size();
    int m = b.size();

    for (int i = 1; i <= ①; i++) {
        for (int j = 1; j <= ②; j++) {
            if (③)
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = ④;
        }
    }

    cout << ⑤ << endl;
    return 0;
}

---

38. ① 处应填？

{{ select(38) }}

• n - 1
• n
• m
• m - 1

---

39. ② 处应填？

{{ select(39) }}

• n
• n - 1
• m
• m - 1

---

40. ③ 处应填？

{{ select(40) }}

• a[i] == b[j]
• a[i - 1] == b[j - 1]
• a[i] != b[j]
• i == j

---

41. ④ 处应填？

{{ select(41) }}

• dp[i - 1][j - 1] + 1
• dp[i - 1][j - 1]
• max(dp[i - 1][j], dp[i][j - 1])
• max(dp[i][j], dp[i - 1][j - 1])

---

42. ⑤ 处应填？

{{ select(42) }}

• dp[0][0]
• dp[n][0]
• dp[0][m]
• dp[n][m]