exam-2022.md

# 2022年算法分析与设计期末试题（回忆版）
2022.6.20，星期一，阴。由于时间安排不合理，本人算法最后一道大题空着就交卷了。为避免老师依然不说明考试形式与题型，特此回忆试卷。
## 填空题 10 道
以考察基本定义为主。例如：
- 动态规划法的两个要素是（）和（）。
- 回溯法是以（）优先搜索解空间树，分支限界法是以（）优先搜索解空间树。
- 二分搜索的时间复杂度是（），归并排序的时间复杂度是（）。
## 简答题 4 道
### 第一道 6 分
第一问构建霍夫曼树，第二问根据霍夫曼树进行编码，第三问解码。
### 第二道 6 分
是否可以用单纯形法解背包问题？如果可以，这是一个好方法吗？如果不可以，请说明理由。
### 第三道 6 分
简述 P 问题和 NP 问题的定义。
### 第四道 9 分
解递归方程：（每道 3 分）
$T(n)=4T(\frac{n}{2})+O(n)$
$T(n)=T(\frac{n}{2})+O(1)$
$T(n)=4T(n-1)+O(1)$
## 算法设计题 4 道
### 第一道 12 分
用动态规划法解股票购买问题，是课堂练习原题，要求描述算法、写出边界条件和转移方程、证明复杂度。
### 第二道 12 分
大多数同学使用贪心法解这一道题。
在一个死胡同巷子里，从巷口到巷子内部一共有 $n$ 个住户，距离巷口分别为 $H[1],H[2],\dots,H[n]$。现需要在巷子内设置 $m$ 家邮局，设邮局与巷口的距离依次为 $P[1],P[2],...,P[m]$ ，要求邮局与任意一家住户的距离不大于 100，请给出设置邮局的方法，同时使得邮局数量最少，并证明你方法的正确性。
### 第三道 13 分
用单纯形法解线性规划问题。本题并不是直接给出方程进行求解，而是给出了一个实际问题：
有长为 8 米的圆钢原材料若干，现需要长 2.5 米的钢柱 300 根，长 1.3 米的钢柱 600 根，求最少需要多少原材料。
要求是给出计算过程，个人认为给出每一张单纯形表即可。
注：本题在进行一些代数变换之后可以直接得到答案，甚至无需解单纯形，疑似凑巧，不代表一般情况都有捷径可走。一般来说本题应该会涉及两阶段法，需要添加人工变量和松弛变量，计算量比较大，注意掌握学单纯性法时老师留的课后练习题。
### 第四道 13 分
考察回溯法/分支限界法。需简述算法流程。
本题的背景是一种棋类游戏，游戏规则类似孔明棋。
下图中黑点代表有棋子，白点代表没有棋子，也就是空位。
每一个棋子都可以跨过另一颗棋子，从而“跳跃”到空位上，而被跨过的棋子会被提走。比如说在上图中，可以跳跃的棋子有：
请用回溯法或分支限界法求：
（1）提走 13 颗棋子的方案，不用管最后一个棋子的位置。
（2）提走 13 颗棋子的方案，最后剩下的棋子需要位于最初的空位上。
有同学提出本题可以使用双向BFS或状压+回溯等解法，感兴趣的同学可自行研究。