一、单项选择题

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

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

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

4、将字符串 "cat", "car", "cart", "case", "dog", "do" 插入一个空的 Trie 树（前缀树）中，构造完成后，包括根节点共有多少个节点？

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

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

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

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

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

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

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

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

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

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

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