威廉希尔首先我参与的夏令营及预推免考核范围是[中九-华五]，总结的考核范围基于所参与的面试及我看的经验贴。我的保研经验贴可见以下链接。

　　（由于内容十分多，我打算慢慢的里面更新，看的人多我就更新快一点吧，可以收藏一下，点个赞，以后看）

　　最粗略的来说考核会包含英语，专业课，数学，相关项目内容，机考，综合素质等方面，考核形式有面试，笔试和机考

　　专业课：各个课程的基础概念及算法，比较常涉及的课程有算法，数据结构，操作系统，机组，数据库，机器学习，计网。但实际会涉及的范围是成绩单上的所有课程，可以注重老师教的范围或者你成绩单里面比如突出的科目（比如100分）

　　数学：课程的基础概念及算法，线代，概率论，高数，离散数学，我觉得被问的频率是，线代=概率论离散数学高数，但不同学校也有区别，比如北航就一定会问离散数学，有些学校不问

　　项目内容：简历及自我介绍中涉及的竞赛及项目一定要好好复习，特别是和老师研究方向相关的部分，提问频率：相关科研经历 相关竞赛 科研经历 竞赛经历

　　综合素质：这里问的会很奇怪，建议多看看学校经验贴，一般来说会问思政，然后可能会涉及一些智商题，如脑筋急转弯，逻辑题等等

　　第二章 递归和分治将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解

　　稳定排序--一样大的值原来在前面就在前面，内部排序和外部排序（数据很大，需要磁盘的参与）选择第k小点，利用快排的思想，用特殊的方式选择区分点

　　Strassen矩阵乘法 类似把矩阵拆成小的矩阵，然后通过数学替换把乘法变成加法

　　线组，每组用五个元素，找出每组的中位数，递归选取每组中位数的中位数，之后再用这个中位数进行划分

　　一维最接近点对问题：利用x坐标从中间分治，求左边最接近和右边最接近以及跨区域的最接近点，从中选取最接近点 O(n*logn) 花在排序上火线性选择上了me二维最接近点对问题：类似于一维最接近点对问题，每一个点位的跨区域点最多六个（跨区域的范围不会超过一个两边区域的最小长度)第三章动态规划

　　贪心选择性质：自顶向下，整体最优解可以以局部最优解进行推得。局部选择了A为最优解，则全局最优解B包括A 最优子结构：问题的最优解包含其子问题的最优解，活动时间--，活动数--，即为子问题的解 使用数学归纳法证明需要掌握的算法：活动安排问题，哈夫曼编码，单源最短路径，最小生成树，多机调度问题

　　哈夫曼编码：不同频率出现的多种符号，用不定长码进行编码，单源最短路：从某一点到其他各点的最短路径最小生成树：可以选择边最小进行连接，或者从某一点开始

　　第五章 回溯法为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法找到正确的解空间-遍历+剪枝

　　线性表:线性和链式，增删改查栈和队列线性和链式，增删改查，栈的top和bottom（不动），FILO队列是FIFO，队首删除，队尾插入。顺序队列会存在假溢出现象，用循环队列空出一个位置可以解决链式表示：串串的模式匹配算法KMP--主串的下标只增不减，通过next数组选取子串的下一个位置修正的next数组（因为还知道目前的字符不是xx字符，多次比较nextval数组）O（m+n），因为知道主串的部分信息数组和广义表数组要求元素是统一的类型，维数和个数一般不发生变化，适合顺序存储特殊矩阵的压缩--对称矩阵（变一维），稀疏矩阵（三元组，十字链表，每行每列一个指针）广义表是由零个或多个原子或者子表组成的有限序列。原子：逻辑上不能再分解的元素。子表：作为广义表中元素的广义表。长度（第一层），深度，表尾是除表头以外的元素树和二叉树root，唯一的根节点无前驱，每一个结点仅有一个前驱二叉树：n个节点的有序集合满二叉树，每一层都是满的，威廉希尔官方网站完全二叉树，只有最下面两层的节点度可以小于2，且均在左边前序，中序，后序遍历树 DLR LDR LRD，层序遍历线索二叉树：利用空指针域，方便二叉树的线表示前驱或后继哈夫曼树的生成（带权路径长度取最小值的树） 把最小的两个合在一起前缀编码，任一字符的编码都不是另一字符编码的前缀 树的存储结构，顺序存储（data，parent），多重链表，孩子链表（数组存头，孩子为一维链表），孩子兄弟链表把树变成二叉树（孩子兄弟），把森林变成二叉树

　　图非线性结构，数据元素之间呈多对多的关系。一些概念：完全图，连通图，强连通图（有向），容易两点之间都有通路生成树（包含图中全部顶点的极小连通子图），有向树（一个点入度是0，其他的是1），生成森林（若干有向树组成）图的存储结构，邻接表（x-y1-y2），邻接矩阵，邻接多重表，十字链表dfs和bfs获得生成树最小生成树 Prim Kruskal算法 前者从某点开始选择最短的边 后者在全图中选择未连通的最短边拓扑排序 从入度为0的点出发，删除相应的边，更新入度关键路径 先拓扑排序，获得执行序列，每执行一个更新后面节点的值，最后再反向执行，活动最早开始时间等于最晚开始时间的节点就是关键路径最短路径 Dijkstra（单源最短路，类似于最小生成树） Floyd（每两点之间的距离，做一个表格，存储i点到j点的距离，首先假设i点经过0点到j点是否更短更新距离，一直经过到n-1点）查找查找表：同一类型的记录(数据元素)的集合。数据元素之间存在着松散的关系。为了提高查找的效率，可在元素之间人为地附加某种确定的关系平均查找长度=（平均查找成功长度+平均查找失败长度）/2静态顺序查找表，有序查找表静态最优查找树 中间的最大，让两边的概率尽可能相等 两边概率尽可能相等，中间不一定最大（二分法）次优查找树 把关键字排序后，固定关键字的顺序，再使用上述的方式索引顺序表：顺序（二分）查找目录，顺序查找块动态二叉排序树：左子树非空则左子树的所有元素小于根节点，右子树非空则右子树的所有元素大于根节点，以此类推查找和插入类似于二分，删除如果有两个孩子，需要找中序遍历的后继（前驱），其他可以直接替换或修改信息即可平衡二叉树 左子树和右子树的高度相差不超过1（利用平衡因子记录）插入后，如果超过1，从最近超过1的节点，进行LL，RR,LR,RL旋转删除，如果有两个孩子则用前驱和后继代替，如果破坏了平衡性则LL，LR等循环B树 B+树 本质上是平衡多叉树，根的范围在2-m，非叶子节点要m/2（上取整）-m（降低树的高度，减少读取外存）插入，大于对应节点就分裂，把中点往上提 删除，就是往下拉后者的信息存在叶子节点（索引和信息），前者直接存在索引上，叶子节点为空B树的根结点可以始终置于内存中，其余非叶结点放置在外存上，每一结点可作为一个读取单位插入：如果存在则返回错误，不超过m则插入，超过则分裂，把父节点读入并接，父节点超过则再裂开删除：如果删除后不够[m/2]，如果兄弟足够则从兄弟借，兄弟不够则合并键树：字符串树B+树的删除和插入只在叶子节点中进行，就是合并和分裂哈希记录的存储地址和它的关键字之间建立一个确定的对应关系，明确值域，确定映射关系哈希函数：直接定址（a*x+b)，平方取中间几位，除留余数 （mod）处理冲突的方法：线) 再哈希法 链地址法（ 公共溢出区（里面是顺序排列，如果冲突就需要一个个找）内部排序插入排序（比较 插入 移动）直接插入排序（二分比较：减少比较次数，表排序：用链表减少移动次数） 希尔排序(有序的时候插入排序的效率高，通过多次插入排序获得更好的效果，间隔5,3,1，分类排一次，减小增量排序)交换排序（左右交换）冒泡 快排（选一个中间节点，low，high，high递减直到比小，low递增直到比大，low==high停）选择排序（选出max or min 再交换）简单选择排序 树形选择排序（类似于锦标赛，赢的前进，需要重复储存胜者，比较废空间)-堆排序（用数组模拟完全二叉树的结构，辅助空间一个。从最下面开始从一个三角堆里面选出最大值，一路往上，在最下面替换最大值，再重新替换）归并排序从一个开始一直归并（较少使用在内部）基数排序多关键字排序（比如321，关键字分别为3,2,1，然后桶排）

　　外部排序多路归并（减少层数，减少IO） 但路太多会减低归并的效率（每次选出最小都需要和其他路进行对比），使用败者树，比输的留下，胜者进入父节点（和胜者树比更新的节点少，但比较次数一致）置换-选择排序 由于路太多内存可能装不下，通过败者树+本方法平均可以排序出两倍内存的段 段号不同，段大为败；段号相同，key大为败最佳归并树 不同段的长度可能不一样，即使用k阶哈夫曼树进行归并

　　笔试题型：无放回，有放回概率条件概率 P（AB）=P（AB）/P(B)二重积分

　　基础概念互斥 对立 独立 P(AB)=P(A)*P(B)全概公式：已知各种原因的概率， 各种原因导致结果的概率， 求结果的概率贝叶斯公式：已知原因的概率， 各种原因和结果一起发送的概率。求结果发生条件下， 某个原因的概率

　　加法公式：P（A+B）=P（A）+P(B)-P（AB） 乘法公式 P(ABC)=P(ABC)P(CB)P(B)先验概率： 由以往数据分析所得 后验概率：得到信息修正后的概率分布律：表示离散型随机变量 x 取各个可能值的概率 （有限个）

　　0-1分布 随机变量 x 只取 0， 1 两个值二项分布--多个概率为p的0-1分布

　　边缘分布：把另一个设置为无穷，或者全加条件分布 除于另一个维度独立性：F(x,y）=Fx(x)*Fy(y)右连续，单调不减，=0 =1收敛就有期望 方差 E(X^2)-E(X)^2

　　D(X+-Y)=D(X)+D(Y)+-2cov(X,Y)大数定律：在随机事件的大量重复出现中，往往呈现几乎必然的规律

　　中心极限定理：独立同分布随机变量的均值呈正态分布（当样本量足够大时，样本均值的分布慢慢变成正态分布，这与样本总体的数据无关）拉普拉斯 列维一林德伯格中心极限定理∶

　　x^2分布，多个相互独立且服从N(0,1）正态分布的元素相加t分布（X/根号Y/n) 近似正态分布F分布 X/n / y/n2点估计：利用一个样本来估计总体的未知参数矩估计：以样本矩作为总体矩的估计量极大似然估计：在未知参数的取值范围内取 使似然函数达到最大值的参数估计，作为未知参数的估计(写出表达式，求导等）估计量的评选标准： 无偏性（期望准确）； 有效性（方差小）； 相合性（收敛于总体）区间估计：除了参数的值，还有参数的置信区间

　　连续 lim △y =lim（f（x+△x）-f(x))=0 △x-x左连续 右连续 x- x+间断点：在去心领域有定义，但在该点不连续第一类间断点 可去 跳跃 第二类 无穷 震荡等价无穷小 比较法则 乘积 夹逼准则洛必达 极限均为0或无穷，去心领域可导 导数存在或无穷单调有界必有极限泰勒公式

　　几何意义：切线的斜率 物理意义：物理量的变化速率微分： A是不依赖与△x的量 后面那个是高解无穷小 dy=A△x

　　几何意义：纵坐标的增量可导-左右导数存在且相等可微-可导-连续中值定理

　　极值 导数=0 看二阶导，威廉希尔官方网站看左右一阶导曲线的凹凸性，下面是凹（二阶导决定）

　　不定积分 -定积分分割 近似 求和 取极限（让面积最大的矩形趋近于0）两个反常积分有一个不存在，反常积分就不存在（到无穷不收敛）定积分存在定义：连续或有界且只有有限个间断点原函数存在定理：连续就有原函数牛顿 一莱布尼茨定理 求不定积分的值，原函数F（b）-F（a）重极限f(x,y)-Ae

　　几何意义曲面和平面y=y的交线，在此点的切线斜率全微分 A和B不依赖于△x和△y

　　高斯公式散度旋度通量数列级数 部分和数列是前n项的和 当n趋近于无穷时 部分和数列收敛 发散

　　正项级数 交错级数绝对收敛 条件收敛 收敛的级数加绝对值后还收敛就是绝对收敛幂级数 收敛区间

　　正项级数 比值判别法，根值判别法（和自己比） 和别的级数比莱布尼兹准则 递减且极限趋近于0 其交错级数收敛

　　线代笔试：求A，秩，极大线性无关 行列变换代数余子式（划去某行某列，求行列式，代数加上1^(i+j)求矩阵的逆:AE-EA-1齐次：秩为n只有0解，其他有非零解 非齐次：拓广矩阵的秩和原相同，有解，小于无穷解求解的方式：先化成行最简矩阵，然后即为等式，然后令x1=X。。。求解方程，求特征值和特征向量 （A-rE）=0 （A+rE）*X=0史密斯正交化： b2=a2-b1*a1/b1*b1*b1余子式：划去某行某列（代数则加上正负）克拉默法则：Ai是第i列元素替换成常数项bi

　　某行提k ，矩阵是全k伴随矩阵：由代数余子式构成的矩阵 A*可逆矩阵 AB=BA=EA！=0 有唯一解（AX=0，只有零解） 秩为n 特征值不全为0 可以表示成初等矩阵的乘积算矩阵的秩（初等变换到E） 算逆矩阵（增广矩阵，把之前的矩阵变E 公式法A-1=A*/A）初等矩阵，单位矩阵经过一次初等变换得到的矩阵矩阵的秩：存在r阶子式大于0，并且所有r+1阶子式等于0线性相关：向量组 A 中至少有一个向量能由其他向量线性表出极大线性无关组 ：目前线性无关，再加任意一个就相关（秩，等价）施密特正交化：投影+单位化

　　向量空间：V是n为向量构成的非空集合，且满足a，b属于V，a+b∈V ka∈V 生成空间，向量空间中的向量的线性组合成的新空间齐次方程组：非零解 秩!=n 后面都是0 基础解系：维数为n-R（A） （化成行最简形状，然后指定值）非齐次有解 R（A）=r（A--） 增广矩阵 无穷解 秩比n小 唯一解 秩=n

　　特征值：λ—A=0 是特征方程的根 特征向量：(rE-A)x=0 代入结果求矩阵等价：经过初等变换可以变成，矩阵的秩相同相似矩阵：设A.B都是n阶矩阵，若存在可逆矩阵P.使得P-1AP=B.则称B是A的相似矩阵（特征值都相等）矩阵合同 A=CTBC C为可逆矩阵n阶方阵A：可对角化的充分必要条件是A有n个线性无关的特征向量实对称矩阵：实对称矩阵的属于不同特征值对应的特征向量相互正交，必可正交存在Q-1AQ=QTAQ= A矩阵的迹：对角线的和二次型： 标准型（只有二次方） 规范性（二次方系数均为1or-1） 实二次型（全为实数） 对称矩阵 xTAx

　　正定二次型 对于任意非0 x，xTAx0 半正定= 负定 不定 正惯性指数=n 和E相似，特征值均大于0对于任意一个二次型（A为实对称矩阵），存在正交变化，化二次型为标准型（变成标准合同矩阵，和其相似且合同） 变换不改变正定性，矩阵可使用史密斯正交化获得实对称矩阵：不同特征值的特征值向量是正交的正定的必要条件：标准型的n个系数均为正数正交矩阵 ：AT=A-1 行（列）向量都是单位向量且两两正交 模长是1

　　机器学习是一种通过先验信息来提升模型能力的方式。分类 回归 聚类 监督学习 半监督学习 无监督学习 强化学习(由智能体和环境两个部分组成。 智能体是行为的实施者， 由基于环境信息的评价函数对智能体的行为做出评价)训练误差 泛化误差（全部样本）强化学习强化学习的目标是通过机器学习方式有效解决序贯决策问题马尔可夫过程：未来与过去无关马尔科夫链：满足无后效性，状态可观测，转移不确定可使用，包含（状态空间、决策集合、转移概率和期望报酬 ） 针对无限阶段问题，引入0-1之间的折扣因子γ贝尔曼方程 ：策略函数，输入状态输出动作状态价值函数：从当前状态开始到最终状态时所获得的累加回报的期望SVM:小样本、非线性及高维模式识别 高维平面求最大间隔 软间隔(1-E)

　　使用拉个拉格朗日乘子法把约束变成 对偶问题（更好算，引入核函数方便） 高维映射 核函数，如高斯核函数，多项式回归 ： y=ax+b 用极大似然估计，最小二乘法，然后求导获得答案线性判别分析（LDA） 线样本投影到一条投影轴上 两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小（均值和协方差）多分类可以拆成 一对多 多对多（二分法，编码）决策树 信息增益 ID3 增益率（处于取值的个数）C4.5 基尼系数（随机抽取，类别不一样的概率） CART 预剪枝 后剪枝 属性缺失 多变量决策树 使用于大数据，多特征的数据贝叶斯 朴素（各特征互相独立） 半朴素（只有一个关联） 拉普拉斯修正（对不存在的属性，上+1，下+n，即假设均匀分布一个）贝叶斯网络Bagging 有放回随机抽取部分样本作为训练集 加权 简单平均 投票随机森林 利用bagging方法训练决策树Boosting （从初始数据集训练一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器。最后将所有基学习器加权结合 ）Adaboost ：自动优化权重和不同模型间的权重GBDT（梯度提升决策树 ）学习算法 ：每一棵树学的是之前所有树的结论和残差PCA 主成分分析方差最大，第一主成分，第二主成分。样本乘上投影矩阵

　　梯度爆炸，梯度消失梯度截断，更换激活函数，正则项，resnetK-means生成k个初始点为质心，然后将离初始点较近的点归入该类，然后重新计算质心，直到质心不变为止，每次更新可以只计算上一次迭代中距离较近的点kNN （k近邻）学习 看k个邻居属于哪一类，使用投票的方式归类 回归则求平均牛顿法和拟牛顿法 使用二阶导来收敛函数LSTM对RNN进行了改进，加了Ct。遗忘门，上一个输入和当前输入绝对遗忘什么输入门： 输入什么信息 输出门：共同决定输出什么信息

　　MLE：极大似然估计MAP：基于经验的后验估计三大相关系数皮尔逊相关系数 协方差处于方差的平方斯皮尔曼相关系数 不同的n对标差反差 d是对应位置的插值

　　命题，可以否定或肯定的陈述句逻辑连接词，真值表命题等价（吸收律等）简单析取式是只有有限个命题变元或其否定的析取构成的析取式析取范式：由有限个简单合取式（基本积）的析取构成的析取式称为析取范式主析取，是若干个极小项析取谓词（所有变量确定后变成命题） 量词（全称A，存在E） 常量，变量，函数指导变项 约束出现（闭式全为此） 自由出现前束范式：谓词全在前面 换名规则，辖域扩张和收缩 否定等值式和蕴含等值式推理规则;假言三段论，合取消去证明方法：直接证明，间接证明，分类讨论 存在性证明自由变项，个体常项----全称量词和存在量词的转换 UI UG EI EG笛卡尔乘积： 幂集定义域 陪域值域（一对一，不存在两个不同的值对应同一个值） 满射（培育等于值域） 双射（满足前两者）闭包：加上最少数量的有序对去达成某种关系自反（R∪自反） 对称（R∪R-1） 传递（R∪R2...Rn）划分成商集，不同的等价类，每个等价类有一个代表元偏序 自反 反对称 传递幂等 a*a=a子半群：子半群，如果闭合子群：单位元和幺元都在，并且所有元素的逆元也在同态：f(a*b)=f(a)+f(b)同构：一对一且满射连通图：任意两点之间有通路，补图，割点，割边欧拉回路：一笔画完所有边，顶点的度为偶数，只能有两个奇数的顶点哈密顿回路：一笔过所有点 边大于某些值则必有

　　寄存器的内容来表示。另外，进程通常还包括进程堆桔段(包括临时数据，如函数参数、返回地址和局部变量)和数据段(包括全局变量)。进程还可能包括堆 (heap)进程通信方式 共享内容 消息传递线程是 CPU 使用的基本单元（资源分配和调度的单位），它由线程 ID、程序计数器、威廉希尔官方网站寄存器集合和技组成不同进程共享文件和数据，代码响应度高，资源共享，开销小用户线程 内核线程 多对多 一对一 多对一（阻塞会出问题）CPU调度（线程）短期调度：从队列中挑进程去执行 抢占，非抢占分派程序调度的时间（上下文，选程序）分报延迟cpu使用率，各类进程的时间（周转，等待，响应），吞吐量FCFS(FIFO） SJF最短工作优先 RR 优先级调度（低优先级饥饿问题，老化，优先级随时间变化）多级队列调度，多级反馈队列调度（不同队列会变换） 高响应比优先 响应时间/runtime多处理器调度 SMP 处理器亲和性（是否允许去别的处理器） 负载均衡，拉进程来和杀进程算法评估：模拟 实现 测试样例进程同步： 进入临界区时（更新某种公共资源），需满足互斥，进步，有限等待互斥锁：又叫自旋锁（忙等待），请求，释放信号量： signal wait 会阻塞自己，不会忙等管程：简化编程，信号量顺序出错问题严重 维护一个使用队列，内部数据只能呗内部使用，一次一个使用优先级反转：低优先级的进程申请了资源，高优先级需要等待此资源，但是中优先级进程阻塞了低优先级。可让低优先级使用优先级继承（临时获得高优先级的优先级）生产者消费者 读者写者 哲学家就餐死锁：申请，使用，释放必要条件：互斥 占有并等待 循环等待 非抢占资源分类图 有环是充分不必要条件处理方法：预防或避免 检测并恢复 无视预防（打破四个死锁的条件之一)避免：时刻检测，存在安全序列才可以分配资源--银行家算法，可使用数，最大需求数，已分配数，需求数检测:类似于避免，但是把MAX改成request，恢复：中止所有进程，一个个中止进程，进行资源抢占内存管理：分配内存及内存保护，交换（把内存的东西交换到外存）基地址寄存器 界限地址寄存器编译（绝对地址）--链接（链接其他模块）--加载（加载系统库，可重定位）--执行（绑定地址，动态加载共享库）虚拟地址--内存管理单元物理地址 可充定位寄存器动态加载（共享库）：只载入存根，执行时才载入代码，也方便更新可变分区内存分配：best-fit first-fit worst-fit外部碎片（紧缩可解决）和内部碎片分段：段号，偏移量 段表（段基址，段界限地址） 超过报寻址错误分页：避免外部碎片，将逻辑地址和物理地址都分成等大的页，页码和页偏移，页表转换页码页表较大一般放在内存中，页表基址缓冲器，TLB（页表的cache） 有效位标记共享页（共享代码等） 倒置页表（只有一个表，给有物理地址的页分配表目，查表慢，减少页表重复）虚拟地址：连续，实际使用再调入物理地址帧分配算法和页面置换算法最优页面置换算法（理想） FIFO，LRU（最近最少使用），近似LRU（只保存八位，001000，第二次机会算法只保留一位，使用过置1，被选择替换时置0，如果是0则被替换）帧分类的数量要达到应用的最小分配数，不然就是会缺页率过大进程太多会抖动（全局置换时）单级目录-双级目录--树目录-通用目录 共享文件，分布式文件系统（安全）

　　第一章概述自主计算机互联的集合体OSI 应用，表示，会话，传输，网络，数据链路，物理TCP/IP 应用，传输，网络，网络接口

　　物理层 信号转换（数字-模拟） 时延 衰减 噪音奈氏准则 C=BlogV 码元的相位 调幅 调频 调相香农定理 C=Hlog2（1+S/N) S/N 信噪比曼彻斯特编码（差分） 两个码元表示一个bit 中间从上往下还是从下往上多进制编码 mB/nB编码频分复用 波分复用 时分复用 码分复用双绞线 光纤 同轴电缆 无向介质（短波，微波）报文交换 电路交换 分组交换同步方式 帧同步 位同步（外加信号，特殊编码，如物理层编码违例法）字符同步 带字符填充的首尾字符定界法（FLAG定界，ESC区分） 带位填充的首尾标记法（每五个1后插0,011111定位）纠错 反馈纠错 前向纠错 海明码（每2n插0 or 1，n+1识别，2n+1纠错）循环坑余编码（CRC，模除为0） 奇偶校验码数据链路层 调节速度停等协议 实用的停等协议 滑动窗口 回退N帧ACK NAK 超时重传 连续确认纯ALOHA 时隙ALOHA CSMA 1-坚持 p-坚持 非坚持（生成随机数时间后监听）CSMA/CD 冲突检测，检测到停止 2个竞争周期无竞争 基本位图协议（n个位代表传不传） 二进制下数法（d个位表示一个数，谁大谁传）有限竞争 上面两者结合无线竞争 MACA 隐蔽站和暴露站的问题二进制指数退避算法 发生冲突后退避一段时间 2^n时槽 n为冲突次数 到16次后网络不可用CSMA/CA 无线冲突竞争=MACA+二进制指数退避点协调（PCF，无立马可发） 分布式协调（一个PCF时间后可发，竞争）请求发送RTS 允许发送CTS 带有源地址 目的地址 通信时间各种线-BASE-X 光纤10BASE-T 100BAST-TX 1000BASE-T 双绞线网络层 网桥透明网桥 逆向学习+扩散算法 记录源端，时间，超时丢生成树网桥 坑余/备份网桥 从根开始，使用最小生成树生成路径，若网桥故障重新生成远程网桥（跨越不同的网络） 两边同，装到大帧里面 两边不同，拆装拆VLAN 多加一个四个字节的VLAN标记动态路由算法距离矢量路由算法 自测 得表 发表（老表） 出现坏表 计数到16就不可达，不把消息传回发消息的人链路状态路由算法 发现邻居 echo算延迟 创建链路状态分组扩散 获得拓扑图（计算dijkstra）32位序号，只收大的，但记录有生命周期（防重启）分级路由 解决路由太多，但是可能不是最短路无连接vs有连接 需要建立和释放链路，有QOS 结点故障会影响 按顺序到达 分组无地址拥塞控制流量感知路由 准入控制 资源预留 分组调度（FIFO，公平队列）流量限流 会带有警告位的ack，让源端降低速度，但警告位减少，恢复速度负载丢弃 随机丢弃，优先级 丢老丢新抖动控制 到达时间的变化量流量整形 漏桶算法 令牌桶算法Q0S 可靠 延迟 抖动 带宽分段/分片 透明分段 每一段网络都要拆开重组不重组，偏移量法 偏移量（偏移量），标识（最后一帧标1）传输层 端到端可靠通信，识别具体应用socket套接字 IP+端口号寻找端口号方式：知名端口号，进程服务器，名称服务器建立链接 三次握手 带有序号 SYN seq=x-SYN seq=y，ack=x-DATA seq=x+1,ack=y释放链接 四次挥手 短计时器超时重发，长计时器超时释放链接TCP提高效率 缓存超过一半或收到ACK才发 具备一半以上空缓存才发ACK拥塞控制 最大最小公平 每个session平均 快重传 收到三个ACK3 重传报文平均往返时延 RTT=A*RTT+（1-A）（新时间）超时重传时间 RT0=B*RTT

　　第二章：原码，反码，补码（取反+1），移码（+2^n)浮点数：对阶，相加减，规范化第三章：存储分层 cpu 寄存器 cache 主存 外存RAM SRAM DRAM（需要更新，刷新策略，集中，分散）ROM 存储器交叉组织cache映射 全相联(查表，命中高，但是慢） 直接映射(hash) 组相联（hash分组后全相联）cache替换 随机替换 FIFO 计数器（年龄技术器（访问+1，选min） 最近最少使用（选中其他+1，选max，选中清零）写回法 只写入cache 写直达 写入cache和内存写更新 写作废（写的时候是否更新别的cache的内容）第四章：CISC-RISC 少用指令，删除可以拆分的指令 长度固定 提高译码速度，减少访存立即寻址 寄存器寻址 寄存器间接寻址 直接寻址 间接寻址偏移寻址（相对寻址 PC，基址寻址 基址寄存器，变址寻址 变址寄存器）段寻址 低四位为0000，+16位偏移量第五章：CPUAR ALU IR PC DR 通用寄存器指令周期 CPU周期 时钟周期（多级时序体系），异步控制，同步控制，组合控制+控制器的实现方式：硬布线 微程序（微指令，控存存一堆的微程序）微程序的实现 水平型（一次多个，01010或者多个互斥的编码对，竖直型（一次一个））流水 瓶颈段再细分 重复设置瓶颈段资源相关（暂停，设置更多的资源）数据相关（动态调度，定向技术，静态调度）名相关控制冲突（前瞻预测，分支历史表，分支目标缓冲器，冻结排空流水）总线分配：请求 仲裁 寻址 传送 返回 令牌 冲突检测 仲裁： 优先级I/O与外设 无条件传送 同步传送 异步应答方式CPU与I/O 简单I/O 轮询 中断驱动DMA（请求，排队，总线请求，总线响应） DMA代理进行字符技术等功能通道 外围处理机中断 菊花链 计数器 中断请求 响应 保护现场 恢复 开中断 中断返回Cache 的更新 随机替换 FIFO LRU 被访问一次清零，选最大 被访问一次+1，选最小

　　关系代数 选择 投影 笛卡尔积 连接（自然连接） 集合运算 赋值 更名运算 sum count min maxSQL select（disinct）as from where group by having限制 数据限制 not null 主键，外键等限制交并补差 或与非删除 更新 插入view 物化视图授权 read insert update虚实体集 无主健，需要依赖XX堆 有序 hashACID 原子 一致 隔离 持久性可串行性可恢复性 用了别人的数据，别x了也得x不能读取别人写的数据互斥锁 共享锁二阶段锁协议 强 互斥锁只能在结束的时候释放 严格 都只能在结束的时候释放最大化投影，早点选择，小的先连接1NF (表都是原子的） 2NF（非主属性完全依赖于主属性） 删除信息重复3NF（没有非主属性的传递依赖） BCNF（任何属性不存在传递和部分依赖） 方便删除修改正则覆盖 联合表达式 删除所以的可导出关系无损连接（表自然链接后相同） 依赖保存（所有的关系合并后同）求BCNF和3NF 先求正则覆盖，把不满足的找出，拆解成新关系求候选键 只在左边出现 未出现（左边都放，逐个放右边的内容） 在在右边出现 LR

　　高级语言-汇编语言-机器语言词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成词法分析程序输入缓冲区 分两块轮流 用一个自动机匹配语法分析程序 记号流-分析树LL(1) 消除左递归，提取左公因子，构造FIRST和FOLLOW集，每一个符号FIRST放入，FIRST有e，FOLLW放入LR LR（0） SLR(1) LR(1) LALR(1)移进 归约 接受 错误处理拓广文法 S‘-S A-a*Bb 展开BGoto 非终结符 action 终结符FOLLOW集，下一个字符解决冲突LALR（1） 合并同心集，不看向前看的符号合并，可能多归约，引入归约-归约冲突消除二义性 优先级，最近最后匹配原则语法分析综合属性从孩子处 继承属性从兄弟或父亲S属性：只有综合属性（LR） L属性：综合+左兄弟（LL）中间代码生成 三元式，四元式参数传递机制 传值调用 引用调用 复制恢复 传名调用名字等价（类型名相同） 结构等价（类型内容相同）基本块划分 三地址代码第一条 goto要去的语句 goto的下一条语句活跃变量要寄存器，假设最终是活跃的，往回推基本块的优化 常数传递，删除死代码，删除公共表达式，削弱计算强度，改变计算次序循环优化 代码外提 削弱计算强度 删除归纳变量0型（无限制，左边有非终，右边有终结）1型（左边小于右边）2型（左边只能是非终）3型文法（这则文法，左线性，右线性）