一、单项选择题(每题 2 分,共 30 分)

1. 在 C++ 中,continue 语句的作用是?

{{ select(1) }}

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

2. 八进制数 $75_8$ 与二进制数 $1 0 1 1_{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) }}

• $\times +ab-cd$
• $+a\times b-cd$
• $ab+cd-\times$
• $\times -+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$ 分。其中第 $16 \sim 18$ 题每题 $2$ 分,第 $32$ 题 $4$ 分。

阅读程序(一)

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

#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;
}

(程序 $1$ ,每题 $1.5$ 分)

(1) 当输入为 $12$ $18$ 时,程序输出为 $6$ $36$ 。

{{ select(16) }}

• 正确
• 错误

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

{{ select(17) }}

• 正确
• 错误

(3) 对任意合法输入 $x$, $y$ ,都有 $g(x, y) \leq x×y$ 。

{{ select(18) }}

• 正确
• 错误

(4) 当输入为 $21$ $6$ 时,程序输出为?

{{ select(19) }}

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

(5) 该程序的时间复杂度最准确地表示为?

{{ select(20) }}

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

阅读程序(二)

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

#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;
}

(程序 $2$ ,每题 $1.5$ 分)

(1) 当输入为 aaabbc 时,程序输出为 a3b2c1 。

{{ select(21) }}

• 正确
• 错误

(2) 程序输出字符串的长度一定是偶数。

{{ select(22) }}

• 正确
• 错误

(3) 如果输入字符串中不存在相邻且相同的字符,则输出字符串长度等于输入字符串长度的 $2$ 倍。

{{ select(23) }}

• 正确
• 错误

(4) 当输入为 abcccdd 时,程序输出为?

{{ select(24) }}

• a1b1c3d2
• a1b1c2d3
• ab3cd2
• a1b1cccdd

(5) 当输入为 aaabbbba 时,程序输出为?

{{ select(25) }}

• a3b3a1
• a3b4a1
• a4b3a1
• a3b4

(6) 设输入字符串长度为 $n$ ,该程序的时间复杂度为?

{{ select(26) }}

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

阅读程序(三)

假设 $1 ≤n,q≤100$ ,询问满足 $1 ≤l≤r≤n$ 。

#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;
}

(程序 $3$ ,每题 $1.5$ 分)

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

{{ select(27) }}

• 正确
• 错误

(2) 当 $l= 1$ 时,程序会使用 $s_0$ ,由于s是全局数组,因此 $s_0$ 初始为 $0$ 。

{{ select(28) }}

• 正确
• 错误

(3) 如果数组中出现负数,程序一定不能正确计算区间和。

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

5 2
1 2 3 4 5
1 3
2 5

程序输出为?

{{ select(30) }}

• 3
  14
  

• 6
  14
  

• 6
  15
  

• 5
  14
  

(5) 若输入为:

4 1
-1 5 -2 4
1 4

程序输出为?

{{ select(31) }}

• $5$
• $6$
• $7$
• $8$

(6) 该程序处理所有输入的总时间复杂度为?

{{ 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;
}

(1) ① 处应填( )

{{ select(33) }}

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

(2) ② 处应填( )

{{ select(34) }}

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

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

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

(5) ⑤ 处应填( )

{{ select(37) }}

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

完善程序(二)

下面程序将一个n× 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;
}

(1) ① 处应填( )

{{ select(38) }}

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

(2) ② 处应填( )

{{ select(39) }}

• n - 1
• i
• j
• n

(3) ③ 处应填( )

{{ select(40) }}

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

(4) ④ 处应填( )

{{ select(41) }}

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

(5) ⑤ 处应填( )

{{ select(42) }}

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