CSP-S 2025 第一轮试卷

有 $5$ 个红色球和 $5$ 个蓝色球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

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

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

将字符串 $\tt cat$, $\tt car$, $\tt cart$, $\tt case$, $\tt dog$, $\tt do$ 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

在一个大小为 13 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(\text{key}) = \text{key} \bmod 13$。依次插入关键字 $18, 26, 35, 9, 68, 74$。插入 $74$ 后，它最终被放置在哪个索引位置？

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权为 $|7 - 3| = 4$。该图的最小生成树总权重是多少？

如果一棵二叉搜索树的后序遍历序列是 $2, 5, 4, 8, 12, 10, 6$，那么该树的前序遍历是什么？

一个 $0-1$ 背包问题，背包容量为 $20$。现有 $5$ 个物品，其重量和价值分别为 $7, 5, 4, 3, 6$ 和 $15, 12, 9, 7, 13$。装入背包的物品能获得的最大总价值是多少？

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（LCA）是结点 $4$。那么下列哪个结点的 LCA 组合是不可能出现的？

递归关系式 $T(n) = 2T(n/2) + O(n^2)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

在一个初始为空的最小堆（min-heap）中，依次插入元素 $20, 12, 15, 8, 10, 5$。然后连续执行两次“删除最小值”（delete-min）操作。请问此时堆顶元素是什么？

$1$ 到 $1000$ 之间，不能被 $2,3,5$ 中任意一个数整除的整数有多少个？

斐波那契数列的定义为 $F(0)=0$, $F(1)=1$, $F(n)=F(n-1)+F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的，而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这种巨大差异的根本原因是？

$5$ 个独立的、不可抢占的任务 $A_1, A_2, A_3, A_4, A_5$ 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3, 4, 2, 5, 1$ 和 $5, 10, 3, 15, 11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？