第1题在C中若结构体中包含一个 static 成员变量则该变量的存储空间属于结构体对象的一部分。答案错误×1、什么是static成员例如#includeiostream using namespace std; struct Student { int age; static int cnt; }; int Student::cnt 0; int main() { Student a, b; a.age 10; b.age 12; Student::cnt; cout a.age endl; cout b.age endl; cout Student::cnt endl; }2、它到底存在哪里普通成员对象a ------ | age | ------对象b------ | age | ------而static cnt只有一份 放在全局静态区并不属于任何对象。大家可以理解成学校 学生A 学生B 学生C ↓ 人数 只有一个不会每个学生都保存一份人数。3、为什么错因为sizeof(Student)不会计算static成员。所以static不是对象的一部分。第2题二项式展开式所有二项式系数之和等于2ⁿ。答案正确√1、例如(ab)^3 a³ 3a²b 3ab² b³系数1 3 3 1相加8 2³2、为什么把a1 b1代进去。得到(11)^n 2^n右边就是所有系数之和。所以一定成立。3、八级考点杨辉三角 第n行和 2^n第3题const int 可以绑定左值也可以绑定右值。答案正确√1、例如void fun(const int x) { cout x endl; } int main() { int a 5; fun(a); // 左值 fun(100); // 右值 }都合法。2、为什么普通引用int x 5;错误。因为5 没有地址但是const int 允许绑定临时变量。这是C的重要特性。3、为什么STL喜欢写const string 因为既不用复制又可以接收临时对象。效率高。第4题若一个无向图最小生成树唯一则所有边权一定不同。答案错误×1、很多同学第一眼觉得好像是真的。其实不是。2、例如A | 1 | B | 2 | C再加一条A-----5-----C边权1 2 5当然唯一。3、再改一下A | 1 | B | 1 | C还有A-----5-----C最小生成树还是AB BC仍然唯一。但是出现两个1说明边权可以重复。4、真正成立的是所有边权不同 ⇒ MST一定唯一。反过来不成立。第5题快速排序最好、平均、最坏都是O(nlogn)答案错误×1、这是经典考点。最好O(nlogn)平均O(nlogn)最坏O(n²)2、什么时候最坏例如已经有序。每次都拿第一个元素。1 2 3 4 5第一次划分左 空 右 4个第二次又左 空 右 3个一直退化。最后n n-1 ... 1就是O(n²)3、所以很多库都会随机化。三数取中。避免退化。第6题所有顶点度数都是偶数就一定存在欧拉回路。答案错误×1、这里最容易掉坑。少了一个条件。必须图连通。2、例如两个圆。○ ○每个点度都是2。但是两部分完全不连。怎么走根本不可能。3、欧拉回路条件①连通②所有点偶度缺一不可。第7题ST表预处理O(nlogn)查询O(1)答案正确√1、这是RMQ经典复杂度。ST表预处理O(nlogn)查询O(1)2、为什么因为提前把2^0 2^1 2^2 ...全部算好了。3、查询直接取两个区间。一次max。结束。4、八级考点算法预处理查询ST表O(nlogn)O(1)线段树O(n)O(logn)树状数组O(n)O(logn)第8题所有边统一增加一个常数最小生成树一定不变。答案正确√1、为什么假设所有边全部1002、例如原来 1 3 5变101 103 105大小关系有没有变没有。因此PrimKruskal每一步选择边完全一样。所以MST不变。3、注意这是统一加同一个数。如果不同边加不同数字。那就可能改变。第9题Prim和Kruskal得到的最小生成树权值一定一样。答案正确√1、注意这里问的是总权值不是树。2、例如可能存在两棵不同MST但是总代价一定相同。否则其中一个就不是最小生成树了。3、因此算法不同。树可能不同。权值一定相同。第10题递推DP和记忆化搜索时间复杂度总是相同。答案错误×1、很多同学认为两者一样。其实不是。2、例如有100万个状态。真正用到100个。3、递推全部算。1000000状态。4、记忆化只访问100状态。复杂度小得多。5、所以不能说总是一样。应该说很多经典DP两者复杂度相近。但并非所有问题都一样。第二部分总结题号答案知识点易错点1×static成员不属于对象占用静态存储区2√二项式定理系数和2ⁿ3√const引用可以绑定右值4×最小生成树唯一MST≠边权互异5×快速排序最坏O(n²)6×欧拉回路还必须连通7√ST表预处理O(nlogn)查询O(1)8√最小生成树所有边统一加同一常数MST不变9√Prim/Kruskal树可能不同但总权值一定相同10×动态规划记忆化搜索不一定与递推复杂度完全一致本套判断题最值得记忆的八级考点① static 不属于对象。② 二项式系数和 2ⁿ。③ const 引用可以绑定右值。④ 边权互异 ⇒ MST 唯一但反过来不成立。⑤ 快排最坏 O(n²)。⑥ 欧拉回路 连通 所有点偶度。⑦ ST 表预处理 O(nlogn)查询 O(1)。⑧ 所有边统一加同一个常数MST 不变。⑨ Prim 与 Kruskal 的最小生成树总权值一定相同。⑩ 记忆化搜索与递推 DP 不一定总有相同时间复杂度。
