一、单项选择题(每题 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$ 与二进制数 $1 0 1 1 0_{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 * b - c + d$
• $a * b - (c + d)$
• $(a * b - c) + d$
• $a * (b - c + d)$

11. 递归函数定义如下:

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

则 f(10) 的值为?

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

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填“$\surd$”,错误填“$\times$”。

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。其中第 $16\sim 18$ 题每题 $2$ 分,第 $32$ 题 $4$ 分。

阅读程序(一)

下面程序计算给定日期是该年的第几天。输入保证是合法公历日期。

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

(程序 1,每题 2 分)

(1) 当输入为 $2024$ $3$ $1$ 时,程序输出为 $61$。

{{ select(16) }}

• 正确
• 错误

(2) 当输入为 $1900$ $3$ $1$ 时,程序输出为 $61$。

{{ select(17) }}

• 正确
• 错误

(3) 当输入为 $2023$ $12$ $31$ 时,程序输出为 $365$。

{{ select(18) }}

• 正确
• 错误

(4) 当输入为 $2026$ $2$ $28$ 时,程序输出为?

{{ select(19) }}

• $58$
• $59$
• $60$
• $61$

(5) 该程序主要循环部分的时间复杂度最准确地表示为?

{{ select(20) }}

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

阅读程序(二)

假设输入是合法的后缀表达式,只包含一位数字和运算符 + - * /,除法为整除且不会除以 $0$。

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

(程序 2,每题 1.5 分)

(1) 当输入为 23+ 时,程序输出为 $5$。

{{ select(21) }}

• 正确
• 错误

(2) 该程序计算的是前缀表达式的值。

{{ select(22) }}

• 正确
• 错误

(3) 对合法输入,运算符执行时栈中至少有两个元素。

{{ select(23) }}

• 正确
• 错误

(4) 当输入为 23+4* 时,程序输出为?

{{ select(24) }}

• $14$
• $17$
• $20$
• $24$

(5) 当输入为 82/3- 时,程序输出为?

{{ select(25) }}

• $1$
• $2$
• $3$
• $4$

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

{{ select(26) }}

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

阅读程序(三)

下面程序求序列的最大连续段和。假设 $1 \leq n \leq 100$,整数均在 int 范围内。

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

(程序 3,每题 1.5 分)

(1) 当 $n=1$ 时,程序输出就是那唯一的数。

{{ select(27) }}

• 正确
• 错误

(2) 每次循环结束后,变量 $f$ 表示以当前元素结尾的最大连续段和。

{{ select(28) }}

• 正确
• 错误

(3) 若序列全为负数,程序输出一定为 $0$。

{{ select(29) }}

• 正确
• 错误

(4) 若输入为:

5
1 -2 3 4 -1

程序输出为?

{{ select(30) }}

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

(5) 若输入为:

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

程序输出为?

{{ select(31) }}

• $-1$
• $0$
• $1$
• $3$

(6) 若输入为:

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

程序输出为?

{{ select(32) }}

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

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

完善程序(一)

下面程序在非降序数组中查找最后一个小于等于 $x$ 的元素下标(从 $0$ 开始)。若不存在,输出 $-1$。请补全程序。

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

(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) }}

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

(5) ⑤ 处应填( )

{{ select(37) }}

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

完善程序(二)

下面程序统计 $n \times m$ 网格中,从给定起点出发能走到的 . 格子个数。每步上下左右走一格,不能走 #。请补全程序。

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

(1) ① 处应填( )

{{ select(38) }}

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

(2) ② 处应填( )

{{ select(39) }}

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

(3) ③ 处应填( )

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

(4) ④ 处应填( )

{{ select(41) }}

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

(5) ⑤ 处应填( )

{{ select(42) }}

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