2025年 CSP-J 第一轮模拟练习试题

一、 单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. [2 分] 一个 16 位有符号整数（使用补码表示）可以表示的最大值，最接近下列哪个选项？ （ {{ select(1) }} ）

• $3 \times 10^4$
• $6 \times 10^4$
• $3 \times 10^5$
• $6 \times 10^5$

2. [2 分] 在 C++ 中，执行 int x = 12; cout << (x & -x); 后，输出的结果是？ （ {{ select(2) }} ）

• 12
• 4
• 8
• 0

3. [2 分] 函数 f(n) 的定义如下，则 f(5) 的返回值是多少？

int f(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return f(n - 1) + f(n - 2) + 1;
}

（ {{ select(3) }} ）

• 7
• 12
• 19
• 31

4. [2 分] 用 5 个权值 5, 9, 12, 13, 16 构造哈夫曼树，该树的带权路径长度 (WPL) 是多少？ （ {{ select(4) }} ）

• 114
• 124
• 134
• 144

5. [2 分] 在一个无向图中，所有顶点的度数之和等于？ （ {{ select(5) }} ）

• 顶点数
• 边数
• 边数的 2 倍
• 顶点数 + 边数

6. [2 分] 从 4 个红球和 5 个蓝球中选出 3 个球，要求选出的球中既有红球也有蓝球。有多少种不同的选法？ （ {{ select(6) }} ）

• 70
• 74
• 80
• 84

7. [2 分] 假设 a, b, c 都是布尔变量，逻辑表达式 !(a && b) || (a && c) 的值与下列哪个表达式始终相等？ （ {{ select(7) }} ）

• !a || !b || c
• a && (!b || c)
• !a && (!b || c)
• (a || c) && (!b || c)

8. [2 分] 已知数列 $a_0=0, a_1=1$，并且对于所有 $n \ge 2$ 有 $a_n = (a_{n-1} + a_{n-2}) \pmod 5$。那么 $a_{2025}$ 的值是多少？ （ {{ select(8) }} ）

• 0
• 1
• 2
• 3

9. [2 分] 下列关于 C++ vector 容器的说法，正确的是？ （ {{ select(9) }} ）

• vector 的 capacity 总是等于其 size。
• 在 vector 尾部插入元素的时间复杂度最坏情况下为 $O(N)$。
• 使用 vector::erase 删除中间元素后，其后的元素不会发生移动。
• vector 的内存分配是不连续的。

10. [2 分] 考虑以下 C++ 函数：

void modify(int *p, int q) {
    *p = *p + q;
    q = *p;
}
int main() {
    int a = 3, b = 4;
    modify(&a, b);
}

在 main 函数调用 modify 后，$a$ 和 $b$ 的值分别是？ （ {{ select(10) }} ）

• 7, 4
• 7, 7
• 3, 7
• 3, 4

11. [2 分] 在一个网格中，机器人从坐标 (0,0) 出发，每次只能向右或向上走一格。要到达坐标 (3,4)，且不经过坐标 (1,1) 的路径共有多少种？ （ {{ select(11) }} ）

• 15
• 20
• 35
• 55

12. [2 分] 某同学用简单选择排序对数组 {5, 2, 8, 1, 9} 进行升序排序，请问在整个排序过程中，需要进行多少次元素交换？ （ {{ select(12) }} ）

• 2
• 3
• 4
• 5

13. [2 分] 二进制数 $11010_2$ 和十六进制数 $1A_{16}$ 的和，用八进制表示是多少？ （ {{ select(13) }} ）

• $52_8$
• $64_8$
• $72_8$
• $100_8$

14. [2 分] 一棵包含 2023 个节点的满三叉树（每个非叶子节点都恰好有 3 个子节点），其叶子节点的数量是多少？ （ {{ select(14) }} ）

• 674
• 1011
• 1349
• 1512

15. [2 分] 给定一个初始为空的双端队列 (deque) D。依次执行以下操作：push_back(1), push_front(2), pop_back(), push_back(3), push_front(4), pop_front()。操作完毕后，队列 D 中的元素从前端到后端依次是？ （ {{ select(15) }} ）

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

---

二、 阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

（1）

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

int main() {
    int n;
    cin >> n;
    vector<int> cnt(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j += i) {
            cnt[j]++;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (cnt[i] % 2 == 1) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

判断题

16. [1 分] 当输入为 10 时，程序输出为 3。 （ {{ select(16) }} ）

• 正确
• 错误

17. [1.5 分] 第 8 行的 j += i 若改为 j++，程序运行时间会变短，且结果不变。 （ {{ select(17) }} ）

• 正确
• 错误

18. [1.5 分] 程序的时间复杂度为 $O(n \log n)$。 （ {{ select(18) }} ）

• 正确
• 错误

单选题

19. [3 分] 若将第 16 行的 cnt[i] % 2 == 1 改为 cnt[i] == 2，当输入为 10 时，输出为（ {{ select(19) }} ）。

• 2
• 3
• 4
• 5

20. [3 分] 当输入为 100 时，程序的输出为（ {{ select(20) }} ）。

• 9
• 10
• 11
• 100

21. [3 分] 如果将 vector<int> cnt(n + 1, 0); 改为在全局作用域声明 int cnt[100005];，对于极大的 $n$ (如 $n=100000$)，主要的优势是（ {{ select(21) }} ）。

• 提高数组元素的访问速度
• 避免局部大数组导致栈溢出，且自动初始化为 0
• 使得程序的时间复杂度降为 $O(n)$
• 允许数组下标为负数

（2）

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    int sum = 0;
    int left = 0;
    for (int right = 0; right < n; ++right) {
        sum += a[right];
        while (sum > k && left <= right) {
            sum -= a[left];
            left++;
        }
        if (sum == k) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

判断题

22. [1.5 分] 该程序可以正确处理数组 a 中包含负数的情况，并求出和为 $k$ 的连续子数组个数。 （ {{ select(22) }} ）

• 正确
• 错误

23. [1.5 分] 第 16 行的 while 循环条件中，left <= right 是必须的，否则当单个元素大于 $k$ 时会导致逻辑错误或越界。 （ {{ select(23) }} ）

• 正确
• 错误

24. [1.5 分] 程序的时间复杂度为 $O(n^2)$。 （ {{ select(24) }} ）

• 正确
• 错误

单选题

25. [3 分] 当输入为 5 5 且数组为 1 2 3 4 5 时，输出为（ {{ select(25) }} ）。

• 1
• 2
• 3
• 4

26. [3 分] 若将第 19 行的 if (sum == k) 移到 while 循环内部（即在 sum -= a[left]; left++; 之后立即判断），会导致（ {{ select(26) }} ）。

• 答案偏大
• 答案偏小或漏解
• 程序陷入死循环
• 没有影响

27. [3 分] 若数组 a 中所有元素均为 1，且 $k = 3, n = 10$，输出为（ {{ select(27) }} ）。

• 7
• 8
• 9
• 10

（3）

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }
    vector<vector<int>> dp(n, vector<int>(m, 0));
    dp[0][0] = a[0][0];
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == 0 && j == 0) continue;
            int from_top = (i > 0) ? dp[i - 1][j] : -1e9;
            int from_left = (j > 0) ? dp[i][j - 1] : -1e9;
            dp[i][j] = a[i][j] + max(from_top, from_left);
        }
    }
    cout << dp[n - 1][m - 1] << endl;
    return 0;
}

判断题

28. [1.5 分] 该程序计算的是从左上角 (0,0) 到右下角 (n-1, m-1) 的路径中，经过的数字之和的最大值，且每次只能向下或向右移动。 （ {{ select(28) }} ）

• 正确
• 错误

29. [1.5 分] 若将第 20 行的 -1e9 改为 0，当矩阵中存在负数时，程序结果可能偏大。 （ {{ select(29) }} ）

• 正确
• 错误

30. [1.5 分] 程序的空间复杂度为 $O(n \times m)$，且该算法在逻辑上无法优化到 $O(m)$ 的空间复杂度。 （ {{ select(30) }} ）

• 正确
• 错误

单选题

31. [3 分] 当输入为：

2 3
1 2 3
4 5 6

时，输出为（ {{ select(31) }} ）。

• 14
• 15
• 16
• 17

32. [3 分] 如果规则修改为：每次可以向下、向右或向右下对角线移动，为了适应新规则，第 22 行附近应修改为（ {{ select(32) }} ）。

• 增加 int from_diag = (i > 0 && j > 0) ? dp[i - 1][j - 1] : -1e9;，并将 max 改为 max({from_top, from_left, from_diag})
• 将 max(from_top, from_left) 改为 max(from_top, from_left) + 1
• 将 dp[i][j] = a[i][j] + ... 改为 dp[i][j] = max(a[i][j], ...)
• 删除 if (i == 0 && j == 0) continue; 即可

33. [4 分] 若输入矩阵全为 $-1$，且 $n=3, m=3$，程序的输出为（ {{ select(33) }} ）。

• -3
• -4
• -5
• -9

---

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）（快速幂算法）

快速幂算法用于在 $O(\log b)$ 的时间复杂度内计算 $a^b \pmod m$ 的值。其核心思想是利用二进制拆分指数。试补全程序。

#include <iostream>
using namespace std;

long long power(long long a, long long b, long long m) {
    long long res = __①__;
    a = a % m;
    while (b > 0) {
        if (b % 2 == __②__) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        b = __③__;
    }
    return __④__;
}

int main() {
    long long a, b, m;
    cin >> a >> b >> m;
    cout << power(a, b, m) << __⑤__;
    return 0;
}

34. [3 分] ① 处应填（ {{ select(34) }} ）

• 0
• 1
• a
• m

35. [3 分] ② 处应填（ {{ select(35) }} ）

• 0
• 1
• 2
• m

36. [3 分] ③ 处应填（ {{ select(36) }} ）

• b - 1
• b / 2
• b * 2
• b % 2

37. [3 分] ④ 处应填（ {{ select(37) }} ）

• a
• res
• b
• m

38. [3 分] ⑤ 处应填（ {{ select(38) }} ）

• " "
• endl
• NULL
• "\n"

（2）（最长递增子序列 LIS）

给定一个整数序列，求其最长严格递增子序列的长度。以下程序使用贪心结合二分查找的方法，将时间复杂度优化至 $O(n \log n)$。试补全程序。

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    vector<int> tail; // tail[i] 存储长度为 i+1 的递增子序列的最小末尾元素
    for (int i = 0; i < n; ++i) {
        int left = 0, right = tail.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tail[mid] < a[i]) {
                left = mid + 1;
            } else {
                right = __①__;
            }
        }
        if (left == tail.size()) {
            tail.__②__;
        } else {
            tail[left] = __③__;
        }
    }
    cout << tail.__④__ << __⑤__;
    return 0;
}

39. [3 分] ① 处应填（ {{ select(39) }} ）

• mid + 1
• mid
• mid - 1
• right - 1

40. [3 分] ② 处应填（ {{ select(40) }} ）

• push_back(a[i])
• pop_back()
• insert(a[i])
• clear()

41. [3 分] ③ 处应填（ {{ select(41) }} ）

• a[i]
• tail[mid]
• left
• 0

42. [3 分] ④ 处应填（ {{ select(42) }} ）

• length()
• size()
• capacity()
• max_size()

43. [3 分] ⑤ 处应填（ {{ select(43) }} ）

• " "
• endl
• NULL
• "\0"