2025-2026学年下学期期中

2025-2026学年下学期期中试卷

1. 给出下面各个递推式中 $T(n)$ 的渐进上界和下界。假设当 $n \le 2$ 时，$T(n)$ 为常数。使你的界尽可能紧，并给出理由。（10 分）

   (1) $T(n) = 2T(n / 2) + n^4$

   (2) $T(n) = T(7n / 10) + n$

   (3) $T(n) = 16T(n / 4) + n^2$

   (4) $T(n) = 7T(n / 3) + n^2$

   (5) $T(n) = 7T(n / 2) + n^2$

   (6) $T(n) = 2T(n / 4) + \sqrt{n}$

   (7) $T(n) = T(n - 2) + n^2$

   ---

2. 给定 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。现在要将这些数字分成两堆，用 $S_1$ 表示第一堆中数字之和，$S_2$ 表示第二堆中数字之和。请设计算法来找到让 $|S_1 - S_2|$ 最小的分法，并分析时间复杂度。（10 分）

   ---

3. 给定一个数组 $A = [a_1, a_2, \ldots, a_n]$，找出最大子数组和，并返回对应的子数组。请设计时间复杂度为 $O(n)$ 的算法。（15 分）

   ---

4. 给定一个非负整数数组 $A = [a_1, a_2, \ldots, a_n]$，其中 $a_i$ 表示从位置 $i$ 最多可以向右跳多少步。初始时你位于下标 $0$，请设计算法来判断你是否能够到达最后一个位置。（15 分）

   ---

5. 给定一个序列 $(a_1, a_2, \ldots, a_n)$，找出其中最长上升子序列，并返回该序列的长度。请设计时间复杂度为 $O(n \log n)$ 的算法。（25 分）

   ---

6. 给定一个序列 $(a_1, a_2, \ldots, a_n)$，找出其中最长的回文子序列，并返回该序列的长度。请设计算法并分析时间复杂度。（25 分）