今天是CVTE的第一场笔试，做了CVTE2016年的笔试题，被虐成狗，写这篇文章记录一下，希望以后不要踩这些坑。也希望自己能够在下周六的笔试中顺利通过。
TCP协议
解析：考察的是计算机网络
- 断开的时候，客户端发起中断请求，就是Fin报文——（我没有数据发送给你了哦）
- 这个时候服务器端可能还没全部接受完数据，所以不能急着关闭socket，所以它会发送ACK告诉客户端——（你的请求我收到了，但是我还没准备好，请继续你等我的消息）
- 此时客户端进入FIN_WAIT状态，继续等服务器端的FIN报文
- 服务器端确认发送完成，则发送FIN报文给客户端——（告诉Client端，好了，我这边数据发完了，准备好关闭连接了）
- 客户端接受到FIN报文后，准备关闭连接，但是还是不信任服务器端，所以它决定再确定一下，发送ACK，然后进入TIME_WAIT状态
- 服务器端如果没有接受到ACK则决定重新 传，接受到了就知道要断开连接了
- 客户端等待了2MSL后依然没有得到消息则说明服务器端已经关闭啦——（好的，那我也关闭好了）
编译和体系结构
- 每条指令的功能
（1）读取某存储单元内容装入给定寄存器。
（2）把一个数据从某个寄存器存入给定的存储单元中。
（3）把一个数据从某个寄存器送到另一个寄存器或者ALU输入端。
（4）进行某种算术运算或逻辑运算，将结果送入某个寄存器。
B答案：CPU在执行程序的过程中，总是在执行完一条指令、取下条指令之前，去主动检测“中断请求信号”，若发现有中断请求，则执行一条“中断隐指令”，以响应中断请求。
CPU响应中断请求后，就会跳转到一个中断服务程序去执行，以进行中断处理。不同的中断类型具有不同的中断服务程序，进行不同的中断处理。有些中断处理非常简单，例如“打印机缺纸”，其中断服务程序只要在屏幕上显示一个消息即可；有些中断处理则比较复杂，例如，对于采用中断方式进行打印输出的情况，中断服务程序中需要启动外设进行I/O，通常在发出启动外设的命令后进行中断返回，以回到原先被中止的另一个进程代码去执行。
二叉树最小深度
解析：完全二叉树时深度最小，这个时候用到了等比数列的运算方法。
Sn=na1 (q=1)
Sn=a1(1-q^n)/(1-q) =(a1-anq)/(1-q) (q≠1)
二叉树、度数、节点数
解析：
- 二叉树的第i 层上至多有2^(i-1) 个结点。
- 深度为k 的二叉树至多有2^k-1 个结点。
满二叉树：深度为k，有2^k-1 个结点。
完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n 个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1 到n。 - 叶子结点n0，度为2 的结点为n2，则n0 = n2+1。
考虑结点个数：n = n0 + n1 + n2
考虑分支个数：n-1 = 2n2 + n1
可得n0 = n2+1 - n 个结点的完全二叉树深度为。log2(n+1)
- n 个结点的完全二叉树，结点按层次编号
有： i 的双亲是n / 2，如果 i = 1 时为根（无双亲）；
i 的左孩子是2i，如果2i>n，则无左孩子；
i 的右孩子是2i + 1，如果2i + 1>n 则无右孩子。
网络号
解析：
二叉树
解析：
- A答案中二叉树有可能是空的，所以可以没有节点数为2
- B答案 10层最多节点为：2^10-1=1023，所以1025个节点最小为11层，最大是单只树1025层
总结基本概念：
基本概念
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——如图(a)；
(2)只有一个根结点的二叉树——如图(b)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形
分治算法
解析：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。
拓扑序列
解析：
不断选取入度为0的节点，然后将其后继节点的入度减一，依次计算。
拓扑序列的求解方法：
(1)、找到一个没有后继的顶点(如果有一条边从A指向B,那么B是A的后继)。
(2)、从图中删除这个顶点，在列表的前面插入顶点的标记。
(3)、重复步骤1和2.直到所有的顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结果。
判断有向图是否有环
判断图有无环的方法包括：1.DFS 2.拓扑排序 3.求最短路径
判断 无向图 中是否存在回路（环）的算法描述
如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。
算法：
第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。
第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。
如果最后还有未删除顶点，则存在环，否则没有环。
有向图是否有环的判定算法，主要有深度优先和拓扑排序两种方法。
