顺序表（线性表）可随机存储，存储密度大（无指针）。
单链表（线性表）顺序存储，非连续存储空间，更容易表示逻辑结构。
n个元素进栈，共有种出栈方式（卡特兰数）
栈的应用：递归、进制转换、迷宫求解、局部变量、括号匹配
队列应用：广度优先、层次遍历、资源竞争、缓冲区
中缀->后缀
1） 数字直接加入
2）非括号运算符，入栈前将优先级比它高的弹出。
- 遇到（ 入栈
- 遇到 ）把 ( 和后面的运算符都弹出。
- 将最后栈里的运算符弹出
有n个节点的树有n-1个边
树中节点数等于所有节点的度和加1，
树的路径长度=根到每个节点路径长度总和
二叉树：每个节点最多有两个子树，有左右之分不可颠倒
平衡二叉树：左右子树高度差不超过1
前缀编码：字符集中没有一个编码是，另一个编码的前缀
B树
每个节点至多m个子树（m-1个关键字）
根节点不是终端的话，至少有两个子树
除根节点外，非叶节点至少m/2向上取整个子树
叶结点都在一层，不带信息
按照二叉树的定义，4个节点的二叉树有多少种？
0个节点的二叉树有1种,即f(0)=1;
1个节点的二叉树有1种,即f(1)=1;
2个节点的二叉树有2种，即f(2)=2；
3个节点的二叉树肯定先得固定一个根节点，然后还剩2个节点，这两个节点有三种排列方式，根节点左边两个、根节点左边一个右边一个、根节点右边两个，这样的话就可以用f(0),f(1)和f(2)来求了：;同理
;于是就有了递推公式：
。
前中后序遍历
光有前序遍历和后序遍历是无法还原二叉树的。
已知某二叉树的前序遍历为A-B-D-F-G-H-I-E-C,中序遍历为F-D-H-G-I-B-E-A-C,请还原这颗二叉树。
已知某二叉树的中序遍历为F-D-H-G-I-B-E-A-C,后序遍历为F-H-I-G-D-E-B-C-A,请还原这颗二叉树。
完全图：任意两个顶点存在边（有向图，无向图
)
连通图：任意两个顶点连通
连通分量：无向图中的极大连通子图
7个顶点任意情况下连通边最少：6个是完全图6*5/2+1（另一个顶点）
进程状态
运行状态：进程正在处理机上运行
就绪状态：进程已获得了除处理机之外的一切所需资源
阻塞状态：进程正在等待某一事件而暂停运行
创建状态：进程正在被创建，尚未转到就绪状态
结東状态：进程正从系统中消失，分为正常结束和异常退出
就绪状态→运行状态：经过处理机调度，就绪进程得到处理机资源
运行状态→就绪状态：时间片用完或在可剥夺系统中有更高优先级进程进入
运行状态→阻塞状态：进程需要的某一资源还没准备好
阻塞状态→就绪状态：进程需要的资源已准备好
死锁
产生条件：
- 系统资源的竞争
- 进程推进顺序非法
- 死锁产生的必要条件
互斥条件
不剥夺条件
请求和保持条件
循环等待条件（循环等待链）
处理策略：
- 死锁预防
破坏四个必要条件 - 避免死锁
资源动态分配过程中，防止系统进入不安全状态；银行家算法 - 死锁的检测和解除
资源剥夺；撤销进程；进程回退
网络层
OSI中的层
| 层 | 功能 | 协议 | 设备 |
|---|---|---|---|
| 应用层 | 为操作系统或网络应用程序提供访问网络服务的接口。 | FTP（文件传送协议）、Telnet（远程登录协议）、DNS（域名解析协议）、SMTP（邮件传送协议），POP3协议（邮局协议），HTTP协议（Hyper Text Transfer Protocol） | |
| (TCP/IP无)表示层 | 数据格式化、转换 | ||
| (TCP/IP无)会话层 | 管理主机之间的会话进程 | ||
| 传输层 | 提供端对端传输 | T CP协议（Transmission Control Protocol，传输控制协议）、UDP协议（User Datagram Protocol，用户数据报协议） | 网关 |
| 网络层 | 路由选择 | IP协议（Internet Protocol，因特网互联协议）;ICMP协议（Internet Control Message Protocol，因特网控制报文协议）;ARP协议（Address Resolution Protocol，地址解析协议）;RARP协议（Reverse Address Resolution Protocol，逆地址解析协议）。 | 路由器 |
| 数据链路层 | 提供可靠的数据传输 | 以太网协议 | 网桥和交换机 |
| 物理层 | 提供一个传输数据的可靠的物理媒体 | 中继器（Repeater，也叫放大器）和集线器 |
地址解析协议，即ARP（Address Resolution Protocol），是根据IP地址获取物理地址的一个TCP/IP协议。
DNS是域名系统(DomainNameSystem)，将URL转换为IP地址
NAT网络地址转换(Network Address Translation)属接入广域网(WAN)技术，是一种将私有（保留）地址转化为合法IP地址的转换技.
IP地址
255.255.255.255该IP地址指的是受限的广播地址。
受限广播地址只能用于本地网络，路由器不会转发以受限广播地址为目的地址的分组；一般广播地址既可在本地广播，也可跨网段广播。
localhost
不联网 ，不使用网卡，不受防火墙和网卡限制 ，本机访问
127.0.0.0/8
不联网 ，网卡传输，受防火墙和网卡限制 ，本机访问
用作回环地址，在主机上发送给127开头的IP地址的数据包会被发送的主机自己接收。
本机IP
联网 ，网卡传输 ，受防火墙和网卡限制 ，本机或外部访问
0.0.0.0
它表示本机中所有的IPV4地址。
私有地址(private address)
也叫专用地址，它们不会在全球使用，只具有本地意义。
A类私有地址：10.0.0.0/8，范围是：10.0.0.0~10.255.255.255
B类私有地址：172.16.0.0/12，范围是：172.16.0.0~172.31.255.255
C类私有地址：192.168.0.0/16，范围是：192.168.0.0~192.168.255.255
子网掩码
标志两个IP地址是否同属于一个子网的，也是32位二进制地址，其每一个为1代表该位是网络位，为0代表主机位。如果两个IP地址在子网掩码的按位与的计算下所得结果相同，即表明它们共属于同一子网中。
子网划分
主机位全0代表网络地址
主机位全1代表广播地址
解析：先判断为C类地址，要五个子网，需要三个1：11100000；剩下五个主机数，2的五次方-2=30>28，所以主机数也够，因此子网掩码应为：255.255.255.224；
三次握手
TCP报文
序列号seq：占4个字节，用来标记数据段的顺序
确认号ack：占4个字节，期待收到对方下一个报文段的第一个数据字节的序号
确认位ACK：占1位，仅当ACK=1时，确认号字段ack才有效
同步位SYN：连接建立时用于同步序号。SYN这个标志位只有在TCP建产连接时才会被置1，握手完成后SYN标志位被置0。
终止FIN：用来释放一个连接。FIN=1表示：此报文段的发送方的数据已经发送完毕，并要求释放运输连接
四次挥手
为什么要三次握手呢？主要是为了信息对等和防止出现请求超时导致脏连接。
只有三次握手之后才能够保证两台服务器都具备发报和收报能力。
为什么连接的时候是三次握手，关闭的时候却是四次握手
答：
Server端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉Client端，"你发的FIN报文我收到了"。只有等到我Server端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四步握手。
如果已经建立了连接，但是客户端突然出现故障了怎么办?
答：
TCP还设有一个保活计时器，服务器每收到一次客户端的请求后都会重新复位这个计时器，时间通常是设置为2小时，若两小时还没有收到客户端的任何数据，服务器就会发送一个探测报文段，以后每隔75分钟发送一次。若一连发送10个探测报文仍然没反应，服务器就认为客户端出了故障，接着就关闭连接。
为什么客户端发出第四次挥手的确认报文后要等2MSL的时间才能释放TCP连接？
这里同样是要考虑丢包的问题，如果第四次挥手的报文丢失，服务端没收到确认ack报文就会重发第三次挥手的报文，这样报文一去一回最长时间就是2MSL，所以需要等这么长时间来确认服务端确实已经收到了。
http、https
HTTP：运行在 TCP 之上，明文传输，客户端与服务器端都无法验证对方的身份
HTTPS：身披 SSL( Secure Socket Layer )外壳的 HTTP，运行于 SSL 上，SSL 运行于 TCP 之上， 是添加了加密和认证机制的 HTTP。
状态码的类别：
| 类别 | 原因短语 |
|---|---|
| 1XX | Informational（信息性状态码） 接受的请求正在处理 |
| 2XX | Success（成功状态码） 请求正常处理完毕 |
| 3XX | Redirection（重定向状态码） 需要进行附加操作以完成请求 |
| 4XX | Client Error（客户端错误状态码） 服务器无法处理请求 |
| 5XX | Server Error（服务器错误状态码） 服务器处理请求出错 |
TCP和UDP有哪些区别。
GET和POST区别
GET：从服务器上获取数据，也就是所谓的查，仅仅是获取服务器资源，不进行修改。
POST：向服务器提交数据，这就涉及到了数据的更新，也就是更改服务器的数据。
PUT：英文含义是放置，也就是向服务器新添加数据，就是所谓的增。
DELETE：从字面意思也能看出，这种方式就是删除服务器数据的过程。
Get是不安全的，因为在传输过程，数据被放在请求的URL中；Post的所有操作对用户来说都是不可见的。 但是这种做法也不时绝对的，大部分人的做法也是按照上面的说法来的，但是也可以在get请求加上 request body，给 post请求带上 URL 参数。
Get请求提交的url中的数据最多只能是2048字节，这个限制是浏览器或者服务器给添加的，http协议并没有对url长度进行限制，目的是为了保证服务器和浏览器能够正常运行，防止有人恶意发送请求。Post请求则没有大小限制。
Get限制Form表单的数据集的值必须为ASCII字符；而Post支持整个ISO10646字符集。
Get执行效率却比Post方法好。Get是form提交的默认方法。
对称加密与非对称加密
对称密钥加密是指加密和解密使用同一个密钥的方式，这种方式存在的最大问题就是密钥发送问题，即如何安全地将密钥发给对方；
而非对称加密是指使用一对非对称密钥，即公钥和私钥，公钥可以随意发布，但私钥只有自己知道。发送密文的一方使用对方的公钥进行加密处理，对方接收到加密信息后，使用自己的私钥进行解密。
由于非对称加密的方式不需要发送用来解密的私钥，所以可以保证安全性；但是和对称加密比起来，非常的慢
简述 cookie？和 session的区别
cookie是由Web服务器保存在用户浏览器上的小文件（key-value格式），包含用户相关的信息。客户端向服务器发起请求，如果服务器需要记录该用户状态，就使用response向客户端浏览器颁发一个Cookie。客户端浏览器会把Cookie保存起来。当浏览器再请求该网站时，浏览器把请求的网址连同该Cookie一同提交给服务器。服务器检查该Cookie，以此来辨认用户身份。
1, session在服务器端， cookie在客户端（浏览器）
2，session的运行依赖 session id，而 session id是存在 cookie中的，也就是说，如果浏览器禁用了 cookie，同时 session也会失效，存储 Session时，键与 Cookie中的sessionid相同，值是开发人员设置的键值对信息，进行了base64编码，过期时间由开发人员设置
3，cookie安全性比 session差
SQL注入
解決方式：通过传参数方式解决SQL注入
关系型数据库和非关系型数据库
关系模型指的就是二维表格模型，好比Excel文件中的表格，强调用表格的方式存储数据（有字段，表与表之间还有关系）
- Oracle
- Microsoft SQL Server
- MySQL：数据保存在磁盘中，检索的话，会有一定的操作，访问速度相
对慢- SQLite（手机端的）
非关系型数据库,即NoSQL（not only SQL），非关联型的，强调Key-Value的方式存储数据
- MongoDB
- Redis：内存型，数据保存在内存中，速度快
进程与线程的区别
1.线程是程序执行的最小单位，而进程是操作系统分配资源的最小单位
- 一个进程由一个或多个线程组成，线程是一个进程中代码的不同执行路线
- 进程之间相互独立，但同一进程下的各个线程之间共享程序的内存空间(包括代码段，数据集，堆等)及一些进程级的资源(如打开文件和信号等)，某进程内的线程在其他进程不可见；
4.调度和切换：线程上下文切换比进程上下文切换要快得多
