2026 CSP-J 初赛模拟第 1 套

本卷共 42 题，总分 100 分。

一、单项选择题

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

1. 在 C++ 中，若希望函数内的局部变量在多次函数调用之间保留上一次的值，应使用哪个关键字？

{{ select(1) }}

• const
• static
• extern
• register

2. 二进制数 $110101_2$ 与十六进制数 $1A_{16}$ 的和对应的十进制值是？

{{ select(2) }}

• 67
• 75
• 79
• 83

3. 已知 int x = 5;，下面哪一项可以正确声明一个引用变量 r，使其引用 x？

{{ select(3) }}

• int r = &x;
• int &r = x;
• int *r = x;
• int &&r = &x;

4. 一个空栈依次将 $1, 2, 3, 4, 5$ 入栈，下面哪个序列不可能作为出栈序列？

{{ select(4) }}

• $2, 1, 4, 5, 3$
• $3, 2, 1, 5, 4$
• $4, 1, 3, 2, 5$
• $1, 2, 3, 4, 5$

5. 一棵有 31 个结点的满二叉树，其叶子结点个数为？

{{ select(5) }}

• 8
• 12
• 15
• 16

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

{{ select(6) }}

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

7. 一个有 8 个顶点、10 条边的无向连通图，至少删除多少条边后可以变成一棵树？

{{ select(7) }}

• 1
• 2
• 3
• 4

8. 下列排序算法的常见实现中，通常不稳定的是？

{{ select(8) }}

• 冒泡排序
• 简单选择排序
• 直接插入排序
• 归并排序

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

{{ select(9) }}

• 21
• 28
• 31
• 35

10. 后缀表达式 3 4 + 5 * 6 - 对应的中缀表达式是？

{{ select(10) }}

• $3 + 4 \times 5 - 6$
• $(3 + 4) \times (5 - 6)$
• $(3 + 4) \times 5 - 6$
• $3 + 4 \times (5 - 6)$

11. 在 C++ 中，表达式 (char)('A' + 5) 的值是？

{{ select(11) }}

• 'E'
• 'F'
• 'G'
• '5'

12. 采用每轮进行一次关键字比较、随后将搜索区间缩小约一半的标准二分查找，对含有 2026 个元素的有序数组查找一个元素，最坏情况下最多比较多少次？

{{ select(12) }}

• 9
• 10
• 11
• 12

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

{{ select(13) }}

• 12
• 18
• 24
• 30

14. 有 6 个字符，其出现频率分别为 $5, 7, 10, 15, 20, 43$。若用哈夫曼编码，频率为 7 的字符编码长度为？

{{ select(14) }}

• 1
• 2
• 3
• 4

15. 下面哪一个通常不是编译器？

{{ select(15) }}

• GCC
• Clang
• MSVC
• Chrome

二、阅读程序

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

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

阅读程序（一）

#include <iostream>
using namespace std;

int f(int x) {
    int s = 0;
    while (x) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

int g(int x) {
    int r = 0;
    while (x) {
        r = r * 10 + x % 10;
        x /= 10;
    }
    return r;
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << " " << g(n) << endl;
    return 0;
}

假设输入的 $n$ 是不超过 1000000 的正整数。

判断题

16. 当输入为 1203 时，程序输出为 6 3021。

{{ select(16) }}

• 正确
• 错误

17. 对任意合法输入 $n$，都有 $g(g(n)) = n$。

{{ select(17) }}

• 正确
• 错误

18. 对任意合法输入 $n$，都有 $f(n) = f(g(n))$。

{{ select(18) }}

• 正确
• 错误

单项选择题

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

{{ select(19) }}

• 3 200100
• 3 2001
• 4 2001
• 4 1002

20. 该程序的时间复杂度最准确地表示为？

{{ select(20) }}

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

阅读程序（二）

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

bool ck(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char t = st.top();
            st.pop();

            if (c == ')' && t != '(') return false;
            if (c == ']' && t != '[') return false;
            if (c == '}' && t != '{') return false;
        }
    }
    return st.empty();
}

int main() {
    string s;
    cin >> s;
    cout << ck(s) << endl;
    return 0;
}

假设输入字符串只包含 (、)、[、]、{、} 这 6 种字符。

判断题

21. 当输入为 ([]{}) 时，程序输出为 1。

{{ select(21) }}

• 正确
• 错误

22. 只要字符串中每种左括号和右括号数量分别相等，程序就一定输出 1。

{{ select(22) }}

• 正确
• 错误

23. 若程序输出为 1，则输入字符串长度一定是偶数。

{{ select(23) }}

• 正确
• 错误

单项选择题

24. 当输入为 ([)] 时，程序输出为？

{{ select(24) }}

• 0
• 1
• true
• false

25. 当输入为 {[()][]} 时，程序输出为？

{{ select(25) }}

• 0
• 1
• 8
• false

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

{{ select(26) }}

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

阅读程序（三）

#include <iostream>
using namespace std;

int a[10][10], dp[10][10];

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];

    if (a[1][1]) dp[1][1] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!a[i][j]) {
                dp[i][j] = 0;
                continue;
            }
            if (i == 1 && j == 1) continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

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

假设 $1 \le n, m \le 8$，输入的 $a_{ij}$ 只可能为 0 或 1。其中 1 表示该格子可以经过，0 表示该格子不能经过。

判断题

27. 如果 $a_{11} = 0$，程序一定输出 0。

{{ select(27) }}

• 正确
• 错误

28. 程序中的 $dp_{ij}$ 表示从左上角走到位置 $(i, j)$ 的合法路径数量。

{{ select(28) }}

• 正确
• 错误

29. 若将两层循环改为外层枚举 $j$，内层枚举 $i$，程序输出结果总是不变。

{{ select(29) }}

• 正确
• 错误

单项选择题

30. 若输入为：

3 3
1 1 1
1 1 1
1 1 1

程序输出为？

{{ select(30) }}

• 3
• 4
• 6
• 9

31. 若输入为：

3 4
1 1 1 1
0 1 0 1
1 1 1 1

程序输出为？

{{ select(31) }}

• 1
• 2
• 3
• 4

32. 若 $n = m = 4$，且所有 $a_{ij}$ 都为 1，程序输出为？

{{ select(32) }}

• 12
• 16
• 20
• 24

三、完善程序

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

完善程序（一）

下面程序使用插入排序将数组从小到大排序，请补全程序。

#include <iostream>
using namespace std;

int a[1005];

void ins(int n) {
    for (int i = 1; i < n; i++) {
        int x = a[i];
        int j = ①;
        while (j >= 0 && ②) {
            a[j + 1] = ③;
            ④;
        }
        ⑤;
    }
}

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

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

    ins(n);

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

    return 0;
}

33. ① 处应填？

{{ select(33) }}

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

34. ② 处应填？

{{ select(34) }}

• a[j] < x
• a[j] > x
• a[i] > x
• j > x

35. ③ 处应填？

{{ select(35) }}

• a[j + 1]
• x
• a[j]
• a[i]

36. ④ 处应填？

{{ select(36) }}

• i++
• j++
• i--
• j--

37. ⑤ 处应填？

{{ select(37) }}

• a[j] = x
• a[j + 1] = x
• a[i + 1] = x
• x = a[j + 1]

完善程序（二）

下面程序用数组模拟一个队列，支持三种操作：

• 1 x：将 $x$ 加入队尾；
• 2：若队列非空，弹出队首；
• 3：若队列非空，输出队首元素，否则输出 empty。

请补全程序。

#include <iostream>
using namespace std;

int q[1005];
int hd = 0, tl = 0;

void ps(int x) {
    q[①] = x;
    ②;
}

void pp() {
    if (③) ④;
}

bool em() {
    return ⑤;
}

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

    while (m--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            ps(x);
        } else if (op == 2) {
            pp();
        } else {
            if (em()) cout << "empty" << endl;
            else cout << q[hd] << endl;
        }
    }

    return 0;
}

假设操作次数不超过 1000，不会因为入队次数过多导致数组越界。

38. ① 处应填？

{{ select(38) }}

• hd
• tl
• tl + 1
• hd + 1

39. ② 处应填？

{{ select(39) }}

• hd++
• tl++
• hd--
• tl--

40. ③ 处应填？

{{ select(40) }}

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

41. ④ 处应填？

{{ select(41) }}

• tl++
• hd++
• tl--
• hd--

42. ⑤ 处应填？

{{ select(42) }}

• hd < tl
• hd > tl
• hd == tl
• q[hd] == q[tl]