某年期末试卷

2023年2月24日下午4点多 我们三人去找金老师申请免听 他直接将一套历年的期末卷纸拿给了我们去做。 由于操作失误，他的卷纸上选择题旁边都印了答案，然后他就不让我们做选择题了，只让做大题。 结合自己的记忆，我来回顾一下当时的考试内容。

首先，从整理上来说，这套卷纸应该是难度不大的。

1时间复杂度 就给了5个T(n)的递推式，然后写出尽量紧确的界。 掌握主方法和代入法，这五道题还是很简单的

2红黑树插入，画图 这道题主要是给了一串数，让你依次插入一个红黑树，并画出各个步骤的图

3给了你一堆数，让你进行计数排序，手绘流程图 关键是第二问还让分析计数排序和快速排序的优缺点

4摊还分析 对于课本中的那个二进制计数器递增问题 利用 聚合分析，核方法和势方法分别进行分析

5prim算法 给了一张无向图，然后手绘各步骤prim生成最短路的流程

6这个是一个动态规划，我没看完题他就收走了 大概是这样的，给了两个字符串A和B，设计动态规划，查找最长公共子串 然后第二问是在问动态规划是什么？有什么特征？然后有哪两种实现方式？

选择题有两道比较基础的NP问题好像