内容发布更新时间 : 2024/5/28 2:00:45星期一 下面是文章的全部内容请认真阅读。

期末考试题型：

1 判断题（10题，10分） 2 填空题（5题，10分） 3 简答题（4题，20分） 4 应用题（5题，60分）

期末考试复习要点：

1 基本概念

算法：有限条指令的序列，确定了解决某个问题的运算或操作顺序（了解概念） 算法的时间复杂度（了解概念） 函数渐进的界O ? ? o ?

有关函数渐进的界的定理（定理1、定理2）（记住、理解）

主定理（会使用主定理求解递推方程）

分治法相关： 分治策略: 适用条件:

算法的设计步骤:

时间复杂度：列出关于时间复杂度函数的递推方程和初值，求解递推方程 提高分治算法效率的途径：

动态规划算法相关： 分治策略: 适用条件:

算法的设计步骤: 时间复杂度：（备忘录的计算工作量）

贪心法： 贪心法: 适用条件:

算法的设计步骤:

贪心法正确性的证明（第一归纳法、第二归纳法）

回溯与分支界限： 解空间： 回溯算法： 分支限界算法： 代价函数： 界函数： 多米诺性质：

NP完全性问题：

P问题、NP问题、NP hard问题、NPC问题

2 几个重要的算法

二分检索 红黑树 插入排序

二分归并排序： 快速排序 堆排序 Prim Kruskal

Bellman-Ford Floyd-Warshall Dijkstra 3 几个重要的问题

背包问题

选最大最小问题 第K小问题

最长公共子序列问题 最优二叉检索树 矩阵链乘法问题 活动选择问题 Huffman编码 最小生成树 连续邮资问题

4 求解递推方程（公式法、迭代法、递归树、主定理）：

??(??)=??(???1)+??2

??

??(??)=9??()+??

3????

??(??)=??()+??()+???? ??是常数

24??(??)=3??(???1)+????3??

??

??(??)=5??()+(????????)2

2??

??(??)=2??()+??2??????

21

()()????=?????1+ ????

??(??)=2??()+????????

3??

()????=3??()+????2??

5??

??(??)=??()+2??

2??(??)=??(√??)+??(lglg??)

??

??(??)=10??()+17??1.2

3??

??(??)=7??()+??3

2??

??(??)=??(+√??)+√6046 2??(??)=??(???2)+?????? ??4??

??(??)=??()+??()+??(n)

55??(??)=√????(√??)+100??