2024-2025-2学期（2025年春季学期）AI2615算法设计与分析期末真题，题目经过翻译，来自于我的一位好友。

原文链接

T1（本题满分25分） ​

设序列$A : (a_{1},a_{2},\dots,a_{n})$，序列$B : (b_{1},b_{2},\ldots,b_{m})$，其中$m<n$。

我们定义序列$B$是序列$A$的子序列，当且仅当序列$B$中的元素按照顺序在序列$A$中出现。比如说，设$A = (1,2,3,4,5,6,7)$，$B_{1} = (1,3,5)$，$B_{2} = (3,1,5)$，那么$B_{1}$是$A$的子序列，而$B_{2}$不是。

请你设计一个$O(n)$的算法，判断读入的序列$B$是否是读入序列$A$的子序列。证明你的算法的正确性并且分析其时间复杂度。

T2（本题满分25分） ​

已知工厂里仅有一台机器，接下来$n$天的最大生产计划$x_{1},x_{2},\cdots,x_{n}$，与机器的最大生产量$s_{1},s_{2},\cdots,s_{n}$。

对于每一天，你有两种选择：

1. 对机器进行检修，那么当天的生产量为0；
2. 让机器继续生产，那么假设上一次检修时间是第$j$天，今天是第$i$天，那么机器的生产量是$min\left\{s_{i-j},x_{i}\right\}$。

请你设计算法，通过合理规划机器的检修和生产，最大化机器在$n$天中的总产量，分析其时间复杂度并证明其正确性。

T3（本题满分25分） ​

设$U = \{1,2,3,\cdots,n\}$，$S=\{A_{1},A_{2},\cdots,A_{m}\}$，且$S$中的每个元素都是$U$的子集。$k$是一个给定的小于等于$n$的整数。

已知：$S$可以被划分为两个集合（即$S$中的每个元素都出现在一个集合中），其中每个集合中的元素两两不交。例如，$S=\left\{\left\{1,2,3\right\},\left\{4,5,6\right\},\left\{1,2\right\},\left\{3,4\right\},\left\{5,6\right\}\right\}$就是一个符合上述条件的集合。

证明：存在大小为$k$的集合$T$，满足$\forall A_{i} \in S$，均有：

$$\left|A_{i} \cap T\right| \leq \left\lceil \dfrac{k}{n} \cdot \left|A_{i}\right| \right\rceil$$

T4（本题满分25分） ​

我们可以按照如下的方式定义停机问题：读入一个字符串，将其看成在 C++ 下的代码，判断如果执行这份代码，程序是否会终止。无论是编译不通过，程序运行异常导致的终止，还是正常终止，都被视为程序终止。

（1）证明：停机问题是$NP-hard$的

（2）停机问题是$NP-complete$吗？证明你的断言。