考试日期：2023.6.1
一、概念题1.O（n²）和Ω（n²）的含义
2.以归并排序为例子阐述分治算法的思想
二、算法题1.区间覆盖问题，并证明贪心正确性
2.a1，a2……an中相邻的两个数只能选择其中一个，怎么选能够得到最大和。使用动态规划算法。
（1）写出目标函数
（2）根据目标函数写出递推方程
（3）根据递推方程求出时间复杂度
3.Floyd-Warshall算法
（1）写出目标函数和递推方程
（2）根据下图补全Floyd-Warshall算法的过程
4.Ford-Fulkson算法过程，写出最大流和最小割
三、证明题1.证明最大流最小割定理
2.顶点覆盖和团问题相关
3.证明TSP的近似算法是2-近似算法
感觉没发挥好，发个回忆版积点德