前言
感谢@甘晴void大佬的分享，找到了这套卷子。
这套卷子因为考前时间有限，有些题没来得及做，但是看了一下，试卷题型已经较为贴近当前题型（除了多了选择题和论述题），而且题目质量中规中矩，因此对于没做的题，贴上笔者检查过的AI解析。
一、单项选择题
题干
解析
1. 答案：A
解析：Strassen 矩阵乘法通过把矩阵分成子块、递归计算（分治）将 8 次乘法减少为 7 次实现加速。
2. 答案：C
3. 答案：D
4. 答案：B
解析：分数背包的贪心算法需先按价值密度排序，排序时间主导为 O(nlogn)。
5. 答案：B
解析：
在回溯法中，采用深度优先搜索，活结点可能被多次回溯访问，但每次回溯时该结点仍然是活结点，因此一个结点在成为活结点后可能持续作为活结点存在，直到其所有分支被探索完毕。
而在分支限界法中，活结点通常存储在队列或优先队列中，一旦一个活结点被扩展，它就会被移除队列并变为死结点，之后不再被使用。因此，在分支限界法中，一个活结点最多只有一次机会成为扩展结点。
6. 答案：B
解析：活动安排问题用“按最早结束时间贪心”能得到最优解，属贪心策略。
7. 答案：无
解析：
8. 答案：A
解析：蒙特卡罗算法以概率方式给出结果，可能以一定概率得出错误答案。
9. 答案
解析：舍伍德算法的目标是消除最坏情况和平均情况下的时间复杂度差异，因此一定能够得到正确的解。
10. 答案：D
二、简答题
题干
解析
1.
问题同构指的是两个问题，在数学模型、计算结构和求解方法上具有相同的本质，因此可以用相同的算法框架或思想来解决。同构问题往往具有相似的最优子结构、递归关系或状态转移方程。
举例：矩阵链乘法问题与凸多边形最优三角剖分问题是经典同构问题。两者均可使用动态规划求解，且状态转移方程形式相同。
2.
最优子结构性质是指一个问题的最优解包含其子问题的最优解，即可以通过组合子问题的最优解来构造原问题的最优解。
要求问题具有最优子结构性质的算法设计思想包括：
动态规划：利用最优子结构构建状态转移方程，自底向上或自顶向下求解。
贪心算法：每一步的贪心选择必须满足最优子结构，以确保局部最优能导致全局最优。
分治法：将问题分解为相互独立的子问题，子问题的最优解合并后应为原问题的最优解。
3.
拉斯维加斯算法：总是给出正确解，但运行时间是随机的，期望时间复杂度有界。
举例：随机化快速排序，随机选择枢轴元素，排序结果一定正确，但运行时间与枢轴选择有关，期望时间为O(nlogn)。
蒙特卡罗算法：运行时间固定，但可能给出错误解，错误概率可以通过重复执行控制。
举例：蒙特卡罗算法求解主元素问题。算法随机选择数组中的一个元素作为候选，统计其出现次数，若超过半数则判定为主元素，否则判定为不存在。单次运行时间固定为 O(n)，但存在将非主元素误判为主元素的概率（小于 1/2）。通过重复执行 k 次，可将错误概率降至 (1/2)^k 以下，从而以可控的错误概率换取确定且高效的运行时间。
三、算法应用题
3.1 题干
3.1 解析
（1）最少需要进行 n-1 天。
（2）
| 选手\天数 | 第 1 天 | 第 2 天 | 第 3 天 |
| 1 | 2 | 3 | 4 |
| 2 | 1 | 4 | 3 |
| 3 | 4 | 1 | 2 |
| 4 | 3 | 2 | 1 |
3.2 题干
3.2 解析
m 矩阵如下：
| i \ j | 1 | 2 | 3 | 4 |
| 1 | 0 | 5000 | 7500 | 8000 |
| 2 | 0 | 25000 | 7500 | |
| 3 | 0 | 2500 | ||
| 4 | 0 |
s 矩阵如下：
| i \ j | 1 | 2 | 3 | 4 |
| 1 | 1 | 1 | 2 | 2 |
| 2 | 2 | 2 | 2 | |
| 3 | 3 | 3 | ||
| 4 | 4 |
最少数乘次数：8000
最优加括号方案：
3.3 题干
3.3 解析
（1）
（2）最大团：
3.4 题干
3.4 解析
四、算法设计题
题干
解析
算法思想
定义状态数组dp[i]表示以第i个元素结尾的最长上升子序列长度，初始时每个元素自身构成长度为1的子序列，故dp[i]初始化为1。对于每个位置i，遍历其前的所有位置j（j < i），若nums[j] < nums[i]，说明nums[i]可接在以nums[j]结尾的上升子序列之后，形成更长的子序列，因此更新dp[i] = max(dp[i], dp[j] + 1)。最终，最长上升子序列的长度即为所有dp[i]中的最大值。
伪代码
int LIS(vector<int>& a) { int n = a.size(); if (n == 0) return 0; vector<int> dp(n, 1); // dp[i] 表示以 a[i] 结尾的LIS长度 int maxLength = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (a[j] < a[i]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLength = max(maxLength, dp[i]); } return maxLength; }时间复杂度
上述算法使用了两层循环，外层循环遍历每个元素（共 n 次），内层循环对每个元素遍历其前的所有元素（平均 n/2 次），因此总的时间复杂度为，其中 n 为序列长度。
五、论述题
题干
解析
随便写写得了，估计不会考，考就是送分的。
