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

---

1. 在 C++ 中，continue 语句的作用是？

{{ select(1) }}

• 立即结束整个程序
• 立即结束当前函数
• 跳过本轮循环剩余语句，进入下一轮循环
• 结束当前循环所在的所有外层循环

---

2. 八进制数 $(75)_8$ 与二进制数 $(1011)_2$ 的和对应的十进制值是？

{{ select(2) }}

• 70
• 72
• 74
• 76

---

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

int a[5] = {1, 2, 3, 4, 5};
cout << a[2];

{{ select(3) }}

• 1
• 2
• 3
• 4

---

4. 一个空队列依次执行如下操作：

push 1
push 2
pop
push 3

此时队首元素是？

{{ select(4) }}

• 1
• 2
• 3
• 队列为空

---

5. 一棵完全二叉树用数组存储，根结点存储在下标 1 的位置。若某结点下标为 12，则它的父结点下标和左儿子下标分别为？

{{ select(5) }}

• $5, 24$
• $6, 24$
• $6, 25$
• $7, 24$

---

6. 一个无向图有 9 个顶点、12 条边，则所有顶点的度数之和为？

{{ select(6) }}

• 12
• 18
• 21
• 24

---

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

{{ select(7) }}

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

---

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

{{ select(8) }}

• *+ab-cd
• +a*b-cd
• ab+cd-*
• *-+abcd

---

9. 由字母 A, A, B, C, D 组成的不同字符串共有多少个？

{{ select(9) }}

• 30
• 45
• 60
• 120

---

10. 递归函数定义如下：

f(0)=1
f(1)=1
f(n)=f(n-1)+2*f(n-2)  (n>=2)

则 $f(5)$ 的值为？

{{ select(10) }}

• 11
• 15
• 21
• 31

---

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

int x = 3;
int *p = &x;
(*p)++;
cout << x;

{{ select(11) }}

• 2
• 3
• 4
• 程序无法通过编译

---

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

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

{{ select(12) }}

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

---

13. 按顺序向一棵空二叉搜索树中插入 $4, 2, 6, 1, 3, 5, 7$，则该二叉搜索树的后序遍历为？

{{ select(13) }}

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

---

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

string s = "abc";
cout << s + s[0];

{{ select(14) }}

• abc
• abca
• aabc
• 程序无法通过编译

---

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

{{ select(15) }}

• sum
• _count
• class
• num2026

---

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

#include <iostream>
using namespace std;

int f(int a, int b) {
    while (b) {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int g(int a, int b) {
    return a / f(a, b) * b;
}

int main() {
    int x, y;
    cin >> x >> y;
    cout << f(x, y) << " " << g(x, y) << endl;
    return 0;
}

假设输入的 $x, y$ 均为不超过 10000 的正整数。

判断题

---

16. 当输入为 12 18 时，程序输出为 6 36。

{{ select(16) }}

• 正确
• 错误

---

17. 对任意合法输入 $x, y$，都有 $f(x, y) = f(y, x)$。

{{ select(17) }}

• 正确
• 错误

---

18. 对任意合法输入 $x, y$，都有 $g(x, y) \le x \times y$。

{{ select(18) }}

• 正确
• 错误

---

选择题

---

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

{{ select(19) }}

• 1 126
• 3 42
• 6 21
• 7 42

---

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

{{ select(20) }}

• $O(1)$
• $O(x + y)$
• $O(\log \max(x, y))$
• $O(xy)$

---

(2)

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

string f(string s) {
    string r;
    int c = 1;

    for (int i = 1; i <= s.size(); i++) {
        if (i < s.size() && s[i] == s[i - 1]) {
            c++;
        } else {
            r += s[i - 1];
            r += char('0' + c);
            c = 1;
        }
    }

    return r;
}

int main() {
    string s;
    cin >> s;
    cout << f(s) << endl;
    return 0;
}

假设输入字符串非空，只包含小写字母，且任意一段连续相同字符的长度都不超过 9。

判断题

---

21. 当输入为 aaabbc 时，程序输出为 a3b2c1。

{{ select(21) }}

• 正确
• 错误

---

22. 程序输出字符串的长度一定是偶数。

{{ select(22) }}

• 正确
• 错误

---

23. 如果输入字符串中不存在相邻且相同的字符，则输出字符串长度等于输入字符串长度的 2 倍。

{{ select(23) }}

• 正确
• 错误

---

选择题

---

24. 当输入为 abcccdd 时，程序输出为？

{{ select(24) }}

• a1b1c3d2
• a1b1c2d3
• ab3cd2
• a1b1cccdd

---

25. 当输入为 aaabbbba 时，程序输出为？

{{ select(25) }}

• a3b3a1
• a3b4a1
• a4b3a1
• a3b4

---

26. 设输入字符串长度为 $n$，该程序的时间复杂度为？

{{ select(26) }}

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

---

(3)

#include <iostream>
using namespace std;

int a[105], s[105];

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

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

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

假设 $1 \le n, q \le 100$，询问满足 $1 \le l \le r \le n$。

判断题

---

27. 程序对每个询问输出数组下标 $l$ 到 $r$ 的元素和。

{{ select(27) }}

• 正确
• 错误

---

28. 当 $l = 1$ 时，程序会使用 $s_0$，由于 $s$ 是全局数组，因此 $s_0$ 初始为 0。

{{ select(28) }}

• 正确
• 错误

---

29. 如果数组中出现负数，程序一定不能正确计算区间和。

{{ select(29) }}

• 正确
• 错误

---

选择题

---

30. 若输入为：

5 2
1 2 3 4 5
1 3
2 5

程序输出为？

{{ select(30) }}

• 3
  14
  

• 6
  14
  

• 6
  15
  

• 5
  14
  

---

31. 若输入为：

4 1
-1 5 -2 4
1 4

程序输出为？

{{ select(31) }}

• 5
• 6
• 7
• 8

---

32. 该程序处理所有输入的总时间复杂度为？

{{ select(32) }}

• $O(n)$
• $O(q)$
• $O(n + q)$
• $O(nq)$

---

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

（1）下面程序在一个升序数组中查找第一个大于等于 $x$ 的元素位置。若不存在这样的元素，输出 -1；否则输出该元素的下标。

数组下标从 0 开始。

#include <iostream>
using namespace std;

int a[1005];

int lb(int n, int x) {
    int l = 0, r = n;

    while (l < r) {
        int m = (l + r) / 2;

        if (①) ②;
        else ③;
    }

    return ④;
}

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

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

    int pos = lb(n, x);

    if (⑤) cout << -1 << endl;
    else cout << pos << endl;

    return 0;
}

---

33. ① 处应填？

{{ select(33) }}

• a[m] <= x
• a[m] < x
• a[m] > x
• a[m] == x

---

34. ② 处应填？

{{ select(34) }}

• l = m
• r = m
• l = m + 1
• r = m - 1

---

35. ③ 处应填？

{{ select(35) }}

• l = m + 1
• r = m
• r = m - 1
• l = m

---

36. ④ 处应填？

{{ select(36) }}

• m
• l
• r - 1
• n - l

---

37. ⑤ 处应填？

{{ select(37) }}

• pos < 0
• pos == 0
• pos == n
• a[pos] == x

---

（2）下面程序将一个 $n \times n$ 的矩阵顺时针旋转 90° 后输出。

#include <iostream>
using namespace std;

int a[105][105], b[105][105];

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

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

    for (int i = 0; i < ①; i++) {
        for (int j = 0; j < ②; j++) {
            b[③][④] = ⑤;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << b[i][j] << " ";
        cout << endl;
    }

    return 0;
}

---

38. ① 处应填？

{{ select(38) }}

• n - 1
• n
• n + 1
• i

---

39. ② 处应填？

{{ select(39) }}

• n - 1
• i
• j
• n

---

40. ③ 处应填？

{{ select(40) }}

• i
• j
• n - 1 - i
• n - 1 - j

---

41. ④ 处应填？

{{ select(41) }}

• i
• j
• n - 1 - i
• n - 1 - j

---

42. ⑤ 处应填？

{{ select(42) }}

• a[i][j]
• a[j][i]
• b[i][j]
• b[j][i]