国科大2022计算机算法设计与分析期末考试-刘玉贵老师

就在刚刚，考完了刘玉贵老师的算法期末，也算是给这门课程做一个总结，同时梳理一下期末的考试范围，希望对学弟学妹有用！

废话不多说，先放考试范围(来源：sep课程网站，期末会给)：

接着放考卷：

 

 总结：

一、题型分布：填空（2分*5）、判断（2分*5）、简答（5*3+10）、算法（20+20+15）

二、试题90%都来自于平时的课后作业题，课后作业需要认真完成

三、同类题型替换：也就是说，上面的试卷是22年的试题，那么23期末，这些题很多是要替换的，但考法基本类似，考试范围相同。以下替换仅代表个人观点：

①填空选择题型大多来源于第八、九、十、十一章。必考一道时间复杂度比较，题型来源于习题二4；

②简答题：简述模拟退火/遗传算法/禁忌算法的主要步骤（看ppt）+基于贪心规则写近似算法（多级调度、顶点覆盖，还是看ppt）+证明NPC（相遇集、独立集等，参考上面考试范围，太难的不会考）+迭代法算所给算法（主要来源是课本第三章分治算法，例如快速傅里叶变换、最近点对等，基本上都是nlong）的时间复杂度;

③算法题：贪心+动态规划+回溯/分支限界

贪心和动态规划都需要先证明（最优解/最优子结构），再写算法

贪心：重在证明最优解，算法写起来很简单。由于需要证明最优解并且写算法，而且是课后题，所以主要范围是建基站和test检测作业；

动态规划：重在写算法，证明最优子结构比较简单。主要范围有：双机调度、最大子段和（最长单调递增子序列）、n个作业最大效益、凸多边形划分三角形等。emmm基本上就是第五章的习题吧，但是都很重要，好好做

回溯/分支限界：直接写算法就可以，不需要像前两道题证明。主要范围：n人分派n个工作、n个作业k台机器。注意要求用回溯法还是分支限界法实现。

写在最后：

刘玉贵老师的期末考试很多都是作业题，只要平时认真完成作业，不必担心过不了。同时，上课听课也很重要，一节课落下后面再想跟上就要付出很大的时间和经历。算法学完之后还是有很大的收获的，加油！