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

1. 已知前序遍历序列为 $ABDCEF$,中序遍历序列为 $DBAECF$,则后序遍历为( )

{{ select(1) }}

• $DBEFCA$
• $DBEACF$
• $DBAECF$
• $DBECFA$

2. 哈希表采用链地址法解决冲突,若哈希函数为 $h(\mathrm{key})=\mathrm{key} \bmod 7$,插入序列 $50,20,35,15,8,29$,则哈希表中链表最长的长度为( )

{{ select(2) }}

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

3. 若有 $n$ 个元素的序列,采用冒泡排序,最少比较次数为( )

{{ select(3) }}

• $n(n-1)/2$
• $n$
• $n-1$
• $n^2$

4. 一个循环队列的队首和队尾指针分别为 $\mathrm{front}$ 和 $\mathrm{rear}$,数组容量为 $m$,则队列长度为( )

{{ select(4) }}

• $(\mathrm{rear}-\mathrm{front}+m) \bmod m$
• $\mathrm{rear}-\mathrm{front}$
• $\mathrm{rear}-\mathrm{front}+1$
• $(\mathrm{rear}-\mathrm{front}+1) \bmod m$

5. 高度为 $4$ 的平衡二叉树(AVL 树),最少包含的结点数为( )

{{ select(5) }}

• $9$
• $8$
• $10$
• $7$

6. 已知递归函数: $f(0)=0$, $f(1)=1$, $f(n)=2\cdot f(n-1)+f(n-2)$,则 $f(5)$ 的值为( )

{{ select(6) }}

• $34$
• $29$
• $24$
• $31$

7. 逻辑表达式 !(a && b) || (a || !b) 的恒等结果为( )

{{ select(7) }}

• 恒真
• 恒假
• $a$
• $b$

8. 快速排序在最坏情况下的时间复杂度和空间复杂度分别是( )

{{ select(8) }}

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

9. 模 $17$ 意义下,$5$ 的乘法逆元为( )

{{ select(9) }}

• $11$
• $7$
• $15$
• $13$

10. 十进制小数 $0.625$ 转换为二进制小数为( )

{{ select(10) }}

• $0.110$
• $0.011$
• $0.101$
• $0.111$

11. 字符串 "noip2026" 的非空子串个数为( )

{{ select(11) }}

• $35$
• $36$
• $37$
• $38$

12. 完全无向图 $G$ 有 $6$ 个顶点,删除( )条边可得到一棵树

{{ select(12) }}

• $9$
• $7$
• $8$
• $10$

13. 将中缀表达式 a + b * c + d 转为后缀表达式,结果为( )

{{ select(13) }}

• a b + c * d +
• a b c + d * +
• a b c * + d +
• a b c * d + +

14. 从 $5$ 双不同的鞋子中任取 $4$ 只,恰有 $2$ 只配成一双的取法数为( )

{{ select(14) }}

• $120$
• $240$
• $60$
• $180$

15. 下列编码中,属于前缀码的是( )

{{ select(15) }}

• $\{00,01,10,1\}$
• $\{0,01,011,0111\}$
• $\{00,010,011,100\}$
• $\{1,11,111,1111\}$

程序输入不超过数组或字符串定义的范围。

除特殊说明外,判断题每题 $1.5$ 分,选择题每题 $3$ 分,共 $40$ 分。判断题正确填「正确」,错误填「错误」。

阅读程序(一)

#include <bits/stdc++.h>
using namespace std;
int n, a, ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        ans ^= a;
    }
    printf("%d", ans);
    return 0;
}

(1) 若输入为 4 1 2 3 4,程序输出为 $4$。

{{ select(16) }}

• 正确
• 错误

(2) 若输入为 9 2 2 1 3 3 3 2 3 1,程序输出为 $3$。( $2$ 分)

{{ select(17) }}

• 正确
• 错误

(3) 程序输出结果的范围在 $[-2147483648,2147483647]$ 之间。

{{ select(18) }}

• 正确
• 错误

(4) 若输入为 6 1 1 2 2 3 3,程序输出为:

{{ select(19) }}

• $1$
• $0$
• $2$
• $3$

(5) 以下哪个输入会使程序输出 $9$?

{{ select(20) }}

• 3 3 1 4
• 4 2 0 2 6
• 4 9 5 2 7
• 8 6 2 9 5 1 4 1 3

(6) 程序执行过程中,若输入为 3 7 7 7,则 ans 的变化过程为:

{{ select(21) }}

• $0 \to 7 \to 0 \to 7$
• $0 \to 7 \to 14 \to 21$
• $0 \to 7 \to 0 \to 0$
• $0 \to 7 \to 7 \to 7$

阅读程序(二)

#include <bits/stdc++.h>
using namespace std;
int n;
char lson[30], rson[30];
void preOrder(char u) {
    if (u == '*') return;
    cout << u;
    preOrder(lson[u - 'a']);
    preOrder(rson[u - 'a']);
}
int main() {
    cin >> n;
    char root;
    for (int i = 1; i <= n; ++i) {
        char fa, l, r;
        cin >> fa >> l >> r;
        if (i == 1) root = fa;
        int idx = fa - 'a';
        lson[idx] = l;
        rson[idx] = r;
    }
    preOrder(root);
    return 0;
}

(1) 函数 preOrder 的遍历顺序是:左子树 $\to$ 根结点 $\to$ 右子树。

{{ select(22) }}

• 正确
• 错误

(2) 变量 $n$ 代表二叉树叶子结点的数量。( $2$ 分)

{{ select(23) }}

• 正确
• 错误

(3) 递归函数 preOrder 会存在栈溢出风险,当二叉树退化成单链且深度超过递归栈上限时。

{{ select(24) }}

• 正确
• 错误

(4) 将 preOrder(lson[...]) 和 preOrder(rson[...]) 交换位置,输出序列变为中序遍历。

{{ select(25) }}

• 正确
• 错误

(5) 若输入如下,下列说法正确的是:

2
a b *
b * *

{{ select(26) }}

• 输出为 ab
• 输出为 ba
• 程序会发生数组越界
• 程序会死循环

(6) 若输入如下,程序输出的结果是:

6
abc
bdi
cj*
d**
i**
j**

{{ select(27) }}

• adbicj
• adbcij
• abdcij
• abdicj

阅读程序(三)

#include <bits/stdc++.h>
using namespace std;
int n, val[105];
long long dp[105][105];
int root[105][105];

void print(int l, int r) {
    if (l > r) return;
    int k = root[l][r];
    cout << k << " ";
    print(l, k - 1);
    print(k + 1, r);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
        dp[i][i] = val[i];
        root[i][i] = i;
    }
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = 0;
            for (int k = l; k <= r; ++k) {
                long long left = (l > k - 1) ? 1 : dp[l][k - 1];
                long long right = (k + 1 > r) ? 1 : dp[k + 1][r];
                long long now = left * right + val[k];
                if (now > dp[l][r]) {
                    dp[l][r] = now;
                    root[l][r] = k;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    print(1, n);
    return 0;
}

(1) print(l,r) 函数输出顺序是二叉树的后序遍历。

{{ select(28) }}

• 正确
• 错误

(2) 交换 print(l,k-1) 和 print(k+1,r) 的调用顺序,输出变为根 $\to$ 右 $\to$ 左。

{{ select(29) }}

• 正确
• 错误

(3) 该算法的时间复杂度为 $O(n^3)$。

{{ select(30) }}

• 正确
• 错误

(4) 若输入 $n=6$, $\mathrm{val}=[1,2,3,4,5,6]$,则输出最大加分为:

{{ select(31) }}

• $65$
• $95$
• $75$
• $85$

(5) 函数 print 在输出时,若某结点无左子树,则:

{{ select(32) }}

• 输出 $0$
• 什么也不输出
• 输出 $-1$
• 递归终止

(6) 若 $n=6$, $\mathrm{val}=[-1,-2,-3,-4,-5,-6]$,程序输出最大加分为:

{{ select(33) }}

• $-21$
• $-13$
• $13$
• $21$

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

完善程序(一)

P11963 [GESP202503 六级] 环线

地铁环线有 $n$ 个车站,依次以 $1,2,\ldots,n$ 标号。车站 $i$($1 \le i < n$)的下一个车站是 $i+1$,车站 $n$ 的下一个是 $1$。从小 A 某个车站出发到某个车站结束,至少经过一个车站,且不会经过同一车站多次。经过车站 $i$ 获得快乐值 $a_i$。求一段行程快乐值之和的最大值。

第一行正整数 $n$。第二行 $n$ 个整数 $a_i$。输出一个整数,表示最大快乐值。

样例:

5
-3 4 -5 1 3

5

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n;
long long a[N], pre[N];
int q[N], ql, qr;
long long ans;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a[n + i] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++) {
        ①;
    }
    ql = qr = 1;
    ans = -1e18;
    for (int i = 1; i <= 2 * n; i++) {
        while (②) {
            ql++;
        }
        ans = max(ans, ③);
        while (④) {
            qr--;
        }
        ⑤;
    }
    printf("%lld\n", ans);
    return 0;
}

(1) ① 处应填( )

{{ select(34) }}

• pre[i] = pre[i - 1] + a[i]
• pre[i] = pre[i] + a[i - 1]
• pre[i] = pre[i - 1] + a[i - 1]
• pre[i] = pre[i] + a[i]

(2) ② 处应填( )

{{ select(35) }}

• ql <= qr && q[ql] < pre[q[ql]]
• ql <= qr && q[ql] < pre[q[qr]]
• ql <= qr && q[ql] < q[qr]
• ql <= qr && q[ql] < i - n

(3) ③ 处应填( )

{{ select(36) }}

• pre[i] - q[qr]
• pre[i] - q[ql]
• pre[i] - pre[q[qr]]
• pre[i] - pre[q[ql]]

(4) ④ 处应填( )

{{ select(37) }}

• ql <= qr && pre[i] < pre[q[ql]]
• ql <= qr && pre[i] < pre[q[qr]]
• ql <= qr && pre[i] < q[ql]
• ql <= qr && pre[i] < q[qr]

(5) ⑤ 处应填( )

{{ select(38) }}

• q[qr] = i
• q[ql] = i
• q[++qr] = i
• q[++ql] = i

完善程序(二)

B4279 [蓝桥杯青少年组国赛 2023] 数独填数

玩家需要根据 $9 \times 9$ 网格上的已知数字,将剩余空格填上数字,使得每一行、每一列、每一个 $3 \times 3$ 方块都包含 $1\sim 9$ 且不重复。输入 $9$ 行,每行 $9$ 个字符(数字或 .)。保证有唯一解。输出 $9$ 行已完成的数独,每行 $9$ 个数字,数字之间无空格。

样例:

17.5..8..
.52.1....
.....759.
.8...94.3
.197.4..8
7......15
4.1...6..
3...2..59
...96..3.

174593826
952816347
638247591
286159473
519734268
743682915
491375682
367428159
825961734

下面程序请补全。

#include <bits/stdc++.h>
using namespace std;
char g[9][9];
bool row[9][10], col[9][10], box[9][10];
bool found;

void dfs(int x, int y) {
    if (found) return;
    if (x == 9) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j)
                cout << g[i][j];
            cout << endl;
        }
        found = true;
        return;
    }
    if (y == 9) {
        ①;
        return;
    }
    if (g[x][y] != '.') {
        ②;
        return;
    }
    for (int num = 1; num <= 9; ++num) {
        int b = x / 3 * 3 + y / 3;
        if (③) {
            g[x][y] = num + '0';
            row[x][num] = true;
            col[y][num] = true;
            box[b][num] = true;
            ④;
            g[x][y] = '.';
            row[x][num] = false;
            col[y][num] = false;
            box[b][num] = false;
        }
    }
}

int main() {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> g[i][j];
            if (g[i][j] != '.') {
                int num = g[i][j] - '0';
                int b = i / 3 * 3 + j / 3;
                row[i][num] = true;
                col[j][num] = true;
                box[b][num] = true;
            }
        }
    }
    ⑤;
    return 0;
}

(1) ① 处应填( )

{{ select(39) }}

• dfs(x, 0)
• dfs(x + 1, 0)
• dfs(x, y + 1)
• dfs(x + 1, y + 1)

(2) ② 处应填( )

{{ select(40) }}

• dfs(x + 1, y)
• dfs(x, y)
• dfs(x + 1, y + 1)
• dfs(x, y + 1)

(3) ③ 处应填( )

{{ select(41) }}

• row[x][num] && !col[y][num] && !box[b][num]
• !row[x][num] && col[y][num] && !box[b][num]
• !row[x][num] && !col[y][num] && box[b][num]
• !row[x][num] && !col[y][num] && !box[b][num]

(4) ④ 处应填( )

{{ select(42) }}

• dfs(x + 1, y)
• dfs(x + 1, y + 1)
• dfs(x, y + 1)
• dfs(x, y)

(5) ⑤ 处应填( )

{{ select(43) }}

• dfs(0, 0)
• dfs(0, 8)
• dfs(8, 0)
• dfs(8, 8)