期末考试复习

！！各次上机的补充题有极大作用！！

成绩构成

往年题型

！！近几年增加了对代码的考查，以验证上机是否是自主完成！！

  1. 判断题（往年8个）

    范围广

  2. 递归树求解递推式

    1. 画树（树根画对，树高画左侧，开销画右侧，叶子节点开销都画成T(1)）
    2. 根据所画树，计算递推式（要用到等比等差公式）
    3. 证明递推式（有时会考，解决不了时记得减去一个低价项）

  3. 求解递推式（不限方法，直接写正确答案给满分，但是错了就没过程分，建议保留过程）

    1. 替换法（建议使用）
    2. 主定理法（建议使用，有可能满足的是主定理的推论）
    3. 递归树法（不建议使用）

  4. 排序

    1. 时间复杂度（三种情况）
    2. 空间复杂度
    3. 稳定性
    4. 适用条件

  5. 多种题型不定

    1. 计算题
      • 例：矩阵链乘
      • 可能比较难，若计算量较大，建议最后做
    2. 问答题（解答题）
      • 例：几类算法的相关问题，如思路、步骤等
      • 分治、DP、贪心、回溯。。。
    3. 算法设计题
      • 可参考第二次上机最后一题（往年原题）
      • 写递推式和思路，不要写Code
      • 不要写太多话，老师会找不到重点
      • 不建议写伪代码
      • 丢分点：
        • 把算法设计当成计算题，只是算出了题目的答案
        • 分析清楚再写
    4. 综合题（近几年新题）
      1. 可能几个算法结合起来考
      2. 可能一类算法出好几问

最耗时间的题型

第一次习题课

θ、Ω、O