1）总线是一组能功能部件之间分时共享的公共信息传送线路。分时、共享是它的两大特点。
2）分时是指同一时刻只能有一个部件向总线上发出信息。
3）总线分为三大类：片内总线、系统总线（数据总线+控制总线+地址总线）、通信总线。
4）通信方式分为：异步通信和并行通信。
5）一些特性：功能特性、电气特性、机械特性、时间特性。
（1）CPU和外设之间数据传输的方式，外部设备发送DMA请求，CPU同意之后就让出总线控制权，DMA控制器接管总线控制权之后开始进行外部设备与内存之间的直接数据的，CPU不再作为中枢。比较适合大量数据的传输，跟中断相比减少了中断请求、相应、保存上下文（即环境）的时间，使得资源利用率以及吞吐量更大。
（2）DMA请求、DMA响应、数据传输、DMA结束
（预处理-->数据传输-->后处理）
五级流水线指的是：取指、译码、执行、访存、写回五个操作。
1）取指：
指令取指（InstrucTIon Fetch）是指将指令从存储器中读取出来的过程。
2）译码：
指令译码（InstrucTIon Decode）是指将存储器中取出的指令进行翻译的过程。经过译码之后得到指令需要的操作数寄存器索引，可以使用此索引从通用寄存器组（Register File，Regfile）中将操作数读出。
3）执行：
指令译码之后所需要进行的计算类型都已得知，并且已经从通用寄存器组中读取出了所需的操作数，那么接下来便进行指令执行（InstrucTIon Execute）。指令执行是指对指令进行真正运算的过程。譬如，如果指令是一条加法运算指令，则对操作数进行加法操作；如果是减法运算指令，则进行减法操作。
在“执行”阶段的最常见部件为算术逻辑部件运算器（ArithmeTIc Logical Unit，ALU），作为实施具体运算的硬件功能单元。
4）访存：
存储器访问指令往往是指令集中最重要的指令类型之一，访存（Memory Access）是指存储器访问指令将数据从存储器中读出，或者写入存储器的过程。
5）写回：
写回（Write-Back）是指将指令执行的结果写回通用寄存器组的过程。如果是普通运算指令，该结果值来自于“执行”阶段计算的结果；如果是存储器读指令，该结果来自于“访存”阶段从存储器中读取出来的数据。
1）五级流水CPU就是在多周期CPU的基础上+流水线思想-------->实现并行。
2）传统的单周期CPU是指指令在一个时钟周期（即时钟到来一次）内执行完成，包括所有的操作。但这里存在的确定就是时钟周期的时间是固定的，所以时钟周期的时间应该是最长的指令所需要的时间，对于那种很短的指令，就会造成浪费。引入多周期，这时就可以减少浪费的时间。
3）单周期CPU（是指在一个时钟周期内完成这五个阶段的处理）。因为五级流水CPU中每一个操作的流水时间是一样的，取得是这五步中的最大执行时间，那么就是最大操作时间*需要执行的操作数目（取指、译码、、、）。
4）因为只有一条指令嘛，所以单周期最快，多条指令是考虑流水线比较好。
东南大学面试题目：
（1）归并排序，内部排序（排序方法在内存中进行），外排序为什么不用多路归并。
内部排序有：
1）插入排序：简单插入排序、折半插入、希尔排序（增量法）。
2）交换排序：冒泡排序、快排
3）选择排序：简单选择排序、堆排序。
4）归并排序
5）基数排序
不稳定的排序有：快排、选择排序、堆排序、希尔排序
外部排序：
为什么用败者树不用胜者树：因为败者树某结点改变之后只需要跟它的父节点进行比较直至根节点即可，但是胜者树还要跟他的兄弟结点进行比较，编程不易实现。
（2）AVL平衡树旋转，从一个状态插入、删除一个数时，最多旋转几次。
1）插入一个数，最多旋转两次LR型，或者RL型。
2）删除一个数，也最多是两次吧。
（3）二叉树，证明二度节点数与零度节点数的关系。
边数目=n0+n1+n2-1;
度=n1+2*n2;
边数目=度
--->n1+2*n2=n0+n1+n2-1
n0=n2+1;
（4）回文链，设计一个算法证明一个链时回文链，使得时间复杂度为O(n)空间复杂度为O(1)。
快慢指针法/暴力破链法。
*推导：慢指针进入环后，快指针最多多绕一个圈。
快指针F先进环，慢指针S后进。
假设慢指针进环那一刻快指针差m步能追上（0<= m < Length环），根据上边结论，两个指针走m次就会相遇了。
因为m < Length环，所以快指针在慢指针进环那一刻最多比慢指针多绕一个圈。
（5）最短路径算法，具体实现中的细节小问题。
1.迪杰斯特拉算法(从该结点出发到其他节点的最短距离)。O(n^2);
需要：visited[]、D[]、path[]、arcs[][];
应用：网络层协议中开放最短路径优先协议OSPF，计算最短路由用的是该算法。
2.弗洛伊德算法（任意两个结点之间的最短距离：动态规划，O(n^3);
需要：arc[][]
（6）最小生成树。
1.prim算法：加点法
从某点出发的最小生成树，如果想要任意点出发求出的最小生成树相同，那么必须满足该树中没有相同长度的边。O(n^2)，与边无关，适合稠密图。
需要：closedge[j].adjvex数据结构(加入生成树后需要将值变为0，以便于后续更新)存储已加入的结点跟j结点直接相连最小距离的结点下标，closedge[j].lowcost为改该最小值。
2.克鲁斯卡尔算法：加边法
将边先进行排序，并用v去记录每个点的连通分量，每次选择与已选边的连通分量不同的且边长度最短的边。选择后要更改相应的连通分量一致。O(e*log2e)，与点无关，适合稀疏图。
需要：edge数据结构
struct Node{
Node head;
Node tail;
ArcType lowcost;
}Edge[arcnum];
以及Veset[]表示连通分量，初始时为各自点的下标。
for循环遍历边的数目，这里不用担心超出，因为会有连通分量的控制，所以必定选不了所有的边！，甚至自己还可以加一个变量，选购了vexnum-1条边就撤也行。
（7）拓扑排序。
有向无环图，可以用来判断图中有无环，使用indegree记录每个结点的入度
需要：indegree[]、stack（临时保存拓扑排序过程中入度变为0的结点）、topo[]保存stack中出来的，同时m记录topo中的结点数目，判断最终是否存在环。
（8）关键路径。
1.首先对AOE网进行拓扑排序（O(n+e),得到的拓扑排序序列存在topo[]中。
2.求每个事件的最早开始时间ve[],先初始化为0,然后根据topo[]从头到尾遍历每个事件i,内循环遍历i的每个邻接点j,若ve[j]<ve[i]+weight--->ve[j]<ve[i]+weight,根据前面改后面。
3.求每个事件的最晚开始时间vl[],先初始化为汇点的最早开始时间ve[n-1],然后根据topo[]从后往前遍历每个事件i,内循环遍历i的每个邻接点j,若vi[i]>vl[j]-weight--->ve[j]<ve[i]-weight,根据后面改前面。
4.最后遍历所有结点i，每个结点在遍历其邻接点j，计算活动<vi,vj>的e[]=ve[i]、l[]=vl[j]-weight。若e[]=l[],为关键路径。
5.从源点到汇点全为关键活动的路径为关键路径（从源点到汇点戴权路径长度最大的路径）,可能存在不止一条关键路径的情况。
****6.若不止一条关键路径，必须同时缩小每条关键路径上的关键活动的时间才能保证提高速度，一条不行。
（9）二叉排序树。
1.注意：不允许存在值相同的元素！
2.构建、插入、都基于搜索。（递归即可）
3.结点的删除分三种情况：O(log2(n))
（1）删除结点为叶子结点，f->lchild=NULL即可。
（2）删除结点仅有左子树/右子树为，f->lchild=p->lchild/rchild即可。
（3）删除结点左右子树均有：1）可以用左子树最右结点/右子树最左结点，即用被删结点的直接前驱/直接后继代替被删结点即可。2）或者可以用左子树代替该节点，该结点的右子树成为该左子树的最右结点的右子树。（但是这样会增加数的深度，一般不采用）。
（10）平衡二叉树。
1.二叉排序树+平衡因子（|depth（左）-depth(右)|<=1）
2.插入结点、删除结点均需要判断、调整二叉树。
3.插入：假设插入左子树上，并使其平衡因子+1。
1）可以采用递归的方式：若树根节点为NULL,则可以直接作为根节点。
2）若跟根节点值相同，放弃。
3）若插入前该子树根节点平衡因子为：-1，则变为0，若为0，则变为1。
4）若插入前该子树根节点平衡因子为：1,则为LL型，进行一次右旋即可。
5）若插入前该根节点左子树平衡因子为：-1,说明为LR型。先左旋再右旋。
为什么有了平衡二叉树还会出现B-、B+、红黑树呢？
因为平衡二叉树太严苛了，每次插入或者删除都有可能涉及树的旋转等操作，太浪费资源了。
所以提出了不那么严苛的这些。
（11）B+树。
1. m阶B+树指的是非终端结点最多有m个子树（m个关键字），根节点非叶子结点的情况下至少
有2个子树，其他非叶子结点至少有（向上取整）（m/2）个子树，Pi表示子树中的值均小于等于关键字Ki
（12）B-树。（即B树）
1. m阶B-树指的是非终端结点最多有m个子树（m-1个关键字），根节点非叶子结点的情况下至少
有2个子树，其他非叶子结点至少有（向上取整）（m/2）个子树，Pi表示子树中的值均大于关键字Ki，Pi-1表示子树中的值均小于关键字Ki。
2. 插入时先找插入位置，插入后看关键字是否>m-1，大于则从中间关键字处分成两个子树，该节点自成一颗子树，若该子树非根节点，则需要跟其原来父节点合并，若合并后超过m-1个关键字在进行分解即可。
3. 删除时找到对应位置，若删除的是最下层的非终端结点，则只需要看该结点内部关键字是否小于m/2-1即可，小于的话看起兄弟是否>m/2，大于的话，让其父节点关键字下来加入该结点中，兄弟结点关键字上去一个。但如果其兄弟都不行，那就只能父节点下来跟该结点和他的兄弟结点一起成为一个结点。
为什么数据库索引用B+树而不用B-树？
因为B-树中间节点存数据，而B+树中间节点存的是索引，在叶子结点存数据。他们的树都存储在外存中，I/O每次读一个页面进内存，当然是B+树中每个节点的孩子数就越多，整个树的高度就低，大大减少了查询的时间。并且B+树叶子结点有序存在一个链表中，适合范围查询。
（13）红黑树。
1. 必须存放在内存中，所以像数据库那种要处理的文件是很大的就不能用红黑树，还因为红黑树层数大（而且属于二叉树），I/O操作太多次了。
为什么会推出红黑树呢？
红黑树看起来也是二排序树的一种，只不过是跟平衡二叉树相比没有那么严苛。平衡二叉树为了为了提高查找的速度，严格限制了树的结构，使得插入、删除非常的耗时。
（14）散列表。
1. 散列函数
2. 处理冲突的方法：开放地址法（线性探测法（+i、-i）%(表长)、二次探测法(+i^2、-i^2)、伪随机探测法）、链地址法
（15）线索二叉树。
好处：中序遍历不需要堆栈,空间复杂度为O(1)。以及每个节点可以很方便的找到其前驱和后继结点。
缺点：插入删除麻烦，费时间。
（16）哈夫曼树。
编码树
struct{
int weight;
Type parent;
Type lchild;
Type rchild;
}
（17）时间复杂度、空间复杂度的计算。
特别的！
1. 时间复杂度
(1) O 表示的是数量级，即算法中语句频度f(n)的最高数量级。
递归通用计算时间复杂度的公式：
T(n)=a*T(n/b)+f(n); 前提：a>1&&b>1
if O(n^(logb(a)))>O(f(n))--->O(T(n))=O(n^(logb(a)));
if O(n^(logb(a)))==O(f(n))--->O(T(n))=O(f(n)*(logn));
if O(n^(logb(a)))<O(f(n))--->O(T(n))=O(f(n));
2. 空间复杂度（注意！递归是用到的栈也是空间，莫忘记!）
算法所需存储空间的量度。
（1）线程：是轻量型进程，由进程创建，是系统进行独立调度和分配的基本单位，线程会与同属于一个进程的其他线程共享该进程所具备的资源，但是线程本身也具备一些自己特有的信息，比如程序寄存器等。
（2）进程：是系统进行资源分配的基本单位，创建一个进程，系统会为其分配相应的内存空间等资源。（我们平时用的exe类型的就是一个进程，比如WeChat和QQ以及浏览器）。一个进程可以拥有一个或者多个线程，线程的引入增加了并发度。
（3）举个栗子（比喻句）：就像是火车与车厢一样。
1. 线程可以看作是轻量级进程，其是处理器调度和执行的基本单位。一个进程拥有>=1个线程，同一个进程拥有的线程共享该进程所分配的资源，地址资源以及CPU资源等，线程之间可并发执行。
2. 出现线程的原因是进程是拥有资源分配的基本单位，进程上下文切换所需时间太多，基于此，产生将“资源分配的基本单位”与“处理机调度的基本单位区分开的想法”。
3. 使得并发度提高。
线程分类：内核级线程、用户级线程
1. 内核级（KLT）线程：
（1）线程的创建、切换、调度都是在操作系统内核实现的。
（2）优点：一个进程中的线程被阻塞了，还可以调用该进程中的其他线程。
在多处理器中，内核可以调用同一个进程中的多个线程同时进行处理。
（3）缺点：一个进程中的线程之间进行切换（切换代价大）时，需要从用户态--->内核态-->用户态，因为切换实在内核实现的没所以费时。而且线程的创建费时间。
3. 用户级（ULT）线程 ：
（1）线程的创建、撤销、切换、管理都是在用户空间进行的，无需内核支持，内核甚至并不知道这些线程。
（2）优点：线程之间的切换不需要转换到内核态，节省了内核空间、也节省了时间。
用户级线程的实现和操作系统无关。
（3）缺点：一个进程中有一个线程被阻塞了，该进程就被阻塞了。一个进程只能在一个CPU上获得执行。
为什么会这样呢？
答：是因为操作系统内核根本不知道线程的存在，他只看得到进程，所以在他眼中是进程被阻塞了。
1. 操作系统的作用：
（1）操作系统是系统资源的管理者。
（2）操作系统是用户和计算机硬件系统之间的接口。
（3）操作系统实现了对系统资源的抽象。
2. 操作系统的功能：
存储器、处理器、文件、设备等的组织和管理，提供用户和计算机系统之间的接口。
3. 操作系统的特性：
（1）并发性：区分并行和并发，并发性指的是系统中同时存在多个运行的程序。在这里操作系统引入进程的目的是实现并发。
（2）共享性：指的是资源的共享，是指同一资源可为多个并发执行的进程所共享。
两种共享的方式：互斥共享（临界资源）和同时访问
（3）虚拟性：时分复用技术（分时系统）和空分复用技术（虚拟存储技术）
（4）异步性：指进程并非一次性执行完，而是走走停停已不可预知的速度向前推进。
1. 作业的调度算法（高级调度）
（1）FIFO
（2）SJF
（3）优先级调度:可剥夺式、不可剥夺式（静态优先级、动态优先级）
**********（2）、（3）存在饥饿情况。*******************
（4）高响应比优先：（等待的时间+要求服务的时间）/(要求服务的时间)=（响应的时间）/要求服务的时间=1+等待的时间/要求服务的时间
其中FIFO、SJF、优先级调度均可用于进程和作业调度。
高响应比优先多用于作业调度。
2. 内存的调度（中级调度）
3. 进程调度（低级调度）
（1）分时系统中的时间片轮转调度：其中时间片的大小设置极为重要，太大就变成FIFO算法了，太小就一直进行进程的上下文的切换，浪费时间。时间片大小最好就是：略大于典型交互的所需的时间，使得大部分的进程可以在一个时间片内完成。
（2）多级反馈队列调度算法：时间片轮转算法+优先级调度算法+先来先服务
1）多级反馈队列中有1~n个优先级依次递减的队列，随着优先级的递减，时间片长度加倍。1~n-1中每个队列都是FCFS进行调度，最后一个队列是时间片轮转调度。
2）当且仅当1~i-1个队列均为空时，才会去调度第i个队列的进程。
3）新来的进程会进入第一级队列的末尾，按照先来先服务去调度，等调度它时，如果一个时间片之后进程执行结束，那么进程就结束。否则进程会进入第二级队列的末尾等待执行，如果一个进程一直执行等待执行等待到了第n级队列，在第n级队列是按照轮转调度执行。
4）优点：
终端型作业用户：短作业优先。
短批处理作业用户：周转时间较短。
长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。
1. 死锁的定义：产生死锁的一组进程中的每个进程都在等待该组进程中其他进程所拥有的资源，使得所有的进程都无法向下推进，即为自锁。（专业定义就是：形成的资源分配图（无环）无法化简完全）。
2. 死锁产生的原因：四个原因，互斥性、不可剥夺、请求和保持、循环等待。
3. 解决死锁的四种方法：
（1）死锁的预防：破坏死锁产生的三个（互斥性一般无法破坏）条件之一即可。
1）破坏不可剥夺条件：或者如果所请求的资源无法满足，那么之前具有的也会释放。
2）破坏请求和保持条件：必须一次性将所需要的资源全部分给它，如果无法全部分配就一个也不给。
3）破坏循环等待条件：给资源编号，顺序资源分配法。在过程中，只要申请了资源编号为Ri的资源，以后的申请就只能申请资源编号大于Ri的。
（2）死锁的避免：安全性检查算法。先看能不能给他，再假设给他，看是否存在一条安全性序列，不存在的话就不安全。（不安全的状态有可能会导致死锁，安全状态不会的）。
（3）死锁的检测：构造资源分配表，看是否能够化简完全（即看是否存在环路）。
（4）死锁的解除：一般是撤销一部分进程使得死锁解除。
4. 死锁的避免（安全性检查：银行家算法）
（1）首先判断资源的请求是否正确：即首先请求的资源<=需要的资源数并且系统具有的资源>请求的资源。
（2）安全性检查：然后假设分给它，看是否会进入不安全状态。
主要涉及内存空间的分配与回收、地址的转换、内存空间的扩充（覆盖和交换）、存储保护
其中覆盖技术：是指同一个进程内进行的，不需要将所有的数据全部移入内存，分为固定区和覆盖区。现代技术改为虚拟内存技术。
交换：指的是进程之间的，是中级调度，将阻塞的进程调出到外存中去。
1. 连续的内存分配（每个进程分配连续的空间）
内存中的剩余空间用一张空闲分区表存储记录
（1）单一连续分配：每次只有一个进程进入内存，为其分配连续的地址。简单、但是利用率很低。
（2）固定分区分配：
1）分区大小相同：就是将内存分成大小固定且相同的分区，每个进程占用一个分区。好控制，但是会产生内部碎片。
2）分区大小不同：就是分为一部分小分区、中分区、大分区。
（3）动态分区分配：不事先将内存分区，按照进程所需空间进行动态分配，分区个数和大小会一直变化。有四种算法，在过程中会利用交换的方式，将目前不会运行的进程换出，会产生外部碎片，可使用动态重定位寄存器进行紧凑，但是费时。
1）首次适应算法2）循环首次适应算法
这两个都是将空闲分区按照地址从小到大链接起来，1）是从头开始选择第一个满足请求的空闲分区。该算法是最简单且最优的，但是会造成低地址部分有很多碎片，而且每次查找都会先查找这些碎片，增加了查找的开销。2）是从上一次找到的空闲分区中的下一个分区开始找到第一个满足请求的空闲分区。
3）最佳适应算法：将空闲分区按照从小从小到大来链接起来，从头开始选择第一个满足需要的分区。会产生很多外部的小碎片无法利用。
4）最坏适应算法：将空闲分区按照从从大到小来链接起来，从头开始选择第一个满足需要的分区。缺点是大作业无法进入。
注意：1. 基本分段式和基本分页式的区别在于：基本分页存储管理是站在计算机的角度考虑的，不具备逻辑性，以增加内存利用率为主，地址的变换由硬件决定。
2. 但是基本分段式是站在用户程序员的角度来的，是具备逻辑性的，有利于信息的共享，只需要在段表中增加一个段表项即可进行共享段。
2. 非连续的内存分配管理（重要）（每个进程分配的空间不是连续的）
（1）基本分页式（地址是一维的）：
1）将每个进程都分成若干大小相同的页面，内存分成大小相同的页框。每个进程都有一个页表，是用于形式地址到物理地址的映射。
2）页面的大小需要注意：页面越小会使得碎片大小越小，内存利用率越高，但是会使得每个进程占用的页面个数增多，页表过大，占用内存的同时也会增加硬件地址转换的开销。页面过大会使得页面内碎片变得过大，内存利用率降低，但是页表长度小而且地址转换速度快。
所以需要在时间和空间进行权衡。
3）引入块表机制，在高速缓冲寄存器中建立块表（TLB），利用程序的局部性原理提高地址转换的速度。
地址变换是由硬件自动完成的！
页表太长，则将页表也分页，不再连续存储，两级页表机制。第一级页表中存放的是下一级页表的起始地址
（2）分段式（地址空间两维：段号+段内地址，因为每个段的大小不一致，所以一定要都有，我们段表中有段号、段长度、本段在内存的起始地址）：对进程进行逻辑的分段，易于理解以及进程对段的共享。
（3）段页式存储管理方式：段号+页号+页内地址，每次访问都需要访存三次。
3. 虚拟内存技术（多次性、对换性、虚拟性）
（1）请求分页式内存管理技术
1）涉及请求页表机制
2）缺页处理机制
3）页面置换算法（也内存无剩余页面的时候进行换出）
*先进先出FIFO：无逻辑性，先来的以后不一定用的就少。效果不佳。会出现Belady异常。
*最佳置换算法（OPT）：已知未来的情况下。向后看，未来最晚使用的就将它置换出去，但是这很难实现，需要提前知道访问页面的顺序。
*最近最久未使用LRU：最近长时间未访问过的页面。向前看，看最后一次访问的页面最早的那个换出。用最近的过去去预测最近的将来。硬件实现，用寄存器进行实现，每个进程有R7~R0寄存器进行表示，每次访问都将最高位置为1，然后其他未被访问的值向右移动一位。效果最好，但是硬件需求高。
*时钟Clock置换算法：产生的原因是，LRU算法性能好，但是其实现苦难，需要高硬件支持，FIFO好实现但是性能差，OPT难实现。所以想找一个新能接近于LRU，但是开销尽量小的算法。
在缓冲区中进行循环查找类似时钟，故称之为时钟Clock算法，它为每个页面都设置了一个访问位。
即产生Clock各种变体。是将进程用链表的形式链接成一个环，每个页面有一个访问位A，访问了就置为1。clock算法是每次从一个页面开始检测访问位，若为0则将其换出，若为1则将其置为0，给他一次驻留内存的机会。
*改进的时钟Clock置换算法：在Clock基础上再增加一个修改位M。因为我们知道我们每次将页面换入内存的时候，外存有我们页面的副本，如果内存中的页面未被修改，那么就不需要换出后写回外存，否则需要重新写回外存，替换原有的页面，相比之下要耗费时间一些。所以我们把它看作是第二级条件。
跟Clock相同成链后，首次找A=0，M=0的，即未被访问的换出，不做任何其他操作，找到就换出即可。第一遍未找到，我们第二遍找A=0，M=1的，此时将遇到的所有A=1，M=1的都置为A=0。若还没找到，则开启第三遍，找A=0，M=0的，若还没找到，则开启第四次找A=0，M=1，则一定可以找到。
（2）驻留集：系统为该进程分配的页框就称为该页面的驻留集。（驻留在页面中的集合）
页面分配方式：
1）固定分配局部置换：每个进程分配固定个数的页框（物理块），缺页时置换出他所分配的页面。
2）可变分配全局置换：缺页时，为新调入的页分配系统剩余的空闲物理块。
3）可变分配局部置换：在这里置换还是从它拥页面中选择去换出，不会影响其他进程。在进程执行的过程中，如果频繁缺页，可再为其分配物理块。若缺页率很低，可收回他所拥有的若干物理块。
（3）抖动：是指为每个进程分配的物理块太少了，导致缺页率激增，频繁执行I/O操作进行页面的换进换出，使得CPU几乎无法做任何有用的工作，我们称之为抖动。
（4）工作集：是指一段时间内，进程要访问的页面的集合，它由时间和工作集的窗口的大小决定，一般工作集的窗口会设置的大一些，但是由于进程具有很好的局部性原理，所以工作集一般不会很大。如果进程的驻留集<进程的工作集，那么就会发生频繁的缺页情况。所以一般驻留集的大小>工作集的大小。
注意学科结合：给你虚拟地址、物理地址、TLB、data Cache以及内存到data Cache的映像方式，TLB大小，页面大小，虚拟地址、物理地址长度，可以进行寻址。
（1）首先先找出物理地址，利用我们的虚拟地址、映像方式、TLB条目数、去TLB中找页表项，找到即可求出相应的物理地址。操作系统知识。
（2）由物理地址根据data Cache以及映像方式找到数据。组成原理知识。
首先要明确，磁盘也是分块的，但是这里的块是虚拟的，我们认为的最小单位
1. 文件分配的方式
（1）连续分配方式：给每个文件分配连续的盘块，记录该文件的表项含有文件名、文件其实盘块地址、占有的盘块数目。
缺点：只适合文件大小固定不变的情况，会产生外部碎片，文件大小改变时，需要移动大量的数据。
（2）链接分配的方式：包括隐式链接和显示链接。
1）隐式链接就是每个盘块有指向下一个盘块的指针，每个文件只需记录文件名、初始盘块的地址以及最后的盘块的地址即可。解决了产生碎片的问题。
缺点：如果中间指针除了错误，就产生文件数据的丢失。
2）显式链接就是磁盘有张FAT表，里面显式的记录了每个盘块指向的下一个盘块号的指针。还可以用特殊的数字记录哪些盘块是空的（-2）等。
优点：FAT表在启动时会被装入内存，查找速度很快且大量减少了I/O操作的次数。
1）和2）的缺点：解决了连续分配方式产生外部碎片，但是无法直接访问一个盘块，只能进行顺序访问。
（3）索引分配的方式（是指对）：想实现直接访问盘块，不需要再顺序访问。为每一个文件分配一个索引表，表中记录了为该文件分配的每一个磁盘块的地址。索引表的第i个条目指向该文件的第i块。（相当于数组）所以要访问文件某个块时，直接找到相应的索引表的相应条目即可找到地址。（第i块---->第i个条目）。
2. 文件存储空间的管理（空闲盘块的管理）：
（1）连续组织方式：空闲表法，用空闲表去存储空闲的区域。具体的分配算法跟内存中连续存储管理中的动态分区分配法相同。包括首次适应、循环首次适应、最佳适应、最坏适应。回收后要进行相应的合并。
（2）空闲链表法：根据链接的单位不同，可分为：
1）空闲盘块链：将空闲盘块作为基本单位形成一个链，每次请求都从链表头部开始分给它适当个数的盘块。每次回收将回收的空闲盘块链接到链表的末尾即可，这种操作对于分配和回收操作非常的方便。但是对于一个文件分配块时要经过多次操作。
2）空闲盘区链：是以分区为单位进行链接的，每个空闲分区不仅有指向下一个空闲分区的指针，还记录了该分区包含的盘快数目。分配和回收的方法跟内存连续分配方式中的动态分区分配算法很像，他们采用的调度策略也相同。（通常采用首次适应），回收也要进行合并。
（3）位视图法（已知每行的位数去求即可）：磁盘中的每一个盘块都有一个二进制位表示状态，0表示空闲，1表示被使用。我们用二维数组记录。
分配：遍历位视图，找出值为0的若干块，根据行号、列号计算盘块号并修改位视图的值为1。
回收：根据盘块号求出行号、列号，修改位视图相应位置为0即可。
访问磁盘的基本单位是扇区！
1. 磁盘有盘面、磁道、扇区、柱面。
2. 柱面：指的是同一个磁道不同磁面。
3. 存一个数据，如果一个磁道存不下，剩余的是存在同一个盘面不同磁道好还是存在不同盘面同一个磁道（即同一个柱面）好？
答：肯定是后者好，不许要移动磁头臂，只需要系统磁头读取数据即可。
4. 磁盘地址用"柱面号·盘面号·扇区号（或块号）"表示
5. 磁盘调度算法：
注意：一次磁盘调度所需要的时间=寻道时间（包括启动磁头臂的时间）+旋转延迟（找到相应的扇区）的时间+传输数据的时间
eg:m*n+s+1/2*r+b/N*r
（1）FCFS：根据进程请求访问磁盘的先后顺序依次访问。公平、对于聚簇性的访问比较好。
（2）最短寻道时间优先SSTF：选择的磁道是距离当前访问磁道最近的。（但是会产生饥饿，这是最短调度算法的通病，只要持续的有更短的请求到来，就永远不会调度距离远的）
（3）Scan算法：又称为电梯调度算法。在当前磁头移动方向上去选择距离最近的请求去访问。再最短寻道时间优先的基础上+磁头移动方向的限制。
Scan算法偏向于处理那些接近最里或最外的磁道的访问请求
（4）循环Scan算法：再Scan的基础上规定磁头只能单向移动。增加了公平性。
同时复习自己的项目，没有大项目就做一个小的项目，回忆自己的课程设计，毕竟自己报的是软件学院。
大数定律是多次独立重复实验下，其频率近似于概率。
1. 切比雪夫大数定律（n个独立同分布随机变量之和的均值）
2. 伯努利大数定律（n次独立重复实验下事件A发生的概率）
3. 切比雪夫定理
指的是（在一定条件下，随机变量个数比较多时）相互独立的随机变量之和近似服从正态分布。
1. 所以n个独立同分布的随机变量之和服从正态分布。---->变形之后可以服从标准正态分布。
2. 列维中心极限定理：n个独立同分布随机变量之和。
3. 拉普拉斯中心极限定理：n次独立重复实验，事件A发生的次数。
下面的例子均以机器学习中样本x以及标签Ci为例。
1. 条件概率公式：原因发生--->结果（由原因推出结果），P（x|Ci）（先验概率公式：根据经验，或者叫做根据已知的数据推出来”）
2. 全概率公式：我们很好由已知的数据求得P(Ci)，但是很难求得P(x)，故可以转化为：P(x)=（i从1-->n求和）(P(xCi))；
3. 贝叶斯公式（后验概率公式）：已知结果，反推原因出现的可能性。比如已知某个类具有某种属性，那么它属于哪个类别（具有标签），这种就是后验概率。
P(Ci|x)=（P(Ci)*P(x|Ci)）/(P(x))，其中P(x)用全概率公式展开即可。
4. 贝叶斯公式用于机器学习中的贝叶斯分类模型，主要是用训练数据去学习一个模型(模型计算出所有的P(Ci)、P(ai|Ci)、P(ai)，ai表示的是具体的属性)，然后每个待分类的测试样本用贝叶斯进行分类，根据其拥有的属性去计算P(Ci|x)中值最大的那个Ci即可。
1. 每次试验仅有两个对立的结果A、A~（比如射击，中还是不中），独立重复试验成为伯努利试验。
2. 其中n次独立重复试验中时间A出现的次数的概率计算满足B(n,p),为二项分布。
1. 无相关不一定独立，独立一定不相关。
2. 相关性系数：pXY=cov(X,Y)/(根号下（D(X)）*根号下（D(Y)）)
3. 两个正态分布的随机变量之和不一定是正态分布的，如果他们两个独立的话，是正态分布的。
向量范数，矩阵范数
3. 行空间，列空间，它们关系？
4. 线性方程组有解/无解/唯一解的条件？
5. 标准正交基，施密特变换
6. Pseudo Inverse伪逆矩阵
1. 矩阵秩：A中k行k列共同具有的k^2个数，是A的一个k阶行列式为A的一个子式，A的一切非0子式的最高阶数为A的秩r，即A不不存在r+1阶非0子式，但至少有一个r阶非0子式。
2. 计算矩阵的秩可以一般利用矩阵的性质（矩阵经过简单初等变换后不会改变它的秩，去将该矩阵变换成标准形式Er即可求出，emm，只经过行变换也可以看出来）
3. 矩阵的秩就是矩阵中的极大线性无关组中向量的个数。
是指矩阵A对向量X的变换相当于一个伸缩变换，没有旋转变换，即相当于一个缩放因子*向量X。那么这个缩放因子是矩阵A的本质，即AX=tX,t即为A的特征值。
（1）线性相关、线性无关：一组向量A={a1,a2,a3...，am}，该组向量构成的矩阵的秩<m,表示存在非0解，线性相关。若构成的秩=m那么线性无关。
由上面可知，(tE-A)X=0向量，X为非零向量。
故|tE-A|=0,其为特征多项式有解，未知量为t。
求出的t0，t1，t2...为特征值，代回原方程组得到一个齐次线性方程组，求解出来的X为对应t值的特征向量，该特征向量的集合称之为矩阵A属于特征值t0的特征子空间。
该矩阵A对应的所有特征值求出的特征向量为
A-*A=E,A为非奇异矩阵（矩阵满秩），存在A的逆。
（1）可以通过求伴随矩阵A*，A-=A*/|A|; 前提是|A|不为0。
（2）还可以通过进过一系列初等行变换/一系列初等列变换:
(A,E)--->(E,A-);
A--->E;
E--->A-;
（1）迹：矩阵对角线之和。
（2）正定矩阵：
1. 专业课：（会了不加分，不会扣分） 计网的三次握手，四次握手。流量控制，拥塞控制，各
层及各层的协议 计组的衡量计算机的性能指标 软件工程，几个软件开发模型 数据结构的链
表，kmp算法，最短路径，prim和kusral，排序算法及时间复杂度 高数的求导，求偏导，求极
限 概率论的条件概率，全概率，贝叶斯公式 操作系统的调度算法，进程和线程，多线程多进
程。
2. 英文面试：自我介绍介绍一下家乡介绍一下项目介绍一下英国的经历研究生计划也会挖一些坑，英文问你你的导师是xx吗？no还有让看小论文的一段话，边看边翻译等。
3. 科研论文（有了加分） 思路哪来的？如何实现的，数学框架，仿真实验如何做的，说一下你在里边的工作，多少行代码？
（1）可导一定连续，连续不一定可导。
（2）什么是可导：左极限=有极限，光滑--->可导。
（3）例子：y=|x|，在x=0处不可导。
（4）可微与可导等价。
（5）可积的概念：假设f(x)在[a,b]上可积分，则f(x)在[a,b]上连续或者f(x)在区间[a,b]上有上界，且只有有限个间断点，那么也是可微的。则推导出：连续----->可积，但是可积推导不出连续，存在上界的情况下可以由有限个间断点。
数理逻辑，二元关系，群与环，数论什么的，是一门比较抽象的学科，主要作用是建立相关的数学
模型，把实际问题抽象成为计算机能够理解的逻辑结构，并且用计算机的思维去解决实际问题，往
往实际用的不多，主要是训练思维。
（1）欧拉回路：经过图G中每条边一次且仅一次的回路，称为欧拉回路。
（2）欧拉路径：经过图G中每条边一次且仅一次的路径，称为欧拉路径。
（3）存在欧拉回路的图称为欧拉图。
无向图 G 有欧拉回路，当且仅当 G 是连通图且无奇度顶点；
无向图 G 有欧拉路径，当且仅当 G 是连通图且恰好有两个奇度顶点。这两个奇度顶点是欧拉路径的端点。
（4）哈密顿图：经过图中每个顶点一次且仅一次的回路称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。同理也有哈密尔顿路径。
在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图
在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图
（1）图G中的边与边之间只在顶点处交叉。
（2）判断一个平面图是否连通可以用欧拉公式：n-m+k=2;
代数系统封闭性 结合律 他就是 半群 含有单位元 就是含幺半群 有逆元就是 群
等价关系
设 R RR 为非空集合 A AA 上的关系，如果 R RR 是自反的、对称的、传递的、称 R RR 为 A AA 上的等价关系
偏序关系
设 R RR 为非空集合 A AA 上的关系，如果 R RR 是自反的、反对称的、传递的、称 R RR 为 A AA 上的等价关系
电话面试，第一个老师
简述一下科研项目的过程
项目中的难点
联系了其他导师吗
通过研究生提高自己哪方面能力
将来希望从事什么工作
写过论文没有
觉得自己有什么缺点
对我的研究方向感兴趣吗
电话面试，第二个老师
欧氏距离的缺点，为什么在xxx中不能用。在欧式空间、高斯分布下使用
欧氏距离：只能在欧几里得空间进行使用。比如从中国飞到美国，只能计算地表的距离，不能直接从地心穿过去
分类问题，都用 onehot + cross entropy
training 过程中，分类问题用 cross entropy，回归问题用 mean squared error。
training 之后，validation / testing 时，使用 classification error，更直观，而且是我们最关注的指标。
CycleGAN 的原理，如果成对的输入不知道标签怎么办
李宏毅
GAN中的G网络和D网络怎么使用的，MSE 损失
什么是度量学习
实现过LSTM的应用吗
1. 最大似然估计是什么
2. 什么是半正定矩阵，举一个例子
3. 程序的编译执行过程
4. 举一个大学中最熟悉的知识点，它的具体作用是什么
5. 计算矩阵的特征值和特征向量
6. 选择排序的过程
1. 英文介绍你的学校、自我介绍
2. 矩阵的秩的概念
3. 最大似然估计是什么
4. O ( n ) O ( l o g n ) O ( n 2 ) O(n)O(logn)O(n^2)O(n)O(logn)O(n
2 复杂度分别对应什么算法
5. 简单描述你参与度最高的项目
6. xxx中常用的指标是什么
7. 政治问题、怎么看待疫情
1. 动态规划的理解
动态规划算法与 分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从 这些子问题的解得到原问题的解。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
2. 指针和引用的区别
3. 深度学习的理解
4. 代码量
5. 贝叶斯公式
6. 先验概率和后验概率分别是什么
P ( A ∣ B ) = P ( A ) P ( B ∣ A ) P ( B ) P ( A ) 是 先 验 概 率 P ( A ∣ B ) 是 后 验 概 率 P(A|B) = P(A)\frac{P(B|A)}{P(B)} P(A)是先验概率 P(A|B)是后验概率P(A∣B)=P(A)
P(B)
P(B∣A)
P(A)是先验概率P(A∣B)是后验概率
1.数据库，有什么类型的数据库
2.关系型数据库的特点
3.关系型数据库有什么操作、操作有什么特点
5.图的遍历方式，DFS
6.冯诺依曼机的体系结构
1. 协议和服务之间的联系和区别？
答：
（1）首先，协议是对等层实体之间通信的规则集，对等层实体之间的通信使得为上层提供服务。本层只能看见本层的服务，看不见下层的协议，即下层的协议对上层服务的实体而言是透明的。
（2）更清楚的说就是，协议是“水平的”，它是对等层实体之间通信的规则集合。而服务是"垂直的"，它是同一个系统相邻层之间下层通过服务访问点向上层提供服务。
2. 计算机网络有哪些层？
答：
（1）OSI/RM：七层，包括应用层、表示层、会话层、 传输层 、网络层、 数据链路层 、物理层。
（2）TCP/IP：四层，包括应用层、传输层、网际层、网络接口层
（3）五层协议：包括应用层、传输层 、网络层、 数据链路层 、物理层。
3. 面向连接的服务以及无连接的服务？
答：
（1）面向连接的服务：是指自通信前需要建立连接，通信结束后需要进行连接释放。整个过程包括，连接建立、数据传送、连接释放。是按序传送、可靠传送的。
（2）无连接的服务：传送数据之前不许要建立连接，随时传就行，速度快，简单，但是无法无法避免数据的丢失、重复等只能“尽最大努力地交付”，是不可靠地传输。
4. 什么事“Everything over IP”? 什么是“IP over Everything”?
(1)“Everything over IP”?
答：
是指在TCP/IP网络体系结构下，各种网络应用都是建立在IP之上进行。
(2)什么是“IP over Everything”?
答：
是指在TCP/IP网络体系结构下，IP可以通过网络接口层运行在不同的物理网络之上。
1. 作用：主要是规定了通信结点和通信链路之间的连接的接口的一些特性。包括机械特性、电气特性、功能特性和过程特性。规定了通信链路上传输的信号的意义以及电气特性。功能是在物理媒体上为数据端的设备透明的传输原始的比特流。
2. 主要的设备有：
（1）中继器：起到的是信号再生的作用（数字信号），与放大器不同（模拟信号）。
（2）集线器：多端口的中继器。
（3）注意：物理层的设备均不支持存储转发功能，所以连接的两端必须使用同一个协议，切连接的两端是同一个局域网的不同的网段。
另外，物理层的设备不阻隔冲突域，也不阻隔广播域，它就是个最便宜的设备。
3. 数据交换的方式：
（1）电路交换：建立连接（独占），数据传输，连接释放。
（2）报文交换：结点具有存储转发功能，但是转发延迟的问题太大以及结点不好管理存储空间。
（3）分组交换：分组交换又分为：数据报交换与虚电路交换（虚电路为什么是虚的，因为其不是专用的。每个结点到其他结点的虚电路可能同时有若干虚电路经过。因为传输的两端可以有多条路，但是每条虚电路只支持两个特定的端系统之间的通信，两个端系统之间可以有多条虚电路为其不同的进程服务。）
1. 数据链路层的功能：在物理层提供服务的基础上为网络层提供服务。主要是加强物理层传输原始比特流的能力，将物理层提供的可能出错的物理连接改造为逻辑上无差错的数据链路。
2. 数据交换的三种方式的对比：
（1）电路交换：三步骤，建立连接-->传输数据-->连接释放。建立连接的时间比较长。且独占信道，适合传输数据量大的时候，信道利用率低且一旦出差错就会导致数据传输失败，无法控制。
（2）报文交换：不需要建立连接，随时发随时接收即可。结点具有存储转发的功能，每个结点接受整个报文之后进行检测，检测无误执行转发，故会存在延迟时间。缺点就是报文大小不确定，结点的存储管理不好控制，且延迟时间较长。
（3）分组交换：将报文划分为长度相同的分组，每个分组都有相应的原地址+目的地址+序号等信息，进行存储转发操作。好处是，分组可以可以并行进行转发，延迟时间缩短且因为分组大小固定所以易于存储的管理。缺点就是，因为每个分组都要加地址信息以及编号之类的，所以增加了传输的数据量。
3. 数据链路层主要完成的功能：
包括组帧、差错控制、流量控制、随机访问介质访问控制（协议）
4. 组帧：包括帧定界、帧同步、透明传输
数据链路层将从网络层获得的IP数据包封装成帧，然后进行传输，封装成帧的时候要添加帧首部和帧尾部，用于提取出数据部分。
组帧的方式有：
（1）字符计数法：在帧首部添加计数字段，记录该帧数据的长度。
（2）特殊字符的首位定界法：用特殊的字符去作为首位定界符。对于数据中可能出现的特殊字符，我们在其前面加上一个转义字符，接受的时候自动去掉即可。
（3）零比特填充的首位定界标志：01111110作为开始和结束的表示，为了方式数据中出现这样的串而出现提前终止的情况，我们对数据中连续的11111后面加一个0，接受的时候相反处理即可，硬件处理。
（4）违规编码法：适用于冗余编码的时候，比如我们的差分曼彻斯特编码（由高到低表示0，则由低到高表示1，高高和低低就是违规编码），我们用违规编码作为定界符即可，但是只适用于冗余编码。
5. 差错控制：检错编码（奇偶校验、CRC）和纠错编码（海明码）
6. 流量控制：就是限制发送方的发送速度，使得接收方可以正确的接收数据。
（1）停止等待协议
（2）后退N帧
（3）选择重发
（2）和（3）有一个共同点就是t+w<=2^n,n为编号的二进制数，否则容易产生若确认帧丢失接收方无法分清新帧旧帧的情况。
（4）这些包括了自动重传机制，即确认，超时重传机制可以确保可靠传输。
7. 随机访问介质控制机制：
在局域网中是总线型的，广播式的发送，所以必须为了防止冲突采取一些措施。
（1）随机接入系统ALOHA：纯ALOHA、时域ALOHA协议
（2）CSMA（载波监听多路访问）：1坚持、非坚持、P坚持。
（3）CSMA/CD(碰撞检测)：先听后发、边听边发、冲突停发、随机重发。适合有线网（局域网）。
1）存在争用期，因为必须保证检测到冲突的时候数据还没发完，所以2*端到端的传播时间必须小于数据的发送延时。即可以确定最小帧长（以太网的最小帧长是64B）
2）随机重发的策略是二进制指数退避算法来防止再次冲突。
（4）CSMA/CA（碰撞避免）：包括预约信道、ACK、RTS、CTS，适用于无线网。并不能完全避免，只能尽量的避免，在发送的过程中不检测冲突。
1）数据发送前先预约信道，告诉其他设备我要发对就的数据，在此期间你们别发。
2）随机重发的策略是二进制指数退避算法来防止再次冲突。
8. 局域网：
9. 数据链路层在广域网中的协议：
（1）PPP协议：按字节传输的，点到点的协议，不可靠，只检错丢弃，不纠错，不适用序号和确认机制。支持全双工。
（2）HDLC（高级数据链路控制协议）：面向比特，提供可靠传输（使用了编号和确认机制），用的是0比特插入法实现透明传输。
10. 链路层设备（局域网中）：隔离冲突域，不隔离广播域
（1）网桥：一次只能转发一个帧。
（2）交换机：多端口的网桥，解决网桥一次只能转发一帧的不足。有直通式、存储转发式。
1. IP地址与MAC地址的区别：
答：
（1）举个栗子，就像是你接收快递时所填的家庭地址和你的个人信息一样。IP地址就是你的住址，这个是可以变的，但是你的个人信息，也就是你的身份证号码是不会变的。
（2）链路层传输需要的是物理地址MAC，网络之间通过路由器转发分组需要的地址是IP地址。
（3）IP地址是逻辑的，MAC地址基于物理设备。
2. IPV4和IPV6的区别：
答：
（1）IPV4地址32位，IPV6地址128位。IPV6的出现是为了解决IPV4地址不够用等问题。
（2）IPV6提高安全性。身份认证和隐私权是IPV6的关键特性。
3. 如何实现ipv4和ipv6的互联：
答：
（1）双栈技术（IPV4协议栈和IPV6协议栈）：数据链路层根据收到的IP数据报进行解析其头部第一个字段，即版本，版本位4就用IPV4协议栈去处理，版本位6就用IPV6协议栈去处理。
（2）隧道技术：实现IPv6的较完整运行。隧道技术是在IPv6网络与IPv4网络间的隧道入口处，由路由器将IPv6的数据分组封装到IPv4分组中。IPv4分组的源地址和目的地址分别是隧道入口和出口的IPv4地址。在隧道的出口处拆封IPv4分组并剥离出IPv6数据包。
4. 虚电路与数据报比较：
答：
（1）虚电路需要建立连接，是有序的，能够保证数据传输的质量，但是灵活性不够强，结点出现问题所有经过此节点的虚电路都不能用了。
（2）数据报交换：无连接不可靠，但是灵活。
5. 子网的划分和掩码：
答：
（1）主要是为了提高IP利用率，就是公有IP的利用率。
（2）还可以减小广播域（注意不是减少，是减小！！！）
（3）便于IP的管理。
6. 因特网中的两大类路由选择协议：
答：
（1）域内路由选择协议IGP：RIP（UDP，用的路由选择算法是距离向量，最多15跳）、OSPF（IP，用的路由选择算法是链路状态，其中用到了迪杰斯特拉最短路径求解算法。
（2）域间路由选择协议EGP：BGP（TCP）
7. 有人认为：“ARP协议向网络层提供转换地址的服务，因此ARP应当属于数据链路层。”正确么？
答：不正确。
因为ARP本身是网络层的一部分，ARP协议为IP协议提供了转换地址的服务；数据链路层使用硬件地址而不使用IP地址，无需ARP协议数据链路层本身即可正常运行。因此ARP不再数据链路层。
8. ARP协议：
ARP 是解决同一个局域网上的主机或路由器的 IP 地址和硬件地址的映射问题。
9. 在经过路由器转发的过程中IP数据报中的IP源地址、目的地址以及MAC源地址和目的地址会发生变化吗？
答：如果路由器不提供NAT，则IP地址是不会变化的。但是如果提供NAT的话，是会改变的。但是MAC源、目的地址是会变化的。
（1）如果源IP地址是私有IP地址，需要经过路由器的NAT的转换，源地址转换成公有的IP地址，但是目的地址是不变的。
（2）MAC源、目的地址会一直变化，根据所处的位置以及下一条进行变化。
提供端到端的服务
1. 传输层的两个协议：无连接不可靠但是很快速的UDP（面向报文）、有连接可靠但是管理麻烦的TCP（面向字节流）。
2. UDP：首部只有8B，4个字段（每个占2B），分别为源端口号、目的端口号、长度（是UDP整个的长度）、校验位（校验UDP中的首部+数据）
3. 如果IP可以可靠传输是不是就不需要UDP了，直接跟应用层联系？
答：不可以。IP只能确定主机，但是真正通信的是两台主机中的进程，所以我们需要确定具体的进程也就是需要源端口号和目的端口号，这需要UDP提供。
4. TCP：20B的首部，包含很多东西。
（1）TCP三次握手建立连接，两次不行吗？
答：不可以。
如果存在已认为丢失的请求连接报文重新传到了服务器端，则服务器会响应然后向客户端发送ACK，此时认为已经建立连接，之后服务器便开始等待客户机传送数据。但是客户机并未响应这个ACK，所以服务器会一直等待下去，造成资源的浪费。
（2）四次呢？
答：四次太多了，三次就可以双方都确认对方已经做好了接收数据以及发送数据的准备。
（3）TCP四次挥手（握手）释放连接，为啥需要四次而不是三次？
答：1）是因为可能有部分数据需要处理。TCP建立连接的时候第二次握手发送的是SYN=1以及ACK=1，故三从握手双方通信达成一致。
2）建立连接时，被动方服务器端结束CLOSED阶段进入“握手”阶段并不需要任何准备，可以直接返回SYN和ACK报文，开始建立连接。
3）释放连接时，被动方服务器，突然收到主动方客户端释放连接的请求时并不能立即释放连接，因为还有必要的数据需要处理，所以服务器先返回ACK确认收到报文，经过CLOSE-WAIT阶段准备好释放连接之后，才能返回FIN释放连接报文。但是连接释放请求的时候，第二次发送的只是ACK，并没有FIN，是因为服务器可能还需要传送一些数据，所以要等待传送完毕之后才能再次给客户端发送FIN=1的连接释放报文。
（4）TCP四次挥手为啥第四次客户机发送ACK之后要等待2MSL之后才能真的关闭？
答：
1）MSL是最大报文段生存周期。客户机发送ACK后如果MSL后服务器端没有接受到，就会再次发送一个请求释放报文，这一过程总的到达客户端的时间最多就是2MSL，所以一旦ACK出现丢失，那么2MSL内客户机一定可以得到消息，然后重新发送ACK，再次重新计时。
2）如果客户机发送ACK之后就关闭了，那么如果出现ACK丢失的现象，即使服务器端再次重新发送请求释放报文，它也不会理会，就会导致服务器端无法结束。
3）还可以防止已失效的连接请求报文。
（5）重传的两种方法：
1）超时重传：根据RTT均值设置一个超时重传的时间。但是这种方法不好的点在于慢。但是这种情况预示着此时拥塞很严重了。
2）冗余ACK：利用TCP接受数据的特点，当前未接受的数据k而言，如果k后的数据到达，每次都会产生一个ACK的确认序号为k，3个这样的就表示需要为k的报文段丢失需要重发。这样的好处是快，而且此时没有那么的拥塞。
1. 应用层传输的方式：
答：C/S方式、P2P点对点方式（平等的，每个主机既可以作为Client也可以作为Service）。
2. 域名解析协议（DNS）：由域名--->IP地址，基于UDP。
3. FTP（文件传输协议）：控制连接（端口号21），数据连接（一般是端口号20），是两个并行的TCP连接，数据传输结束立即断开数据连接。
4. SMTP以及POP3：（基于TCP）
（1）SMTP：简单邮件传输协议，只传输二进制信息，在用户代理--->邮件服务器，以及邮件服务器-->邮件服务器之间的邮件的传输。（Push的方式）
（2）POP3：邮局协议，是传输从邮件服务器到用户代理。（Pull的方式）
5. 还有HTTP也是基于TCP有连接的。
1. 说下浏览器请求一个网址的过程？
答：
（1）首先是解析域名，DNS进行，获得IP地址。然后端口号发送端随机分配，服务器是固定的80端口。
（2）知道IP和端口号之后就可以建立3次握手建立TCP连接。
（3）发送HTTP请求报文。
（4）服务器处理浏览器发来的请求，返回要显示的页面html信息。
（5）传输结束，4次握手释放连接。
（6）显示页面。
1. 关系型数据库。
2. 网状型数据库。
3. 层次模型数据库。
1. 结构化的。
1. 数据的查询、删除、插入、修改基本操作。
2. 安全性检测，并发控制。
1. 关系数据库用二维表（表）来实现数据之间的联系。
2. 嵌入式SQL语言是指直接在编程语言中写SQL，就像是python和java中写一样，他的作用是可以去处理多行数据。
3. 在数据库设计过程中，需求分析和概念设计可以独立于任何数据库管理系统进行，逻辑设计和物理设计与选用的DAMS密切相关。（DBMS包括数据的定义（约束）、数据的操纵）、数据库的运行、组织、存储等管理。
4. 触发器：主要是一种约束
eg: CREATE TRIGGER 触发器名
BEFORE/AFTER/INSTEAD
UPDATE/INSERT/DELETE [of 属性名] ON 表名
REFERENCING
...
FOR EACH ROW/SEGMENT
条件（可选）
操作;
5. 并发控制：
（1）正确性准则：可串行化调度，是指并发事务实行的结果与某一次序串行执行这些事务的结果相同。
（2）并发控制如何保证数据的一致性：封锁机制，以及封锁协议（一级、二级、三级）。以及通过保证原子性、隔离性、持久性来保证一致性（ACI-->D）。
（3）并发操作可能带来的数据不一致性包括：丢失修改、读脏数据、不可重复读。（主要是因为破坏了事务的隔离性）
（4）意向锁：
1）意向锁的作用：对关系加显示锁就相当于对该关系的所有元组都加了相同的锁（多粒度封锁，分成树，每个结点被加锁相当于其后裔结点也被加了锁）。但是这意味着每次我想要对某个结点加锁时，都不仅需要检查该结点上被加的锁，还需要检查他的所有前结点以及后裔结点上被加的锁，这太麻烦了。
2） 引出意向锁的目的：意向锁是指，当你对某个结点加显示锁（X/S）时，就意味这你对该结点所有的上层结点都加了意向锁（IX/IS）。所以某个结点上有意向锁就意味着，该节点存在后继结点上加了X/S锁。
3）好处在哪？假如你想对某个结点加显示锁，那么你除了查看该结点上加的显示锁之外，只需要看该结点加的意向锁即可，比如你想给该结点加X锁，但是该结点已经有了一个意向锁IX，说明他的子结点存在加X锁的，那你就不能给结点加X，会冲突。
4）申请锁自上往下进行，释放锁自下往上进行。
6. 关系规范化：
（1）定义：是指用形式更加清晰、结构更加规范的关系模式取代原有关系的过程。
（2）目的：是为了消除存储的异常，减少数据的冗余，保证数据的完整性（正确性和一致性）和存储效率。避免出现删除异常、插入异常、更新异常的行为。
7. 数据库的完整性和安全性：
（1）数据库的安全性：指的是保护数据库以免其受到恶意的破坏和非法存取。
1）针对的对象是：未授权的用户和非法的操作。
2）保护数据库安全性的办法有：存取的控制（设置权限，数据和用户均设置）、用户身份的鉴别、视图机制、数据加密。
（2）数据库的完整性：数据的正确性+相容性。指的是要防止数据库中存在数据的语义不正确的数据，即确保数据的正确性。
1）数据的正确性：符合现实世界语义、满足实际需求的数据。
2）数据的相容性：指的是同一个对象在不同表中的含义是符合逻辑的。（参照完整性）
3）数据库中三类数据完整性约束：包括实体完整性+参照完整性+用户定义的完整性。
8. 数据查询：
（1）数据查询的流程：
1）连接器：连接数据库。连接器负责跟客户端建立连接、获取权限、维持和管理连接。
2）查询缓存：MySQL 拿到一个查询请求后，会先到查询缓存看看，之前是不是执行过这条语句。之前执行过的语句及其结果可能会以 key-value 对的形式，被直接缓存在内存中。key 是查询的语句，value 是查询的结果。如果你的查询能够直接在这个缓存中找到 key，那么这个 value 就会被直接返回给客户端。
3）分析器：分析器先会做“词法分析”。你输入的是由多个字符串和空格组成的一条 SQL 语句，MySQL 需要识别出里面的字符串分别是什么，代表什么。做完了这些识别以后，就要做“语法分析”。根据词法分析的结果，语法分析器会根据语法规则，判断你输入的这个 SQL 语句是否满足 MySQL 语法。还有语义分析。
4）优化器：优化器是在表里面有多个索引的时候，决定使用哪个索引；或者在一个语句有多表关联（join）的时候，决定各个表的连接顺序。对关系代数进行优化。
5）执行器：开始执行的时候，要先判断一下你对这个表 T 有没有执行查询的权限，如果没有，就会返回没有权限的错误。
（2）查询的优化方法：
1）数据获取方式的优化:
a. 一次获取的数据尽量少：查询获取数据 , 尽量带 WHERE 条件精确指定获取范
围 , 且一次获取的数据量要少（应用层开发阶段必须注意）
数据获取，遵循的基本原则：
--- 少：不要全表扫描。要用什么取什么
--- 准：带 where 条件获取，用谁取谁
--- 快：加索引到 where 条件涉及的列上，用谁则快速取到谁
--- 减少关联：没有直接联系，不要硬拉郎配。减少耦合，减少关联。
b. 不用 select * ： 臭名昭著，远远避之。
获取什么列就明确指定列名。
查询语句中出现的列名，最好是索引的一部分。
c. LIMIT x ：在满足应用需求的情况下可限制元组个数
9. 触发器：保证参照完整性的。
delimiter//
CREATE TRIGGER t_afterInsert_study
AFTER INSERT ON study
FOR EACH ROW
#select COUNT(*) FROM sstudent where StudID=new.StudID GROUP BY StudID)=0
#(select COUNT(*) FROM course where CourseID=new.CourseID GROUP BY CourseID)=0
BEGIN
IF((select COUNT(*) FROM sstudent where StudID=new.StudID GROUP BY StudID)=0 OR
(select COUNT(*) FROM course where CourseID=new.CourseID GROUP BY CourseID)=0)
THEN
DELETE FROM study
WHERE StudID=new.StudID AND CourseID=new.CourseID;
END IF;
END
//
1.什么是软件危机？具体表现有哪些？
答：
（1）软件危机是指在软件开发、运行和维护的阶段中所遇到的一系列严重的问题。
（2）主要包括两方面的问题：
1）如何开发软件以满足人们日益增长的需求。（提高软件生产率）
2）如维护数量不断膨胀的已有软件。（软件的质量维护的方面）
（3）具体表现：
1）对软件开发估计对的成本和进度不准确。
2）人们对已完成的软件不满意的现象时常发生（需求分析做的不到位）。
3）软件的质量不可靠（没有严格使用质量保证技术）。
4）缺乏文档等信息资料使得软件可维护性差。
5）软件的生产速率的提高远远跟不上计算机应用程序迅速普及深入的趋势。
2. 你认为一个软件工程师应具备什么素质？
（1）求知欲和进取心。软件行业的技术是不断发展的，新技术、新思想代替旧技术、旧思想，所以软件工程师也应该不断地学习新技术。
（2）具备良好的沟通能力。与客户深入的沟通才能准确且全面的了解用户的需求。在开发软件的过程中与团队成员不断地沟通使得开发的的过程更加的顺利。
（3）自觉的规范意识和团队精神。开发大型的软件是一个团队一起完成的，并非一个人单独开发一个软件，在这个过程中需要团队成员之间的良好的合作。
（4）良好的编码能力。软件人员的一个重要职责是把用户的需求功能用某种计算机语言予以实现。
（5）认识和运用数据库的能力。信息是以数据为中心的，与数据库的交互在所有的软件开发中都是必不可少的，所以要求我们的软件工程师必须具备这样的能力。
（6）具有软件工程的概念。
3. 由软件的特点，谈谈你对软件工程的理解？
（1）首先是软件的特点：
1）软件是复杂的，软件是人类思维和智能的一种延伸和在异体上的再现，远比任何以往人类的创造物都要复杂的多，软件的复杂性是软件的固有属性、本质特性。
2）软件是不可见的，软件是客观世界空间和计算机空间之间的一种逻辑实体，不具有物理的形体特征。
3）软件是不断变化的，它需要随着应用、硬件、用户和社会等各种因素的变化而不断的被修改和扩展。
4）软件必须遵从人为的惯例并适应已有的技术和系统，软件需要随接口的不同而改变，随时间的推移而变化，而这些变化是不同的人设计的结果，许多复杂性来自保持与其他接口的一致，对软件的任何再设计，都无法简化这些复杂特性。
（2）对软件工程的理解：
1）IEEE给软件工程下的定义是：把系统的、规范的、可度量的途径应用到软件开发、运行和维护的各个阶段，就是将工程应用于软件。以及研究所提到的这些途径。
2）软件工程的三要素是：过程+方法+工具。
3）软件危机是包括：软件质量低劣、成本高、进度不可控、软件维护费用高、开发效率慢等。为了应对软件危机，软件工程应运而生。所以软件工程是为了解决这些问题的，是采用规范化的工程化方法去进行软件的开发、运行和维护。就是要用工程化方法去规范软件开发，让项目可以按时完成、成本可控、质量有保证。
4. 结构化软件开发与面向对象软件开发各有什么特点？
（1）结构化开发：
1）具有顺序性和阶段性。将软件开发的过程划分为若干相对独立的阶段。每个阶段按顺序的进行开发，并且每个阶段结束需要进行阶段性评审，对产品和文档进行严格的评审。前一个阶段的成功结束，才能够开始下一个阶段的开发。
2）严格的阶段评审使得可以较早 的发现问题，提高软件的质量以及开发的成功率，使得开发工作可以有条不紊的向前推进。
3）该方法有利于提高软件的正确性、可靠性、可维护性，具有完整的开发质量保证措施。
4）缺点是，开发周期长，对于个性化的开发阶段文档的编写较为复杂以及繁琐，无法发挥开发人员个性化开发的能力。
（2）面向对象软件开发：
1）强调从现实世界中客观存在的事物出发去理解问题以及要构造的系统。运用人类日常生活的思维方式和原则进行开发。
2）对象的概念贯穿了整个软件开发的过程，使得系统开发各阶段的系统成分具有良好的对应关系，提高了系统开发的效率和软件的质量，提高了系统的可维护性。
3）对象概念的一致性，使得系统开发的各类人员在软件开发的各个阶段具有共通的语言，改善了系统开发过程中人员交流和协作。
4）对象的继承、多态性，以及对象的相对独立性对软件的可重用性提供了强有力的支撑。
5）对象的相对稳定性以及对易变性的隔离增强了系统的应变能力。
5. 结构化软件设计和面向对象软件设计的区别？
（1）处理问题的出发点不同。
1）结构化设计强调过程抽象化和模块化。以过程为中心去构造、处理客观世界问题的。是一种面向过程开发方法，适合初学者。
2）面向对象软件设计强调的是从客观世界中的实体以及实体之间的关系出发去理解问题域，将问题域中的要领直接映射到对象以及对象的接口之上。是用人们日常习惯的思维方式去处理问题。
（2）处理问题的基本单位以及逻辑层次关系不同。
1）结构化设计处理问题的基本单位是模块，将系统按照功能以及高内聚低耦合的原则将其分解成一个一个小模块，构造模块间的关系。用模块之间的层次关系去表示模块之间的联系。
2）面向对象设计是以对象的角度思考问题，将复杂的系统看做是一个复杂的对象，由简单的对象组成，从用生活中的事物以及事物之间的关系出发去进行分解。用对象的集合类作为处理问题的基本单位。使得计算机世界尽量的像客观世界靠拢。
（3）数据处理的方式不同：
1）结构化设计是面向过程的，将系统开发抽象分解成若干模块，数据跟方法是分离的，用户使用方法去处理数据。
2）面向对象的设计将数据和操作封装成一个整体，用户不能直接对数据进行操作，对数据的操作必须通过给对象内的方法发消息，然后该方法去处理数据来完成。
6. 什么是软件管理？软件开发和软件管理有何关系？
（1）软件管理：管理是指按照计划、组织和控制等一系列活动，合理的配置和使用各种资源，已达到既定目标的过程。软件项目管理是软件工程的普适性的活动，软件的管理先于任何技术活动之前，并且贯穿于整个项目开发过程。
（2）软件开发和软件管理的关系：软件项目的管理是一项普适性的活动，它先于任何技术性的活动之前就开始了，并且贯穿于整个项目开发过程的各个阶段中（软件的建模、构造、部署）。只有在科学且严格的软件管理之下，先进的技术方法和优秀的软件工具才能够充分的发挥作用。因此，有效的软件管理是大型软件开发项目成功的关键，也是软件开发过程中必不可少的组成部分。
7. 软件项目管理的特点和意义。
（1）特点：
1）不确定性。软件项目是抽象的，是逻辑实体而非物理实体，所以项目的管理具有不确定性。
2）阶段性。项目的阶段性决定了项目的历时有限，有着明确的起点和终点。
3）独特性。没有完全一样的项目。
（2）意义：构造软件产品是一项复杂的任务，尤其是当需要多个工作人员长期共同工作的时候，软件的项目管理是一项普适性的活动，它先于任何技术性的活动开始之前进行，贯穿于整个软件开发的各个阶段。
8. 谈一谈你对软件工程这门学科的理解。
答：软件工程=管理+技术。
正如IEEE给他下的定义一般：软件工程是指将系统的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程应用于软件。并且研究上面锁提到的方法。
由于软件规模不断增大-->软件危机的产生。
为了应对软件危机-->软件工程应运而生。
其目的旨在管理+技术的方式去开发软件，制定计划，合理利用有限的资源（人力、物力）去高效率的开发一个质量高、可维护性好、用户满意度高等的软件。其中涉及很多知识，包括程序设计、软件架构、软件体系结构、数据结构、数据库、编译原理、设计模式等等知识。
比起以前单独开发，这里更加强调的是规范化、合理化、高效化的开发方法。
9. 什么是软件架构？谈一谈软件架构设计的历史、发展、作用。
10. 你对框架是怎么理解的？耦合会导致什么问题？怎么解耦合？（真题）
11. 软件架构在软件开发中的重要性。
12. 谈一谈你对需求工程的理解。
（1）需求工程产生的原因：是因为软件设计人员对用户需求不明确就开始着手设计，导致最终用户对已完成的软件不满意的现象时常发生。
（2）基于此，我们提出了需求工程：是理解用户需求的技术以及任务。
（3）需求工程是在沟通和建模之前进行的，是理解用户需求、评估要求、分析可行性的一个基础，一定程度上保证了软件的质量。
（4）需求工程是成功制作软件的一个重要的环节。如果没有需求工程，那么最终生产的软件很可能无法满足用户的需求。
13. 软件测试的概念、目标、原则。
（1）软件测试是指：在一定的条件下对程序进行操作，以发现程序中的错误，对软件的质量进行评价的一个过程。也是对软件是否满足预期设计要求进行评估的一个过程。
（2）测试目标：是想要发现通过测试可以避免的一些开发风险，实施测试去尽量的降低开发过程中的风险。确定测试何时结束，再开发的过程中可以将测试看做是一个标准的项目。
（3）原则：
1）所以的测试都应该能够追溯到用户的需求上去。
2）应该远在测试开始之前就制定测试计划，在测试的过程中，要记录测试的各种数据，以便后期的维护工作。
3）为了达到最佳的测试效果，应该由第三方从事测试工作。
4）穷举测试是不可能的，所以应该尽可能在有限的资源的情况下设计尽可能覆盖程序所有逻辑的测试用例。
5）注意集群的现象，应用pareto原则到软件测试中。pareto原理说明，测试发现中的错误中的80%都是有软件中20%的模块所引起的。
6）要考虑各种极端以及边界的情况。
14. 对软件测试中的白盒测试与黑盒测试的理解。
（1）白盒测试是对软件的程序内部结构的测试，包括逻辑覆盖以及控制结构测试。
1）其中逻辑覆盖包括：语句覆盖、判定覆盖、条件覆盖、判定条件覆盖、条件组合覆盖、路径覆盖等。
2）控制结构测试：基本路径测试、循环测试、条件测试。
（2）黑盒测试：是功能测试，不考虑内部结构，根据输入、输出去测试软件的功能。包括：等价类划分、边界值分析、因果图法、决策表法、场景分析法。
15. 各个过程模型的特点以及之间的对比。
（1）瀑布模型
（2）快速原型模型
（3）增量模型
（4）螺旋模型
（5）RUP
（6）敏捷开发
（7）喷泉模型
16.拓然型知识：
（1） 谈一谈移动互联网平台的现状和发展方向。
（2）在alphago与李世石对弈的背景下，谈一谈人工智能发展的现状、以及未来。
（3）在大数据下，传统的关系型数据库遇到的困难和挑战。
（4）网络上信息的种类日益繁多，谈一谈未来的搜索引擎会面临那些挑战？
（5）物联网信息多样化，搜索引擎即将面临的挑战。
（6）谈谈你对VR的理解、有关应用，以及未来的发展前景。
（7）在目前这个移动互联网时代，谈谈你对大数据的认识、理解、应用。
（8）物联网的应用前景和技术特点？设计物联网时要注意的问题？
（9）搜索引擎和物联网！
首先图算法有：DFS、BFS、Prim、克鲁斯卡尔、迪杰斯特拉、弗洛伊德、拓扑排序、关键路径。
1）求图中任意两点之间的最短路径的floyd弗洛伊德算法（O（n^3））。
1）0型文法（短语文法）：α-->β，α由(VN|VT)组成，且必定含有一个非终结符。β=(VN|VT)*
2）1型文法（上下文相关文法）：在0型文法基础上增加，α-->β，|α|<=|β|;
3）2型文法（上下文无关文法）：在1型文法基础上增加，α-->β，其中，α是非终结符。
4）3型文法（正规文法）：分为左线性+右线性文法，
在2型文法基础之上为，A-->a|aB或者是A-->a|Ba这种形式。
关系是后面的在前面的基础之山增加了新的规则。
1）目的：优化后的代码运行快、存储空间需求小。这也正是我们优化代码的目的，从时空两个维度尽可能让代码效率高。在时间和空间两个维度优化代码，尽可能以较小的代价取得最优的优化结果。
2）技术：消除公共子表达式、复写传播、删除无用代码、代码外提(在循环中一直没有改变的值，我们把它提到循环外面去)、强度削弱（乘除变加减）、删除归纳变量。
1）信号量机制：主要是保护共享资源的。
2）管道pipe：一个写，一个读。
3）消息队列：消息队列是消息的链接表，存放在内核中并由消息队列标识符标识。 用户可以从消息队列中读取数据和添加消息，其中发送进程添加消息到队列的末尾，接收进程在队列的头部接收消息，消息一旦被接收，就会从队列中删除。
4）共享内存：共享内存就是允许两个或多个进程共享一定的存储区。共享内存没有任何的同步与互斥机制，所以要使用信号量来实现对共享内存的存取的同步。
1）都是运输层的协议。
2）TCP协议是有连接、可靠的传输，需要校验、序号、有确定和重传（超时、冗余ACK）机制、流量控制、拥塞控制（慢开始（阈值）、拥塞避免算法（拥塞窗口到达阈值之后）、快重传（利用冗余ACK）、快恢复（直接从阈值开始用拥塞避免算法））。很可靠，但是耗费资源、浪费时间，适合要求准确度很高的网页通信、邮件等，不适合实时通信等。
UDP是无连接、不可靠，但是很方便很快速，适合要求实时且容许些许错误的场合，比如语音通话等实时系统。
1）原码、反码和补码都是计算机表示数据的编码方式，在原先的值的基础上加上符号位，可以使得减法转换成加法。
2）原码=符号位（0|1）-真值的绝对值;
反码=正数=原码|负数=符号位不变-原码数值位取反;
补码=正数=原码|负数=反码+1;
将指令的执行分成五个阶段：分别是取指、译码、执行、访存、写回。
1）DFS是图的深度优先搜索算法。
用递归，注意不连通的情况。注意要加一个标记访问数组visited[]。
复杂度：邻接矩阵：O(n^2)因为搜索每个点的邻接点需要遍历一行，邻接表：O(n+e)，直接是链表连接的，所以就是有多少表就是多少。
2）BFS是图的广度优先搜索算法。
（1）完全二叉树：一个有n个结点、k层的二叉树，其1~n号结点与满二叉树中1~n号结点一一对应。
（2）用队列进行层次遍历。记录遍历的结点数目+每次pop()出一个结点之后都对其进行孩子的判断。
p=pop();
count++;
if(p->lchild!=null&&p->rchild!=null)---->then push(lchild)，push(rchild)
else if(p->lchild==null)--->then return false;
else if(p->rchild==null)---> then push(lchild); break;
else break;
while(!stack.empty()){
stack.pop();
count++;
}
if(count==n) return true;
return false;
1）可以给链表加一个头结点进行暴力破链表法。
2）也可以快慢指针法，这个不会破坏链表还可以接着查看环的入口，环的长度等信息。
1. prim算法：加点法。数据机构需要：D[i]表示该结点与已选择的结点之间的最小距离。每次选择最小但不为0（标识已选过的结点）的一个结点，更改其D值=0，更新D不为0的结点的D[]值。外循环n-1次即可。记录path[]，表示选取的结点相连的结点。
时间复杂度：O(n^2)
2. kruscal算法：加边法。需要加一个数据结构是closedge[i]记录该边的起点、终点、weight。防止产生环路，还需要记录连通分量，每一个结点都有。
1）先给边closedge[]排序。
2）for循环逐个选取最小的weight的边。判断front结点和back结点的连通分量是否相同，不相同就加入，并且改连通分量使其一致。如果相同则cotinue直接遍历下一条边。
3）这个循环结束的条件是加边数=n-1时停止。
4）时间复杂度：O(nlogn)。
1）求一个顶点到其他顶点的最短距离。需要数据结构记录距离D[]，但是切记，D[]得值会更新，但不会随着计算出来最短路径后被置为0，所以，还需要visited[]标记访问。需要path[]表示该结点的前驱结点。
2）初始化D[]和path[]，默认无穷大和-1。
3）选择未访问过的且距离v0最小的点，更新其他D[]的值，可以将vk作为v0-->vi的中间结点。
4）然后循环选取未访问过的距离最小的点即可。最外层for循环n-1次即可。
5）时间复杂度：O(n^2)
1）是先计算每个顶点的入度，计算过程中将入度为0的结点入栈。同是需要记录访问的结点数count。
2）while循环，栈不为空，循环
{
出栈，输出。count++;
循环，将该点指向的所有结点的入度-1,判断为0--->入栈;
}
如果count<n--->有环
否则--->无环
.
1）模式匹配：字符串的匹配算法。
2）主要思路：是充分利用子串的结构使得主串的指针不需要回溯！
3）加入子串中有：next[j]=k,那么表明：t[0]~t[k-1]=t[m-k+1]~t[m];
又因为主串和子串在i、j处匹配不上，所以表明s[i-j]~s[i-1]=t[0]~t[j-1]
-->s[i-k]~s[i-1]=t[0]~t[k-1]，所以i不动。
KMP代码:
i=0,j=0;
while(i<n&&j<m){
if(j==-1||s[i]==t[j]){
i++;
j++;
}
else{
j=next[j];
}
}
if(j==m){
return i-j;
}
else{
return -1;
}
4）next数组的求解：
与KMP算法过程一样，充分利用子串的自身前后缀的性质！！！
整体思路：字符从0开始存
next[0]=-1;
i=0,j=-1;
while(i<str.length()){
if(j==-1||str[i]==str[j]){
i++,j++;
next[i]=j;
}
else{
j=next[j];
}
}
1. 快排：不稳定。适合n大，且较为无序的时候，时间复杂度平均值-->O(nlog2n)，最坏可以达到O(n^2)。空间复杂度：O(logn)--->O(n)之间。
快排思想：在冒泡排序思想上的改进。冒泡排序是想要每次比较相邻两个结点，每次交换相邻两个结点只能消除一个逆序。快排的想法是每次交换不相邻的两个结点从而一次消除多个逆序。
2. 归并：稳定。分治法思想，用递归实现，时间复杂度-->O(nlog2n),但是空间复杂度-->O(n)。用于链式可以不加存储空间，但是递归依旧需要，大概O(logn)
1）工厂方法是创建型模式。用于自动产生产品，而不需要用户手动生产。由工厂返回产品。用户只需要通过工厂返回产品即可，不需要直接操作产品类的。
2）具体的由：抽象工厂父类、若干工厂子类、抽象产品父类、若干产品子类， 利用多态。具体工厂中的prodece方法返回对应的具体的产品。
可导、可微、连续、可积之间的关系（一元函数+二元函数）。
三个中值定理的区别、联系和物理意义（罗尔、拉格朗日、柯西）。
梯度、方向导数与梯度下降。
泰勒公式。
线性空间（向量空间）。
矩阵的秩。
特征值和特征向量。
相似矩阵。
正定矩阵。
线性相关、线性无关。
矩阵的正交。
大数定理。
中心极限定理。
全概率公式和贝叶斯公式。
正态分布（高斯分布）。
概率密度函数。
集合论。
平面图。