2025-2026学年下学期期中

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

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

(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$

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

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

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

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

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