写于 20226.17 参考资料 hhy老师给的期末总复习提纲 课后答案

简答题（4*5）

算法的渐进表达式计算

例子：

算法B的计算时间满足递推关系f(n) =5 f(n-1)-6f(n-2), n>2; f(0)=1, f(1)=0 。请给出算法B的渐近表达式。

教材中全排列输出的两种实现方式的算法思路和执行流程

第一种算法 permutations1

动态规划的应用 (20)

例子：

用动态规划法来求解下列 0/1背包问题的实例： n=4, W={2,3,4,5}，P={3,4,5, 7}，M=9。 请写出递推计算公式，并通过填写表格来完成计算。

V[i,j] : 遍历前 i 个·东西，容量为j
image.png

贪心算法的应用(20)

动态规划、回溯法、贪心算法的区别与联系

回溯算法的应用(20)

回溯法——3着色

图的遍历(10)

二分图
DFS
关于无向图判断是否存在回路的方法
深搜求DAG图拓扑排序

算法设计(10)

动态规划——求DAG中最长路径