数据结构
1.排序
排序有：
不稳定：快速排序，希尔排序，选择排序，堆排序（速记：快些选一堆朋友聊天）
稳定：除不稳定外，都是稳定的。
注释：归并排序的空间复杂度为O(n)，快速排序的空间复杂度为O(log2(n)）
排序具体过程：https://www.cnblogs.com/hokky/p/8529042.html
快速排序参考：https://blog.csdn.net/wei_cheng18/article/details/80302818
归并排序参考：https://www.cnblogs.com/ludashi/p/6051871.html
其他基础知识：https://www.cnblogs.com/ksWorld/p/7537157.html
操作系统
进程是系统进行资源调度和分配的基本单位；线程是CPU调度的基本单位。
进程 = 资源 （包括寄存器值，PCB，内存映射表）+ TCB（栈结构）
线程 = TCB（栈结构）
进程 间的资源是分隔独立的，内存映射表不同，占用物理内存地址是分隔的
线程 的资源是共享的
进程 的切换不仅要切换PC，还包括切换资源，即切换内存映射表
线程 的切换只是切换PC，切换了TCB（栈结构）
区别：
（1）进程具有独立的空间地址，一个进程崩溃后，在保护模式下不会对其它进程产生影响。
（2）线程只是一个进程的不同执行路径，线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉。
内存管理
要解决的两个问题
1）每个进程代码中使用的地址可能相同。解决思路：对代码中的地址重定向（加个基地址）。
2）物理内存可能比较小，不能同时放很多进程进来。解决思路：把要运行的代码移到内存，暂时不用的代码移入磁盘，即交换（swap），内存置换
1.分段
2 页表
3 段页结合的内存管理
4 请求调页内存换入
5 内存换出：
有页表需要调入，那么谁调出。
页面置换算法
1：最佳置换算法（Optimal）：一种理论的算法，选着淘汰的页面是以后一定不再使用的页面（理想化的），该算法无法实现，只能作为其他算法好坏的一个评价对比。
2：先进先出（FIFO）算法：总是最先淘汰最先进去的页面，该算法容易实现。缺点：通常程序调入内存的先后顺序和程序执行的先后顺序不一致，导致缺页率高。
3：最近最久未使用算法LRU：算法赋予每个页面一个访问字段，用来记录上次页面被访问到现在所经历的时间t，每次置换的时候把t值最大的页面置换出去(实现方面可以采用寄存器或者栈的方式实现)。
4：时钟算法clock(也被称为是最近未使用算法NRU)：页面设置一个访问位R，并将页面链接为一个环形队列，页面被访问的时候访问位设置R为1。页面置换的时候，如果当前指针所指页面访问R为0，那么置换，否则将其置为0，循环直到遇到一个访问为位0的页面。
但是这个方法有缺点：缺页比较少的时候（最近没有使用淘汰中的“最近”太长了），所有的R都为1（很少变成0）,每次都要转一圈才能找到换出去的页，退化成FIFO，效率不高。
改进： 双指针，一个快，一个慢，像时钟一样 （定时清除R位）（更像clock）
快时钟做R的清0定时清0,等到慢指针转到这里的时候R=0,说明在定时时间片内没有备访问，该页可以被替换了。
计算机网络
2.IP地址分类
IP地址是32位的二进制数值，用于在TCP/IP通讯协议中标记每台计算机的地址。通常我们使用点式十进制来表示，如192.168.0.5等等。
每个IP地址又可分为两部分。即网络号部分和主机号部分：网络号表示其所属的网络段编号，主机号则表示该网段中该主机的地址编号。按照网络规模的大小，IP地址可以分为A、B、C、D、E五类。
注意：
1）以下是留用的内部私有地址，Internet上没使用的地址
A类 10.0.0.0--10.255.255.255
B类 172.16.0.0--172.31.255.255
C类 192.168.0.0--192.168.255.255
2）IP地址与子网掩码相与得到网络号
3）主机号，全为0的是网络号（例如：192.168.2.0），主机号全为1的为广播地址（192.168.2.255）
3，ARP是地址解析协议，简单语言解释一下工作原理。
地址解析协议，即ARP（Address Resolution Protocol），是根据IP地址获取物理地址的一个TCP/IP协议。
1：首先，每个主机都会在自己的ARP缓冲区中建立一个ARP列表，以表示IP地址和MAC地址之间的对应关系。
2：当源主机要发送数据时，首先检查ARP列表中是否有对应IP地址的目的主机的MAC地址，如果有，则直接发送数据，如果没有，就向本网段的所有主机发送ARP数据包，该数据包包括的内容有：源主机 IP地址，源主机MAC地址，目的主机的IP 地址
3：当本网络的所有主机收到该ARP数据包时，首先检查数据包中的IP地址是否是自己的IP地址，如果不是，则忽略该数据包，如果是，则首先从数据包中取出源主机的IP和MAC地址写入到ARP列表中，如果已经存在，则覆盖，然后将自己的MAC地址写入ARP响应包中，告诉源主机自己是它想要找的MAC地址。
4：源主机收到ARP响应包后。将目的主机的IP和MAC地址写入ARP列表，并利用此信息发送数据。如果源主机一直没有收到ARP响应数据包，表示ARP查询失败。
注意：广播（255.255.255.255）发送ARP请求，单播发送ARP响应。
传输层和网络层的区别：
网络层为不同的主机提供通信服务，传输层为不同应用进程提供通信服务。
网络层只对报文头部进行差错检测，而传输层对整个报文进行差错检测。
6, 在浏览器中输入www.baidu.com后执行的全部过程
1、客户端浏览器通过DNS解析到www.baidu.com的IP地址220.181.27.48，通过这个IP地址找到客户端到服务器的路径。客户端浏览器发起一个HTTP会话到220.161.27.48，然后通过TCP进行封装数据包，输入到网络层。
2、在客户端的传输层(添加TCP头)，把HTTP会话请求分成报文段，添加源和目的端口，如服务器使用80端口监听客户端的请求，客户端由系统随机选择一个端口如5000，与服务器进行交换，服务器把相应的请求返回给客户端的5000端口。然后使用IP层的IP地址查找目的端。
3、客户端的网络层（添加IP头）不用关系应用层或者传输层的东西，主要做的是通过查找路由表确定如何到达服务器，期间可能经过多个路由器，这些都是由路由器来完成的工作，我不作过多的描述，无非就是通过查找路由表决定通过那个路径到达服务器。
4、客户端的链路层（添加MAC头），包通过链路层发送到路由器，通过邻居协议查找给定IP地址的MAC地址，然后发送ARP请求查找目的地址，如果得到回应后就可以使用ARP的请求应答交换的IP数据包现在就可以传输了，然后发送IP数据包到达服务器的地址。
