前言

感谢@甘晴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 为序列长度。

五、论述题

题干

解析

随便写写得了，估计不会考，考就是送分的。