由于今年本校加入了7月8日的初试，初试还考的408，故开始稍微复习复习。
Update: 疫情原因复试也要在网上进行了，这里会补充其他科目的简要复习。
数据结构
这部分比较简单，快速过完
线性表
顺序表（数组）、单链表、循环/双向链表
栈
顺序栈（数组实现）、链式栈（链表实现）
递归工作栈（函数调用与返回）
栈实现递归过程的非递归算法
迭代实现递归
回溯法：使用递归和栈帮助试探和回溯
队列
FIFO特性
优先级队列：堆是一种实现
多维数组
数组的数组
一些特殊矩阵不建议用多维数组：对称矩阵（一维数组）、稀疏矩阵（三元组<row, column, value>顺序表）
稀疏矩阵的转置
由于要预先确定矩阵 A 的每一列的第一个非 0 元素在 B 中相应的位置，如果遍历效率很低，O(row*cols^2^)
用两个辅助数组存储矩阵 A 中每一列的非 0 元素个数和矩阵 A 中每一列第 1 个非0 元素在 b 中的存储位置
字符串
KMP算法模式匹配
next[j]求法：看0到i-1首尾重合的部分
广义表
元素= 节点类型+信息（引用数or值or头指针，取决于类型）+尾指针
树
DFS、BFS、森林（与树的转换）、huffman树
堆
最小堆、最大堆
建立：自底向上逐步建立，每一步执行下滑算法，自上向下与子中较小的（最小堆）比较
插入：自下而上的上滑算法
删除：用堆中最后一个填开头，然后执行一次下滑
并查集
处理动态连通问题
简单并查集效率较低：
路径压缩：最坏情况可能形成链表的问题
按秩合并：尽量不增加树高：把简单的树往复杂的树上合并
二叉搜索树BST
左更小、右更大
极端情况退化成链表
改进：AVL、红黑树、2-3树……
图
数据结构中仅讨论简单图，即无重复边、无到自身的边
无向图：连通：点能到即连通，无向图的极大连通子图即为连通分量
有向图：强连通：点互相能到即为强连通，有向图的极大强连通子图即为强连通分量
生成树：包含图中所有节点的极小连通子图，砍一条就不连通，加一条就有回路
在非连通图中，连通分量的生成树构成生成森林
结构
邻接矩阵：二维数组
邻接表：链表的数组，不方便统计入度
十字链表（有向图）：见王道数据结构219，pdf231.其实就是顶点节点加上一个指针指向第一个到该顶点的弧，弧结点有两个指针，一个指向下一个弧头相同的弧，另一个指向下一个弧尾相同的弧
邻接多重表（无向图）：把邻接表中的一条边（会用两个结点表示）用一个结点，边的结点记录两端
遍历
BFS、DFS
最小生成树
边数 = 点数 - 1
Prim和Kruscal都基于贪心
Kruscal
每次看权值最小边的两个顶点是否属于不同连通分量，是则加入这条边
适合边稀疏的图
Prim
初始：随机选顶点
每次找顶点集中与分量外相连边中权值最小的，加入
适合边稠密的图（复杂度O(v^2^)）
最短路径
Dijkstra求单源最短路
算法过程与Prim相像
dist数组记录从源点v0到其他所有顶点的当前最短路径长度
path记录从源点v0到其他所有顶点的当前最短路径的前驱结点，用于记录最短路径
如果有负权边就可能不正确
O(v^2^)
Floyd求所有顶点间最短路径
jki迭代
O(v^3^)
拓扑排序
用于AOV网的活动关系，即描述活动Vi必须先于Vj
取无前驱顶点 → 删除 → 重复
有环报错
关键路径
用于AOE网的活动关系，用边表示活动
最迟开始时间和最早开始时间差额为0即为关键活动
排序
其他排序：直接插入、希尔（分成子表进行直接插入）、冒泡
快排
找pivot应该在的位置，一次后pivot左的比pivot小，右的比它大，再对左右子表执行快排即可
选择排序
堆排序，构造堆后每次取堆顶
归并
2路归并：分成两段然后递归
基数排序
划分各个关键字范围
是一种特殊的桶排序
计算机网络&操作系统&算法
这几门课之前做过笔记，直接看那个。。
重点看算法，被问到的概率很大。。
计算机组成&计算机系统基础
这两部分比较像，可以放在一起复习
TLB & cache
TLB可以理解为页表的cache，在高速缓存中存储可能会用到的页表项
异常：故障、陷阱（预先安排，比如进行CPU单步跟踪时）、终止
离散数学简要复习
由于没时间再加上离散太难，，只能简单看看了。。
1 逻辑
合取：且；析取：或；蕴含：p→q；双蕴含：等价于
A → B ≡ ¬A ∨ B 蕴含等值
A → B ≡ B → A 假言易位
范式：合取范式：简单析取式的合取；析取范式：简单合取式的析取
谓词：命题函数P(a1,a2,…,an)，函数P称为谓词
量词：全称量词∀，存在量词∃
2 集合
空集：没有任何元素的集合
后继：a ∪ {a}，记作a^+^
运算：并、交、相对补（-）、对称差（⊕）、广义交&并（集合内所有元素的交&并）
集合的笛卡尔积A × B
关系：关系是一个集合，若R ⊆ A × B，则称R为A到B的关系。R有定义域、值域
| 关系的运算：逆、复合（设R ⊆ A × B，S ⊆ B × C，则R ∘ S = {(x,y) | (x,t)∈R, (t,y)∈S}、幂（R不断复合自己） |
函数：这样的二元关系F: $(\forall x,y,z)(xFy\ \and\ xFz \to y=z)$
满射（值域都有）、单射（反过来也是函数）、双射（满且单）
3 数论
整数上的二元关系：整除、同余
最大公约数gcd
中国剩余定理：一元线性同余方程组有解，且有公式求
欧拉函数：小于或等于n的正整数中与n互质的数的数目
容斥原理：有穷全集共N个元素，每个性质对应子集A1, … , An，则不满足任何性质的集合的元素个数为：
| $N - S1 + S2 - S3 ……$，其中Si就是多少个元素取交集之和，例如S2即为 $ | A1\cap A2 | , | A2\cap A3 | , | A1\cap A3 | $ 这样 |
排列组合：r-排列（有序）、r-组合（无序）
鸽笼原理
4 离散概率
概率是频率趋于的常数
古典概型：$P(A) = \frac{A中样本点个数}{\Omega中样本点总数}$
| 条件概率$P(A | B)=\frac{P(AB)}{P(B)}$ |
| 贝叶斯定理：$P(A_1 | B)=\frac{P(A_1B)}{P(B)}=\frac{P(A_1)P(BA_1)}{\sum_{i=1}^{n}P(A_i)P(B | A_i)}$ |
独立事件：$P(AB)=P(A)P(B)$
期望：E(X)
方差：V(X)
$V(X)=E(X^2)-E(X)^2$
5 代数系统
关系的性质
（反）自反性、（反）对称性、传递性
自反：$\forall x\in A,xRx$
反自反：$\forall x\in A,\neg xRx$
对称：$\forall x,y\in A,xRy \to yRx$
反对称：$\forall x,y\in A,xRy,yRx \to x=y$，即不存在除了xRx之外的对称
传递：$\forall x,y,z\in A,xRyRz \to xRz$
等价：自反、对称且传递
闭包：关系R的某性质闭包：（如自反闭包），加入最少的有序对使得满足性质
偏序
偏序关系：自反、反对称、传递
偏序集：集合+集合的一个偏序关系
代数
运算的封闭性：对于运算，若结果仍在集合内则封闭。减法在自然数集上不封闭，除法在整数集上不封闭
代数系统：1个非空集合+至少1个运算，运算对集合封闭
单位元e：e ◦ x = x ◦ e = x，左单位元&右单位元
左、右不一定存在，不一定唯一，若都存在则必相等且唯一
逆元：存在单位元的才有逆元，x ◦ x’ = e
零元：x ◦ t = t ◦ x = t
同构：一模一样，f(x*y) = f(x) ◦ f(y)，f是双射
同态：f不需要双射
6 群论
半群：代数系统+结合性
幺半群：半群+单位元
群：幺半群+逆元
群的阶：元素个数、
abel群：交换群
子群：群的子代数
有限子群判定定理：G为群，H是G的非空有限子集，H是G的子群等价于：$\forall a,b \in H, ab \in H$
群元素的阶：设a是群G中的一个元素，使得 的最小正整数n称为a的阶
循环群：有一个生成元可以不断生成得到群
7 格
偏序集定义：偏序集，集合中所有元素有上下确界，则构成偏序格
格导出的代数系统：两个运算∨和∧
代数格：代数系统+交换律结合律吸收律
分配格：x∨(y∧z)=(x∨y)∧(x∨z)
有界格：有上下界
有补格：有界格每个元素均存在补元（a∧b = 0, a∨b = 1）
8 布尔代数
布尔格：有补分配格
9 图论
表示：三元组：点、边、边与点的关联关系
邻接矩阵、邻接表等
入度、出度
完全图，记作$K_n$
正则图：k-正则图：无向图每个点的度都为k
二部图：点可以分为两部分
通路：点边点……组成
简单通路：无重复边
路径（初级通路）：无重复边和重复点
回路：起点和终点相同
路径存在性定理：若i到j有通路，则i到j有长度≤n-1的路径
连通图：无向图任意两点连通
点割集：去掉一个点的集合，连通分量数增加，去掉集合中任意子集不会使连通分量增加，只有一个元素，则称为割点
边割集：改成边，只有一个元素称为割边，又称桥
e是割边当且仅当e不在图的任一简单回路上
点连通度：连通图删除最少的点使其称为不连通
点连通度小于等于边连通度小于等于最小度
欧拉图：包含欧拉回路，即包含图中每条边的简单回路
欧拉图的判定：所有结点的入度和出度都相等（有向图），奇数度的结点个数为0（无向图）
半欧拉图的判定：有两个点不相等（有向图），有两个点度为奇数（无向图）
哈密顿图：包含哈密顿回路，即包含图中每个点的初级回路
带权图：边上有权值，Dijkstra算法求SSSP（单源最短路）
有向图：弱连通：对应的无向图连通；强连通：真正连通
竞赛图：底图是完全图的有向图，即任意两点都有一次“竞赛”
图的匹配：一个边独立集，集合内任意两边不相邻
10 树
树是边最少的连通图，树中每条边均是割边 树是边最多的无回路图
最小生成树算法：Kruscal和Prim
其他课程
软工
面向对象OOP：封装、继承、多态
封装：把多个功能和数据聚合在一起形成类
继承：子类可以获得父类的属性值和方法
多态：同一接口可以有不同的实现方式
敏捷开发AD：极限编程思想的体现，迭代、拥抱变化
瀑布开发WM：传统模式，多个阶段像瀑布一样循序渐进，包括需求分析、设计、编程、测试、维护
线代
奇异矩阵 = 不满秩 = 对应的行列式值为0
矩阵的三种初等变换：
- 互换矩阵的两行
- 以一个非零数乘以矩阵的某一行
- 把某一行各元素的k倍加到另一行对应元素上
线性方程组的解：
非齐次：
- r(A) < r(A,b)，无解，r(A,b)即A的增广矩阵的秩
- r(A) = r(A,b) = n， 有唯一解
- r(A) = r(A,b) < n，有无数解
齐次：
行列式值为0，有无穷多解，否则只有零解
逆矩阵：AB = BA = E，则B为A的逆
正交矩阵：AA^T^ = A^T^A = E
相似矩阵：B = X^-1^AX
矩阵的特征值：对于n阶方阵A，有数m和非零n维列向量x，Ax = mx，则称m是A的一个特征值
三大关系：等价（初等变换）、合同（初等变换行列一起做）、相似
分别对应矩阵的秩不变，矩阵的特征值的正负分布不变，矩阵的特征值不变。
合同可以看成等价的特例，相似可以看成合同的特例
概率论
等可能概型（古典概型）：样本只包含有限个元素、每个基本事件等可能
条件概率（参考离散数学4）
各种分布：
离散：0-1、二项分布（n次伯努利试验）、泊松分布（小概率）
连续：均匀分布、指数分布λe^-λx^、正态分布
随机变量的数字特征： 期望、方差
| 切比雪夫不等式：只知道E(X)和D(X)的情况下估计概率 P{ | X-E(X) | < ε}的界限：$P( | X-\mu | < ε) ≥ 1 - \frac{\sigma^2}{\epsilon^2}$ |
协方差cov(X, Y) = E(X − E(X)) E(Y − E(Y))
相关系数$\rho=\frac{cov(X,Y)}{\sqrt{D(X)D(Y)}}$
大数定律：随机变量序列的算术平均值向随机变量各数学期望的算术平均值收敛
中心极限定理：设随机变量X1，X2，……，Xn，……独立同分布，当n很大时 ΣXi 近似服从正态分布
一些英文问题
也不知道会不会问到，临时瞎写的。。
学的比较好的课程：
Personally I think it would be the Computer Network. There are some reasons.
First, I like the rhythm of this course. It’s not so hard as FLA or Algorithm, the difficulty is just right. And it is hierarchical, you know, we study from physical layer, data link layer, all the way to application layer. I really Enjoy the rhythm. Second, as I said in my self introduction, I found I have interest in this field. As we all know, interst is the best teacher.
研究生期间打算：
First, I need to study hard to establish a systematic frame of my knowledge in the filed. There are lots of papers to read to finish this goal.
Second, I hope I can cultivate the ability of innovation, which I think is the most important thing in my future. This is a systematic process, for which I need to study, summarize, and think.
万一不会了：
I’m very sorry, but due to the long time, I don’t remember the content of this part very clearly. 然后扯点自己知道的
关于项目
园区网多设备协同流量控制技术研究项目
项目背景：
-
园区网中经常会有突发流量的出现
- 突发流量下，非瓶颈的接入交换机也可能丢包
- 要降低丢包率
项目工作：
- 园区网交换机启用ECN。通过修改进入园区网的数据包的ECN位实现
- 当出现拥塞信号时，在AP处减小返回ACK的接收窗口，以迫使源端发送更少的数据包
我的工作：
- 启用ECN后，核心、汇聚、接入交换机需要一个阈值来控制。负责研究在园区网网络环境下阈值如何设置
- 使用NS3进行仿真