2021年 山东大学 算法导论考卷 回忆版

2021SC@SDUSC
一
（1）解释算法时间复杂度的三个符号——Θ、Ω、Ο
（2）T（n）=T（3n/4）+nlogn，计算T（n）的时间复杂度
（3）证明顶点覆盖问题是NP完全问题
二
（1）寻找强连通分支，证明其正确性，时间复杂度
（2）在已有最小生成树的基础上，将随机一条边的权重变大，求新的最小生成树的更新算法。写出伪代码，证明其正确性。
三
（1）寻找最短路径的三个相关证明
1.最短路径的子路径也是最短路径
2.对于任意两个点间的所有最短路径，总有一条为有限长度
3.证明三角不等式
（大概是这三个，诶嘿）
（2）Floyd-Warshall算法（多源最短路径问题）说明其相关思想，补全（更新）邻接矩阵，并写出最短路径
四
（1）从左到右有n堆棋子，每堆棋子若干个，只能合并相邻堆的棋子，合并的花费为被合并棋子堆的棋子数。
现要把这n堆棋子合并为一堆，给出一个花费最小的算法

2021年 山东大学 算法导论考卷 回忆版最先出现在Python成神之路。