2026年 CSP-J 第一轮预测试题

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

1. [2 分] 在计算机存储容量单位中，1 TB (Terabyte) 等于多少 GB (Gigabyte)？ （ {{ select(1) }} ）

• 1000
• 1024
• 2048
• 512

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

• 12
• 4
• 8
• 0

3. [2 分] 给定递归函数 int f(int n) { if (n <= 1) return 1; return f(n - 1) + f(n - 2); }，则 f(5) 的返回值是多少？ （ {{ select(3) }} ）

• 5
• 6
• 7
• 8

4. [2 分] 若一个栈的入栈序列为 A, B, C, D，则下列哪个选项不可能是其出栈序列？ （ {{ select(4) }} ）

• D, C, B, A
• A, B, C, D
• D, A, B, C
• C, D, B, A

5. [2 分] 对于任意一棵非空二叉树，若其叶子结点（度为 0 的结点）数为 $n_0$，度为 2 的结点数为 $n_2$，则 $n_0$ 与 $n_2$ 满足的关系是？ （ {{ select(5) }} ）

• $n_0 = n_2 + 1$
• $n_0 = n_2$
• $n_0 = 2n_2$
• $n_0 = n_2 - 1$

6. [2 分] 将 3 个相同的红球和 2 个相同的白球排成一排，要求 2 个白球互不相邻，共有多少种不同的排列方法？ （ {{ select(6) }} ）

• 6
• 10
• 12
• 20

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 分] 二进制数 $10110_2$ 和十六进制数 $1A_{16}$ 的和，用八进制表示是多少？ （ {{ select(8) }} ）

• $50_8$
• $56_8$
• $60_8$
• $64_8$

9. [2 分] 在 C++ 中，关于 std::vector 的 push_back 操作，下列说法正确的是？ （ {{ select(9) }} ）

• 每次调用的时间复杂度严格为 $O(1)$
• 均摊时间复杂度为 $O(1)$，但在触发扩容时单次操作为 $O(N)$
• 调用后 vector 的 capacity 一定等于 size
• 该操作会导致 vector 中已有元素的内存地址全部改变

10. [2 分] 考虑以下 C++ 代码：

void swap_val(int &a, int b) {
    int t = a;
    a = b;
    b = t;
}
int main() {
    int x = 5, y = 10;
    swap_val(x, y);
}

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

• 5, 10
• 10, 10
• 10, 5
• 5, 5

11. [2 分] 在一个 $8 \times 8$ 的网格中，机器人从左上角 $(1,1)$ 出发，每次只能向右或向下移动一格。要到达右下角 $(4,4)$，共有多少种不同的路径？ （ {{ select(11) }} ）

• 20
• 35
• 56
• 70

12. [2 分] 使用冒泡排序算法对数组 {5, 4, 3, 2, 1} 进行升序排序，在整个排序过程中，元素之间总共需要进行多少次交换？ （ {{ select(12) }} ）

• 4
• 6
• 8
• 10

13. [2 分] 用权值集合 $\{2, 3, 5, 7, 9\}$ 构造一棵哈夫曼树，该树的带权路径长度 (WPL) 是多少？ （ {{ select(13) }} ）

• 52
• 55
• 57
• 60

14. [2 分] 以下代码片段的时间复杂度是？

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= i; ++j) {
        // O(1) 的操作
    }
}

（ {{ select(14) }} ）

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

15. [2 分] 初始为空的队列 $Q$，依次执行以下操作：push(1), push(2), push(3), pop(), push(4), push(5), pop(), pop()。操作完成后，队列 $Q$ 中剩余的元素从队首到队尾依次是？ （ {{ select(15) }} ）

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

---

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

（1）

#include <iostream>
using namespace std;

int count_ones(int x) {
    int cnt = 0;
    while (x) {
        cnt += (x & 1);
        x >>= 1;
    }
    return cnt;
}

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

判断题

16. [2 分] 当输入为 3 时，程序输出的结果为 2。 （ {{ select(16) }} ）

• 正确
• 错误

17. [2 分] count_ones 函数的时间复杂度为 $O(\log x)$。 （ {{ select(17) }} ）

• 正确
• 错误

18. [2 分] 若将第 7 行的 cnt += (x & 1) 改为 cnt += (x % 2)，对于正整数输入，程序运行结果会发生改变。 （ {{ select(18) }} ）

• 正确
• 错误

单选题

19. [3 分] 当输入为 7 时，程序的输出结果为（ {{ select(19) }} ）。

• 3
• 4
• 5
• 6

20. [3 分] 整个 main 函数程序的时间复杂度为（ {{ select(20) }} ）。

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

（2）

#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];
    }
    int max_len = 1, cur_len = 1;
    for (int i = 1; i < n; ++i) {
        if (a[i] > a[i - 1]) {
            cur_len++;
            if (cur_len > max_len) {
                max_len = cur_len;
            }
        } else {
            cur_len = 1;
        }
    }
    cout << max_len << endl;
    return 0;
}

判断题

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

• 正确
• 错误

22. [1.5 分] 若输入的数组元素全部相等（例如 3 3 3），程序输出为 1。 （ {{ select(22) }} ）

• 正确
• 错误

23. [1.5 分] 若将第 16 行的 cur_len = 1; 删除，程序依然能正确求出最长连续递增子序列的长度。 （ {{ select(23) }} ）

• 正确
• 错误

单选题

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

• 1
• 0
• 6
• 5

25. [3 分] 该程序的空间复杂度为（ {{ select(25) }} ）。

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

26. [3 分] 若将第 11 行的 int max_len = 1, cur_len = 1; 改为 int max_len = 0, cur_len = 0;，则程序会出现的问题是（ {{ select(26) }} ）。

• 编译报错
• 当数组严格递减时，输出结果错误
• 程序陷入死循环
• 输出结果始终比正确答案大 1

（3）

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

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i] >> v[i];
    }
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = W; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[W] << endl;
    return 0;
}

判断题

27. [1.5 分] 第 15 行的内层循环必须逆序（从 $W$ 到 $w[i]$）遍历，否则该程序将变成求解“完全背包问题”。 （ {{ select(27) }} ）

• 正确
• 错误

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

• 正确
• 错误

29. [1.5 分] 数组 dp 初始化为全 0，这意味着程序允许背包未被完全装满，且默认所有物品价值非负。 （ {{ select(29) }} ）

• 正确
• 错误

单选题

30. [4 分] 当输入为 3 4 且物品信息为 2 3、1 2、3 4 时，程序的输出结果为（ {{ select(30) }} ）。

• 5
• 6
• 7
• 9

31. [3 分] 若要求背包必须恰好装满，初始化 dp 数组的正确方式是（ {{ select(31) }} ）。

• 全部初始化为 0
• dp[0] = 0，其余元素初始化为一个极小的负数（如 -1e9）
• 全部初始化为一个极小的负数
• dp[W] = 0，其余元素初始化为 0

32. [3 分] 若将第 15 行改为 for (int j = w[i]; j <= W; ++j)，且输入同上题（3 4 \n 2 3 \n 1 2 \n 3 4），则输出结果将变为（ {{ select(32) }} ）。

• 5
• 6
• 7
• 8

---

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

（1）（二分查找）

给定一个长度为 $n$ 的非递减有序整数数组 $a$ 和一个目标值 $x$。请补全程序，使用二分查找找到数组中第一个大于或等于 $x$ 的元素的下标。如果不存在这样的元素，则输出 -1。

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

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    int left = 0, right = n - 1;
    int ans = n; // 初始化为 n 表示未找到
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] >= x) {
            ans = __①__;
            right = __②__;
        } else {
            left = __③__;
        }
    }
    
    if (ans < n) {
        cout << __④__ << endl;
    } else {
        cout << __⑤__ << endl;
    }
    
    return 0;
}

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

• mid
• left
• right
• a[mid]

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

• mid
• mid - 1
• mid + 1
• left - 1

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

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

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

• ans
• a[ans]
• left
• x

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

• 0
• n
• -1
• ans

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

给定一个长度为 $n$ 的整数序列，求其最长严格递增子序列的长度。以下程序使用动态规划在 $O(n^2)$ 时间复杂度内求解。试补全程序。

#include <iostream>
#include <vector>
#include <algorithm>
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> dp(n, __①__);
    int max_len = __②__;
    
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[i] > a[j]) {
                dp[i] = max(dp[i], __③__);
            }
        }
        max_len = max(max_len, __④__);
    }
    
    cout << __⑤__ << endl;
    return 0;
}

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

• 0
• 1
• a[i]
• n

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

• 0
• 1
• n
• dp[0]

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

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

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

• dp[j]
• dp[i]
• i
• j

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

• dp[n]
• n
• max_len
• dp[n-1]