保研专业课
五月份了，得开始准备专业课的笔面试了~
主要问题来自于各类经验贴。持续更新
数学
复习资料整理：
https://zhuanlan.zhihu.com/p/567252248?utm_id=0
线性代数
问：特征值为0，和矩阵的秩有什么关系。
答： 矩阵的秩等于其非零特征值的数目。
拓展：对于对称矩阵A，其特征值都是实数。可进行特征分解：
问：半正定矩阵的特征和性质。
答：其对应的二次型
拓展：如果是正定矩阵的话，其对应的二次型为0等价于
概率论
问：说一下先验概率和后验概率。
答：
问：贝叶斯、全概率、条件概率
答：
问：大数定律是什么
答：
离散数学
问：给你一个真值表，如何推出真值表达式。
答：找出输出端为1的各行，每行的输入变量作乘，1为变量本身，0为变量取非，最后把各式进行求和即可。
问：一个有向图是有向树的条件
答：1.只有一个结点入度为0；2.边数为点数减一。
问：说出偏序、全序、良序的定义
答：
问：集合的划分、集合的基数、无穷集合的比较、单射、满射、等价关系、偏序关系、全序关系、布尔格、欧拉图、哈密顿图、树的定义、有向边树的定义。
答：逆天
高数
问：函数的极限定义。导数的定义。
答：设函数
（白话：某个点的极限就是一个常数，该点的某个去心邻域内部的点的函数值都满足和该常数的差的绝对值小于任意小的正数）
问：一致性的定义。
答：
问：拉格朗日中值定理是什么
答：这个定理主要解释的是”平均变化率等于瞬时变化率“。具体来讲，如果函数满足在某个闭区间[a,b]上可导，在开区间(a,b)上连续，那么在开区间(a,b)上必存在一个点使得该点的导数等于平均变化率，即
问：介绍一下间断点。
答：间断点就是非连续点，即不满足函数极限等于函数值的点。根据左右极限将间断点分为第一类和第二类间断点，第一类间断点左右极限相等，但不等于函数值；第二类间断点指左极限或右极限不存在的点。
408
数据结构
问：讲一下两种最小生成树算法，以及如何优化。
答：Prim基于扩展点集的方法求解，每次迭代都取出与当前已加入树的点集距离最近的点加入点集。优化方法：用一个斐波那契堆来维护权重最小的边
Kruskal基于扩展边集的方法来求解。它依次取出边权小到大的边加入树，并在此之前判断是否会出现环。优化方法：并查集判联通分量。
问：给出几种求最长回文子串的解法。
答：暴力的话，可以用类似于区间dp的东西，令
然后可以枚举中心点，向外拓展，这些都是
也可以把向外拓展的那个for用二分+哈希优化一下，
一般正常做都是用manacher，
简单介绍原理的话，就是用类似于动态规划的思想，在转移的时候维护当前右边界最靠右的回文子串。根据当前位置
问：树的直径怎么求。
答：随机找一个点，dfs求出离它最远的点u。然后同理找到离u最远的点v，直径即为uv。
证明可以用反证法，画画图就知道了。
问：介绍一下Huffman编码。
答：Huffman是一种前缀编码，它基于每个字符的出现频率来贪心地构建Huffman树，然后根据不同的根到叶节点的路径来得到对应的编码。
问：哪些排序算法是稳定的，哪些不稳定
答：稳定排序算法定义：关键字相同的排列顺序在排序前后不变。
问：各种排序算法及其时间复杂度。
答：
插入排序：
- 直接插入排序（当前元素插入前面已经有序的序列，
） - 折半插入排序（优化为二分查找，但是涉及到元素移动，复杂度依然是
) - 希尔排序（增量分组插入排序，玄学算法）
交换排序：
- 冒泡排序（相邻元素交换，使最小的值一个个"冒泡"出来，
） - 快速排序（效率基于split算法（可以刷刷力扣熟悉一下？），分治，最坏情况
，理想情况 ）
选择排序：
- 简单选择排序（选择当前最小元素，
） - 堆排序（
建堆（自底向上），然后一个一个删除根， ）。
归并排序：
基数排序：
桶排序：
操作系统
问：计算机启动过程。
答：
问：中断的定义。和异常有什么不同。
答：
问：经典的wait signal写代码。这个东西很无聊，只能记得自己多练，记住一些常用模型（生产者消费者、读者写者等）
问：线程进程的区别，线程同步的方式
答：
问：操作系统的四大作用
答：抽象硬件为用户接口，使计算机易于使用；提高资源的利用率，例如多道程序设计技术；
计算机网络
问：拥塞避免和流量控制
答：拥塞避免是TCP拥塞控制中采用的一个算法，其原理是在TCP发送方拥塞窗口达到一定阈值后，线性地缓慢增加拥塞窗口，这样能够有效避免拥塞。流量控制是TCP的一种限制发送方速率的算法，TCP采用滑动窗口机制实现，TCP接收端可在返回的TCP确认报文段中根据自身情况设置发送方的接收窗口大小，来达到对发送方的流量控制。
问：路由算法
答：路由协议分为两种：内部网关协议和外部网关协议。
内部网关协议之一RIP是基于距离向量的，要求自治系统内的每一个路由器都要维护到其它AS内每一个网络的距离记录，这里的距离用跳数来度量。RIP认为距离短的路由就是好的路由，在和相邻路由器（只和相邻路由器）交换信息时会根据这个原则贪心地更新自己的距离向量。RIP存在路由环路问题。
开放路径优先OSPF是基于链路状态的，它在原本RIP距离的基础上提出了“代价”这一度量指标。OSPF路由器会产生链路状态通告LSA，采用洪泛的方式对其余同AS上的路由器进行更新，最后趋于一致。在此基础上OSPF路由器会基于LSA构建的链路状态数据库，采用类似于dijkstra的算法求出到其它网络的最短路径，并以此指定路由策略。
外部网关协议有BGP，BGP要求每个AS都至少有一个路由器作为“BGP发言人”，一个BGP发言人和其它发言人交换信息需要建立一个TCP连接，然后在此基础上交换BGP报文，交换后基于自己的策略采用相应的路由算法。
计算机组成原理
问：说一下cache。cache的替换算法有哪些？
答：
数据库
问：数据库中数据的四个特性
答：
软件工程
问：给代码，求问满足不同路径下的变量集合（黑盒）
问：给代码，求问哪行出问题，如何改进（白盒）
问：课：软件生命周期、软件开发模型（瀑布、螺旋、敏捷）并比较（各自的优点适用的场景）、软件测试方法、什么是黑白盒测试、白盒测试有哪些（语句覆盖、判断覆盖、条件覆盖、路径覆盖、判断条件覆盖）、路径覆盖是否一定是条件覆盖
答：逆天
AI
勾八东西
问：介绍一下SVM原理？
答：
问：什么是凸函数？如何判断凸函数？
答：
问：有监督学习和无监督学习区别
答：
英语
问：用英文介绍自己最满意的项目。
答：I'm sorry to say I didn't do any valuable projects during my undergraduate years. If I must say so, I will introduce a online operating-system related project proposed by MIT.
问：你觉得最骄傲的一件事情
问：介绍一下你的学校？为什么来我们学校？
问：介绍一下你的家乡？
机试
作为ACMer，也要在意机试。不要自视甚高，眼高手低。
这是我少数的能拿的出手的东西，但也不要压力太大
去年南软的四道：
- 面向对象，考察桥接模式和抽象工厂模式
- 前缀和
- 环形染色问题
- 凸包算法
太变态了，考凸包？
问：一个N个正数的集合，找出和为M的子集
答：dfs???
只输出一个方案的话可以搞个背包。
杂项
问：你如果遇到无法解决的事情会怎么办
答：如果是学习或科研方面的工作，我会借助chatgpt这类工具以及一些网络上的资源来获得解答。如果是生活中的事情，我会求助于身边人，并且通过这件事情进行反思。
问：你认为你的缺点？并如何改善
答：我是个比较敏感的人，这可能并不能算做一个严格意义上的缺点。对于一件事情，我可能会提前想象出它的结果，从而导致犹豫，造成没办法在有效的时间内做出比较有效的结果。换句话说，我不是那种敢于做出突破自我的工作的人。我认为这是因为我没有专心于行动本身，从而导致自己喜欢浪费时间胡思乱想，或许这就是 终日而思，不如须臾之所学也。
问：你认为的自己的优点有哪些？
答：我认为我的自我学习能力比较强。在大学期间，我在没有任何人带我教我的情况下从零开始入坑算法竞赛，并在自我努力下能力逐渐变强，最后获得一系列ICPC等奖项。其次我是一个兴趣驱动的人，对于我感兴趣的东西，我会花时间一步一步的去弄懂它的原理，我认为因为兴趣本身，学习才会变成一个快乐的过程。
问：介绍一下你最近了解的时政（逆天
答：阿赛jumping？好的985也不比中专差。
模拟面试
1、正交矩阵有什么性质？
答：正交矩阵和它自身的转置相乘为单位矩阵。几何意义上，它所对应的线性变换为空间中的旋转和反射，即向量在正交矩阵变换下的长度和夹角保持不变。
2、矩阵的迹有什么性质？
答：矩阵的迹为矩阵对角元的和。也是所有特征值的和。对于若干的向量或矩阵相乘所得矩阵，它们相互之间轮换得到的矩阵的迹是相等的。
3、说一下你对特征值和特征向量的理解。
答：定义上，一个方阵的特征值是满足以下方程的解
在机器学习中，特征向量一般代表着矩阵的“特征信息”。例如PCA降维中，我们都是先求样本的协方差矩阵，然后进行特征分解（或者奇异值分解），将样本尽量投影到其部分特征向量（一般按特征值从大到小排序）所张成的空间上，一般认为这么降维能够最大化无监督样本的特征信息。（凭记忆瞎说的，毕竟我不是搞AI的）
4、介绍一下最短路算法及其优化。
答：单源最短路径可采用经典的dijkstra算法。dijkstra只能用在正权图上，它是基于贪心的思想：它维护一个已求出最短路值的点集和未求出最短路值的点集。构建一个数组dis来表示通过已求出点集能得到的最短路径，每次从未求出点集中找出dis最小的放到已求出点集，然后再根据该点更新dis，这样迭代下去可求出所有点的最短路。朴素算法是
多源最短路采用floyd算法，它是基于动态规划的思想，通过枚举中转结点来转移状态：
5、介绍一下你的项目。
答：