2026 CSPJ 初赛模拟 2（JH）

本卷共 42 题，总分 100 分，建议用时 90 分钟。

一、单项选择题

共 15 题，每题 2 分，共 30 分。

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

int x = 1;

for (int i = 1; i <= 4; i++)
    x = x * 2 + i;

cout << x;

{{ select(1) }}

• 31
• 42
• 46
• 63

2. 十六进制数 $3A_{16}$ 加上十进制数 6，结果的十进制表示是（ ）。

{{ select(2) }}

• 60
• 62
• 64
• 66

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

int x = 0, y = 0;
if (++x || ++y)
    cout << x << " " << y;

{{ select(3) }}

• 0 0
• 1 0
• 1 1
• 2 1

4. 下面程序输出（ ）。

void f(int &x) { x *= 2; }
int main() { int a = 5; f(a); cout << a; }

{{ select(4) }}

• 5
• 7
• 10
• 20

5. 如果一棵二叉树有 9 个叶子结点、7 个只有一个孩子的结点，则这棵二叉树共有多少个结点？

{{ select(5) }}

• 22
• 23
• 24
• 25

6. $84$ 与 $126$ 的最大公约数是（ ）。

{{ select(6) }}

• 14
• 21
• 28
• 42

7. 一棵非空二叉树中每个内部结点都恰有两个孩子。若叶结点有 11 个，则内部结点有（ ）个。

{{ select(7) }}

• 9
• 10
• 11
• 12

8. 在所有边权均为 1 的图中求从起点到各点经过的最少边数，最合适的基础数据结构是（ ）。

{{ select(8) }}

• 栈
• 队列
• 最小堆
• 并查集

9. 元素 1、2、3、4 依次进栈，允许进栈和出栈交替。下面不可能得到的出栈序列是（ ）。

{{ select(9) }}

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

10. 归并排序在最坏情况下的时间复杂度是（ ）。

{{ select(10) }}

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

11. 用左闭右开区间 [l,r) 二分查找第一个大于等于 x 的位置时，正确的循环不变量是（ ）。

{{ select(11) }}

• 答案始终在 [l,r) 中
• 答案始终小于 l
• 答案始终大于等于 r
• 区间内所有元素都小于 x

12. 向一个空的最小堆依次插入 7、3、5、1，删除堆顶后，新的堆顶是（ ）。

{{ select(12) }}

• 1
• 3
• 5
• 7

13. 下列软件中属于操作系统的是（ ）。

{{ select(13) }}

• Ubuntu
• GCC
• Visual Studio Code
• Chrome

14. 执行 string s="algorithm"; cout << s.find("go");，输出为（ ）。

{{ select(14) }}

• 1
• 2
• 3
• string::npos

15. 1 到 100 中，能被 3 或 5 整除的整数共有（ ）个。

{{ select(15) }}

• 40
• 46
• 47
• 53

二、阅读程序

程序输入不超过数组或字符串定义的范围。判断题正确填 “✓”，错误填 “✗”。

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

阅读程序（一）

#include <iostream>
using namespace std;

int a[105];

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

    for (int i = 1; i <= n; i++)
        a[i] = 1;

    int p = 0, c = 0, t = 0;

    while (c < n - 1) {
        p++;
        if (p > n)
            p = 1;

        if (!a[p])
            continue;

        t++;

        if (t == k) {
            a[p] = 0;
            c++;
            t = 0;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (a[i])
            cout << i << endl;
    }

    return 0;
}

假设 $1 \le n \le 100$，$1 \le k \le 100$。

判断题

16. 当输入为 5 2 时，程序输出为 3。

{{ select(16) }}

• 正确
• 错误

17. 当 $k = 1$ 时，程序输出一定为 $n$。

{{ select(17) }}

• 正确
• 错误

18. 每次有一个位置被删除后，变量 $t$ 都会被重新赋值为 0。

{{ select(18) }}

• 正确
• 错误

单项选择题

19. 当输入为 6 3 时，程序输出为？

{{ select(19) }}

• 1
• 2
• 5
• 6

20. 当输入为 7 3 时，程序输出为？

{{ select(20) }}

• 1
• 3
• 4
• 7

阅读程序（二）

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

int a[15][15], dp[15][15];

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

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

    dp[1][1] = a[1][1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1)
                continue;

            if (i == 1)
                dp[i][j] = dp[i][j - 1] + a[i][j];
            else if (j == 1)
                dp[i][j] = dp[i - 1][j] + a[i][j];
            else
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

假设 $1 \le n, m \le 10$，输入的所有 $a_{ij}$ 均为正整数。

判断题

21. 程序输出的路径代价包含起点 $(1, 1)$ 和终点 $(n, m)$ 的权值。

{{ select(21) }}

• 正确
• 错误

22. 程序中的 $dp_{ij}$ 表示从 $(1, 1)$ 走到 $(i, j)$ 的最小代价。

{{ select(22) }}

• 正确
• 错误

23. 程序允许从一个格子向上或向左移动。

{{ select(23) }}

• 正确
• 错误

单项选择题

24. 若输入为：

3 3
1 3 1
1 5 1
4 2 1

程序输出为？

{{ select(24) }}

• 5
• 6
• 7
• 8

25. 若输入为：

2 4
2 1 3 4
5 1 1 1

程序输出为？

{{ select(25) }}

• 5
• 6
• 7
• 8

26. 该程序的时间复杂度为？

{{ select(26) }}

• $O(n)$
• $O(m)$
• $O(nm)$
• $O(n^2 m)$

阅读程序（三）

#include <iostream>
using namespace std;

int ch[105][105], c[105];
int sz[105], dep[105];

void dfs(int u) {
    sz[u] = 1;

    for (int i = 1; i <= c[u]; i++) {
        int v = ch[u][i];
        dep[v] = dep[u] + 1;
        dfs(v);
        sz[u] += sz[v];
    }
}

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

    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        ch[f][++c[f]] = i;
    }

    dep[1] = 1;
    dfs(1);

    cin >> x;
    cout << dep[x] << " " << sz[x] << endl;

    return 0;
}

假设输入表示一棵以 1 为根的有根树，且对任意 $i > 1$，父亲编号都小于 $i$。

判断题

27. 程序执行完 dfs(1) 后，$sz_1$ 一定等于 $n$。

{{ select(27) }}

• 正确
• 错误

28. 程序中根结点 1 的深度为 $0$。

{{ select(28) }}

• 正确
• 错误

29. $sz_x$ 表示以 $x$ 为根的子树中结点数量，并且包含 $x$ 本身。

{{ select(29) }}

• 正确
• 错误

单项选择题

30. 若输入为：

7
1 1 2 2 3 3
2

程序输出为？

{{ select(30) }}

• 1 3
• 2 3
• 3 2
• 2 7

31. 若输入为：

9
1 1 2 2 4 4 5 5
4

程序输出为？

{{ select(31) }}

• 2 3
• 2 7
• 3 3
• 4 1

32. 若输入为：

9
1 1 2 2 4 4 5 5
2

程序输出为？

{{ select(32) }}

• 1 9
• 2 3
• 2 7
• 3 7

三、完善程序

单项选择题，每题 3 分，共 30 分。

完善程序（一）

下面程序使用冒泡排序将数组从小到大排序。若某一轮没有发生交换，则提前结束排序。请补全程序。

#include <iostream>
using namespace std;

int a[1005];

void bub(int n) {
    for (int i = 0; i < n - 1; i++) {
        bool ok = true;

        for (int j = 0; j < ①; j++) {
            if (②) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                ③;
            }
        }

        if (④)
            ⑤;
    }
}

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

    for (int i = 0; i < n; i++)
        cin >> a[i];

    bub(n);

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

33. ① 处应填？

{{ select(33) }}

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

34. ② 处应填？

{{ select(34) }}

• a[j] < a[j + 1]
• a[j] > a[j + 1]
• a[i] > a[j]
• j > i

35. ③ 处应填？

{{ select(35) }}

• ok = true
• ok = false
• i++
• j--

36. ④ 处应填？

{{ select(36) }}

• ok
• !ok
• i == n - 1
• a[i] == a[i + 1]

37. ⑤ 处应填？

{{ select(37) }}

• continue
• return false
• i--
• break

完善程序（二）

下面程序求一个由 . 和 # 构成的网格中，从 $(1, 1)$ 到 $(n, m)$ 的最短步数。每次可以向上下左右移动一格，只能经过 .。若无法到达，输出 -1。请补全程序。

#include <iostream>
using namespace std;

char s[105][105];
int d[105][105];
int qx[10005], qy[10005];

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

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

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

    int hd = 0, tl = 0;

    if (s[1][1] == '.') {
        ①;
        qx[tl] = 1;
        qy[tl++] = 1;
    }

    while (②) {
        int x = qx[hd];
        int y = qy[hd];
        hd++;

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

            if (③ && s[nx][ny] == '.' && ④) {
                d[nx][ny] = ⑤;
                qx[tl] = nx;
                qy[tl++] = ny;
            }
        }
    }

    cout << d[n][m] << endl;
    return 0;
}

38. ① 处应填？

{{ select(38) }}

• d[1][1] = 0
• d[1][1] = 1
• d[n][m] = 0
• d[n][m] = 1

39. ② 处应填？

{{ select(39) }}

• hd > tl
• hd < tl
• hd == tl
• tl == 0

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

• d[nx][ny] == -1
• d[nx][ny] != -1
• d[x][y] == -1
• d[x][y] > d[nx][ny]

42. ⑤ 处应填？

{{ select(42) }}

• d[x][y]
• d[x][y] - 1
• d[nx][ny] + 1
• d[x][y] + 1