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

---

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

#include <iostream>
using namespace std;

int a[3];

int main() {
    cout << a[0];
    return 0;
}

{{ select(1) }}

• 不确定
• 0
• 1
• 程序无法通过编译

---

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

{{ select(2) }}

• 50
• 52
• 54
• 56

---

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

int x = 5;
cout << x++ << " " << x;

{{ select(3) }}

• 5 5
• 5 6
• 6 6
• 6 5

---

4. 一个栈初始为空，依次执行如下操作：

push 1
push 2
pop
push 3
pop
push 4

{{ select(4) }}

• 1
• 2
• 4
• 栈为空

---

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

{{ select(5) }}

• D E B F G C A
• D B E F G C A
• E D B G F C A
• D E B C F G A

---

6. 一棵完全二叉树用数组存储，根结点存储在下标 1 的位置。若某结点下标为 14，则它的兄弟结点下标是？

{{ select(6) }}

• 6
• 7
• 13
• 15

---

7. 一个不含自环的有向图有 5 个顶点，若用邻接矩阵表示，矩阵中最多可能有多少个非零元素？

{{ select(7) }}

• 10
• 15
• 20
• 25

---

8. 冒泡排序对 6 个元素进行从小到大排序，在最坏情况下需要比较多少次？

{{ select(8) }}

• 12
• 15
• 18
• 21

---

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

{{ select(9) }}

• 24
• 26
• 28
• 32

---

10. 前缀表达式 - * a b + c d 对应的中缀表达式是？

{{ select(10) }}

• $a \times (b - c) + d$
• $a \times b - (c + d)$
• $(a - b) \times (c + d)$
• $a \times (b + c) - d$

---

11. 递归函数定义如下：

f(0)=0
f(n)=n+f(n/2)  (n>0, / 表示整数除法)

{{ select(11) }}

• 15
• 17
• 18
• 20

---

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

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

{{ select(12) }}

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

---

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

string s = "csp";
s[1] = '+';
cout << s;

{{ select(13) }}

• csp
• c+p
• +sp
• 程序无法通过编译

---

14. 在升序数组 $[1, 3, 5, 7, 9]$ 中，使用二分查找第一个大于等于 6 的元素，其值为？

{{ select(14) }}

• 5
• 6
• 7
• 9

---

15. 下面哪一个不是操作系统？

{{ select(15) }}

• Linux
• Windows
• macOS
• Python

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

阅读程序（一）

#include <iostream>
using namespace std;

int md[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool lp(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}

int main() {
    int y, m, d;
    cin >> y >> m >> d;

    if (lp(y))
        md[2] = 29;

    int s = 0;

    for (int i = 1; i < m; i++)
        s += md[i];

    s += d;

    cout << s << endl;
    return 0;
}

假设输入的日期合法。

判断题

---

16. 当输入为 2024 3 1 时，程序输出为 61。

{{ select(16) }}

• 正确
• 错误

---

17. 当输入为 1900 3 1 时，程序输出为 61。

{{ select(17) }}

• 正确
• 错误

---

18. 当输入为 2023 12 31 时，程序输出为 365。

{{ select(18) }}

• 正确
• 错误

单项选择题

---

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

{{ select(19) }}

• 58
• 59
• 60
• 61

---

20. 若只考虑变量 $m$ 对循环次数的影响，该程序中求和循环的时间复杂度为？

{{ select(20) }}

• $O(1)$
• $O(m)$
• $O(d)$
• $O(y)$

阅读程序（二）

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

int st[105], tp;

int main() {
    string s;
    cin >> s;

    for (int i = 0; i < s.size(); i++) {
        char c = s[i];

        if ('0' <= c && c <= '9') {
            st[tp++] = c - '0';
        } else {
            int b = st[--tp];
            int a = st[--tp];

            if (c == '+')
                st[tp++] = a + b;
            else if (c == '-')
                st[tp++] = a - b;
            else if (c == '*')
                st[tp++] = a * b;
            else
                st[tp++] = a / b;
        }
    }

    cout << st[0] << endl;
    return 0;
}

假设输入是合法的后缀表达式，只包含一位数字和 +、-、*、/ 四种运算符，并且不会出现除以 0。

判断题

---

21. 当输入为 23+ 时，程序输出为 5。

{{ select(21) }}

• 正确
• 错误

---

22. 该程序用于计算前缀表达式的值。

{{ select(22) }}

• 正确
• 错误

---

23. 对合法输入，程序运行过程中不会出现从空栈中取元素的情况。

{{ select(23) }}

• 正确
• 错误

单项选择题

---

24. 当输入为 23+4* 时，程序输出为？

{{ select(24) }}

• 14
• 17
• 20
• 24

---

25. 当输入为 82/3- 时，程序输出为？

{{ select(25) }}

• 1
• 2
• 3
• 4

---

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

{{ select(26) }}

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

阅读程序（三）

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

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

    int f = 0;
    int ans = -1000000000;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        if (f < 0)
            f = x;
        else
            f += x;

        ans = max(ans, f);
    }

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

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

判断题

---

27. 如果输入的所有数都为负数，程序输出其中最大的一个数。

{{ select(27) }}

• 正确
• 错误

---

28. 每次循环结束后，变量 $f$ 表示以当前读入数字结尾的最大连续子段和。

{{ select(28) }}

• 正确
• 错误

---

29. 该程序允许选择空子段，因此答案可能为 $0$。

{{ select(29) }}

• 正确
• 错误

单项选择题

---

30. 若输入为：

5
1 -2 3 4 -1

{{ select(30) }}

• 5
• 6
• 7
• 8

---

31. 若输入为：

6
-3 -1 -2 -5 -4 -6

{{ select(31) }}

• -1
• 0
• 1
• 3

---

32. 若输入为：

8
2 -1 3 -5 4 -2 6 -1

{{ select(32) }}

• 5
• 6
• 7
• 8

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

完善程序（一）

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

数组下标从 0 开始。

#include <iostream>
using namespace std;

int a[1005];

int fd(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 = fd(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) }}

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

---

37. ⑤ 处应填？

{{ select(37) }}

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

完善程序（二）

下面程序统计一个由 . 和 # 构成的网格中，从给定起点出发能够到达的 . 格子数量。每次可以向上下左右移动一格，只能经过 .。请补全程序。

#include <iostream>
using namespace std;

char s[105][105];
int vis[105][105];
int n, m, ans;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int x, int y) {
    ①;
    ②;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (③ && ④)
            ⑤;
    }
}

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> s[i][j];

    cin >> sx >> sy;

    if (s[sx][sy] == '.')
        dfs(sx, sy);

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

---

38. ① 处应填？

{{ select(38) }}

• vis[x][y] = 1
• vis[n][m] = 1
• s[x][y] = '#'
• ans = 0

---

39. ② 处应填？

{{ select(39) }}

• ans--
• ans++
• x++
• y++

---

40. ③ 处应填？

{{ select(40) }}

• nx >= 0 && nx <= n && ny >= 0 && ny <= m
• nx >= 1 && nx < n && ny >= 1 && ny < m
• nx >= 1 && nx <= n && ny >= 1 && ny <= m
• nx > n || ny > m

---

41. ④ 处应填？

{{ select(41) }}

• !vis[nx][ny] && s[nx][ny] == '.'
• vis[nx][ny] && s[nx][ny] == '.'
• !vis[x][y] && s[x][y] == '#'
• s[nx][ny] == '#'

---

42. ⑤ 处应填？

{{ select(42) }}

• dfs(x, y)
• dfs(nx, y)
• dfs(x, ny)
• dfs(nx, ny)