2026 CSPJ 初赛模拟 1（JH）

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

一、单项选择题

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

1. 执行 int x = 3; cout << (x << 2);，输出为（ ）。

{{ select(1) }}

• 6
• 8
• 12
• 16

2. 下面程序的输出是（ ）。

int x = 0;
if (x != 0 && 10 / x > 1) cout << "A";
else cout << "B";

{{ select(2) }}

• A
• B
• 运行时除零错误
• 无法通过编译

3. 执行下面代码后，a.size() 的值是（ ）。

vector<int> a = {1, 2, 3};
a.push_back(4);

{{ select(3) }}

• 2
• 3
• 4
• 5

4. 在单链表中，已经持有结点 p 的指针和一个新结点 q。若只把 q 插到 p 之后，该操作的时间复杂度是（ ）。

{{ select(4) }}

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

5. 一个长度为 8 的数组实现循环队列，并约定始终空出一个位置来区分队空与队满。该队列最多同时保存（ ）个元素。

{{ select(5) }}

• 6
• 7
• 8
• 9

6. 一棵树共有 18 个结点，则它共有（ ）条边。

{{ select(6) }}

• 16
• 17
• 18
• 19

7. 后缀表达式 5 2 3 * + 4 - 的值是（ ）。

{{ select(7) }}

• 3
• 5
• 7
• 9

8. 下列排序算法中，在通常实现下是稳定排序的是（ ）。

{{ select(8) }}

• 堆排序
• 快速排序
• 归并排序
• 选择排序

9. 有向无环图包含边 $1\to3,2\to3,3\to4,2\to4$，它共有（ ）种拓扑排序。

{{ select(9) }}

• 1
• 2
• 3
• 4

10. 从编号 1 到 8 的位置中选 3 个，要求任意两个被选位置不相邻，共有（ ）种选法。

{{ select(10) }}

• 16
• 20
• 24
• 56

11. 已知 $f(1)=2$，且 $f(n)=2f(n-1)+1$，则 $f(4)$ 等于（ ）。

{{ select(11) }}

• 15
• 19
• 23
• 31

12. 大小为 7 的哈希表使用 h(x)=x%7 和线性探查。依次插入 10、17、24、31，元素 31 最终位于下标（ ）。

{{ select(12) }}

• 3
• 4
• 5
• 6

13. 下面代码的时间复杂度是（ ）。

for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; ++j)
        ++cnt;

{{ select(13) }}

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

14. 有 5 个字符，其出现频率分别为 $2, 3, 7, 9, 18$。若使用哈夫曼编码，则频率为 2 的字符编码长度为？

{{ select(14) }}

• 1
• 2
• 3
• 4

15. 下面哪个 STL 容器最适合描述 “先进先出” 的数据结构？

{{ select(15) }}

• stack
• queue
• set
• map

二、阅读程序

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

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

阅读程序（一）

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

string rot(string s, int k) {
    int n = s.size();
    k %= n;

    string t;
    for (int i = k; i < n; i++)
        t += s[i];

    for (int i = 0; i < k; i++)
        t += s[i];

    return t;
}

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

假设输入字符串非空，且只包含小写字母和数字。

判断题

16. 当输入为 abcde 2 时，程序输出为 cdeab。

{{ select(16) }}

• 正确
• 错误

17. 当 $k$ 是字符串长度的倍数时，程序输出一定与原字符串相同。

{{ select(17) }}

• 正确
• 错误

18. 该程序实现的是将字符串向右循环移动 $k$ 位。

{{ select(18) }}

• 正确
• 错误

单项选择题

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

{{ select(19) }}

• cspj2026
• 26cspj20
• pj2026cs
• 2026cspj

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

{{ select(20) }}

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

阅读程序（二）

#include <iostream>
using namespace std;

int v[105], w[105], dp[1005];

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

    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            if (dp[j] < dp[j - v[i]] + w[i])
                dp[j] = dp[j - v[i]] + w[i];
        }
    }

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

假设 $1 \le n \le 100$，$1 \le m \le 1000$，且所有 $v_i, w_i$ 均为正整数。

判断题

21. 第 13 行的循环从大到小枚举 $j$，可以保证每个物品最多被选一次。

{{ select(21) }}

• 正确
• 错误

22. 若将第 13 行改为从 $v_i$ 到 $m$ 递增枚举 $j$，程序仍然总能求出每个物品最多选一次的最优值。

{{ select(22) }}

• 正确
• 错误

23. 程序中的 $dp_m$ 表示恰好装满容量 $m$ 时的最大价值。

{{ select(23) }}

• 正确
• 错误

单项选择题

24. 若输入为：

3 5
2 3
3 4
4 5

程序输出为？

{{ select(24) }}

• 5
• 7
• 9
• 12

25. 若输入为：

3 4
2 10
2 20
3 25

程序输出为？

{{ select(25) }}

• 20
• 25
• 30
• 35

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

{{ select(26) }}

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

阅读程序（三）

#include <iostream>
using namespace std;

int n, ans;

void dfs(int p, int la) {
    if (p > n) {
        ans++;
        return;
    }

    dfs(p + 1, 0);

    if (!la)
        dfs(p + 1, 1);
}

int main() {
    cin >> n;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

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

判断题

27. 当输入为 1 时，程序输出为 2。

{{ select(27) }}

• 正确
• 错误

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

{{ select(28) }}

• 正确
• 错误

29. 当输入为 4 时，程序输出为 7。

{{ select(29) }}

• 正确
• 错误

单项选择题

30. 当输入为 5 时，程序输出为？

{{ select(30) }}

• 8
• 13
• 16
• 21

31. 若删去第 13 行的 if (!la) 判断，直接执行 dfs(p + 1, 1);，当输入为 4 时，程序输出为？

{{ select(31) }}

• 8
• 10
• 15
• 16

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

{{ select(32) }}

• 18
• 20
• 21
• 32

三、完善程序

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

完善程序（一）

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

#include <iostream>
using namespace std;

int a[1005];

void sel(int n) {
    for (int i = 0; i < n; i++) {
        int p = ①;

        for (int j = ②; j < n; j++) {
            if (③)
                p = j;
        }

        int t = a[i];
        a[i] = ④;
        ⑤ = t;
    }
}

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

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

    sel(n);

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

    return 0;
}

33. ① 处应填？

{{ select(33) }}

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

34. ② 处应填？

{{ select(34) }}

• 0
• i
• i + 1
• n

35. ③ 处应填？

{{ select(35) }}

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

36. ④ 处应填？

{{ select(36) }}

• a[i]
• a[p]
• a[j]
• t

37. ⑤ 处应填？

{{ select(37) }}

• a[i]
• a[p]
• a[j]
• p

完善程序（二）

下面程序输出所有长度为 $2n$ 的合法括号序列，请补全程序。

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

int n;

void dfs(int l, int r, string s) {
    if (①) {
        cout << s << endl;
        return;
    }

    if (②)
        dfs(③, r, s + "(");

    if (④)
        dfs(l, ⑤, s + ")");
}

int main() {
    cin >> n;
    dfs(0, 0, "");
    return 0;
}

其中 $l$ 表示已经放入的左括号数量，$r$ 表示已经放入的右括号数量。

38. ① 处应填？

{{ select(38) }}

• l == r
• l == n
• r == n
• l == n && r == n

39. ② 处应填？

{{ select(39) }}

• l < n
• l > n
• r < n
• r > l

40. ③ 处应填？

{{ select(40) }}

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

41. ④ 处应填？

{{ select(41) }}

• l < r
• l == r
• r < l
• r == n

42. ⑤ 处应填？

{{ select(42) }}

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