单项选择题15题（每题2分），阅读程序17题（共40分），完善程序10题（每题3分），共100分

一、单项选择题

共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、递归函数定义如下：

$$\begin{aligned} f(0) &= 1 \\ f(1) &= 1 \\ f(n) &= f(n-1) + 2 \times f(n-2) \quad (n \geq 2) \end{aligned}$$

则 $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分。其中第16~18题每题2分，第32题4分。

阅读程序（一）

#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) \leq 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)$

---

阅读程序（二）

#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)$

---

阅读程序（三）

#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 \leq n, q \leq 100$，询问满足 $1 \leq l \leq r \leq 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分。

完善程序（一）

下面程序在一个升序数组中查找第一个大于等于 $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

---

完善程序（二）

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

#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]