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

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

1. [2 分] 将 4 个相同的红球和 6 个相同的蓝球排成一排，要求任意两个红球都不相邻，有多少种不同的排列方法？ （ {{ select(1) }} ）

• 21
• 35
• 42
• 70

2. [2 分] 在 KMP 算法中，对于模式串 $P = \text{ababaca}$，其 next 数组（next[i] 定义为模式串 $P[0..i]$ 最长公共前后缀的长度，且数组下标从 0 开始）的值是什么？ （ {{ select(2) }} ）

• $\{0, 0, 1, 2, 3, 0, 1\}$
• $\{0, 1, 2, 3, 4, 0, 1\}$
• $\{0, 0, 1, 2, 3, 1, 1\}$
• $\{0, 0, 1, 2, 3, 0, 0\}$

3. [2 分] 对一个大小为 16（下标 $0 \sim 15$）的数组构建满线段树。查询区间 $[2, 13]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？ （ {{ select(3) }} ）

• 8
• 9
• 10
• 11

4. [2 分] 将字符串 apple, apply, app, ape, bat, bag 插入一个空的 Trie 树（前缀树）中。构建完成的 Trie 树（包括根节点）共有多少个结点？ （ {{ select(4) }} ）

• 10
• 11
• 12
• 13

5. [2 分] 对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），如果它是连通的，且存在唯一的拓扑排序，那么它必须满足什么条件？ （ {{ select(5) }} ）

• 图中每个顶点的入度都必须大于 0
• 图中必须存在一条包含所有 $n$ 个顶点的有向路径（哈密顿路径）
• 图必须是一棵有向树
• 边数 $m$ 必须等于 $n(n-1)/2$

6. [2 分] 在一个大小为 11 的哈希表中，使用闭散列法的二次探查法（$H_i = (H(\text{key}) + i^2) \bmod 11$）来解决冲突。哈希函数为 $H(\text{key}) = \text{key} \bmod 11$。依次插入关键字 23, 34, 45, 12, 56。插入 56 后，它最终被放置在哪个索引位置？ （ {{ select(6) }} ）

• 4
• 6
• 8
• 10

7. [2 分] 一个包含 6 个顶点的完全图（顶点的编号为 1 到 6），任意两点之间的边权等于两顶点编号的乘积。该图的最小生成树总权重是多少？ （ {{ select(7) }} ）

• 15
• 20
• 21
• 25

8. [2 分] 如果一棵二叉树的中序遍历序列是 D B E A F C，后序遍历序列是 D E B F C A，那么该树的前序遍历是什么？ （ {{ select(8) }} ）

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

9. [2 分] 一个 $0-1$ 背包问题，背包容量为 15。现有 5 个物品，其重量和价值分别为 3, 4, 5, 6, 7 和 8, 10, 12, 15, 18。装入背包的物品能获得的最大总价值是多少？ （ {{ select(9) }} ）

• 35
• 37
• 38
• 40

10. [2 分] 在一棵以结点 1 为根的树中，已知结点 12 和结点 18 的最近公共祖先（LCA）是结点 4。那么下列哪个结点的 LCA 组合是不可能出现的？ （ {{ select(10) }} ）

• $LCA(12, 4) = 4$
• $LCA(18, 4) = 4$
• $LCA(12, 18, 4) = 4$
• $LCA(12, 1) = 4$

11. [2 分] 递归关系式 $T(n) = 3T(n/3) + O(n \log n)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？ （ {{ select(11) }} ）

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

12. [2 分] 在一个初始为空的最大堆（max-heap）中，依次插入元素 10, 25, 15, 30, 20, 5。然后连续执行两次“删除最大值”（delete-max）操作。请问此时堆顶元素是什么？ （ {{ select(12) }} ）

• 10
• 15
• 20
• 25

13. [2 分] 1 到 1000 之间，不能被 3, 5, 7 中任意一个数整除的整数有多少个？ （ {{ select(13) }} ）

• 456
• 457
• 458
• 459

14. [2 分] 在使用分治法求解最大子段和问题时，时间复杂度为 $O(n \log n)$，而使用动态规划（Kadane 算法）时间复杂度为 $O(n)$。造成这种差异的根本原因是？ （ {{ select(14) }} ）

• 分治法需要额外的递归调用栈空间
• 分治法在合并左右子区间时，需要 $O(n)$ 的时间计算跨越中点的最大子段和，存在重复计算；而动态规划通过状态转移避免了这种重复计算
• 动态规划使用了更少的数据存储空间
• 分治法无法处理包含负数的数组

15. [2 分] 有 4 个独立任务 $T_1, T_2, T_3, T_4$，处理时间分别为 2, 3, 4, 5，截止时刻分别为 3, 5, 6, 8。如果任务超时，惩罚为其处理时间。为了最小化总惩罚，应该采用哪种贪心策略？ （ {{ select(15) }} ）

• 优先执行处理时间最短的任务
• 优先执行截止时间最早的任务，若冲突则替换掉已选任务中处理时间最长的任务
• 优先执行处理时间最长的任务
• 优先执行截止时间最晚的任务

---

二、 阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 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. [1 分] 当输入为 3 时，程序输出的结果为 2。 （ {{ select(16) }} ）

• 正确
• 错误

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

• 正确
• 错误

18. [1.5 分] 若将第 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)$

21. [3 分] 若将 count_ones 中的 x >>= 1 改为 x = x / 2，对于正整数输入，程序的运行结果和效率（ {{ select(21) }} ）。

• 结果改变，效率变低
• 结果不变，效率基本不变
• 结果改变，效率变高
• 结果不变，效率变高

（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;
}

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

单选题

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

• 1
• 0
• 6
• 5

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

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

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

• 编译报错
• 当数组严格递减时，输出结果错误
• 程序陷入死循环
• 输出结果始终比正确答案大 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;
}

判断题

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

单选题

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

• 5
• 6
• 7
• 9

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

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

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

• 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;
}

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

• mid
• left
• right
• a[mid]

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

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

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

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

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

• ans
• a[ans]
• left
• x

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

• 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;
}

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

• 0
• 1
• a[i]
• n

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

• 0
• 1
• n
• dp[0]

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

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

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

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

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

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