操作系统

操作系统基本特征:并发(并发和并行区别)，共享(同时共享和互斥共享)，虚拟(时分复用和空分复用)，异步

操作系统基本功能:进程管理，内存管理，文件管理，设备管理

系统调用，中断分类(外中断，异常，陷入)

进程管理

进程与线程(概念与区别)，进程状态切换，进程调度(先来先服务(FCFS),短作业优先(SJF),最短剩余时间(SRTN),时间片轮转)

进程同步：临界区，竞争条件，同步与互斥，信号量，管程，消费者生产者，哲学家就餐

进程间通信

死锁

死锁概念，必要条件(互斥，占有和等待，不可抢占，环路等待)

处理方法：鸵鸟策略，死锁检测与恢复，死锁语法，死锁避免

内存管理

虚拟内存，分页系统，页面置换算法(最佳(OPT),最近最久未使用(LRU),先进先出(FIFO))

链接

编译系统：预处理，编译，汇编，链接。静态链接，动态链接

计算机网络

互联网(概念，组成，ISP，网络通信方式)，电路交换与分组交换

计算机网络性能指标(速率，带宽，吞吐量，时延(排队，处理，传输，传播)，时延带宽积，往返时间RTT，利用率)

网络体系结构(各层作用及常用协议)，协议(概念，要素(语法，语义，同步)，TCP/IP协议族

数据在各层之间的传递过程(图)

应用层

DNS

域名系统(作用，系统架构，域名服务器，域名解析过程)

HTTP协议

1 HTTP(概念,url组成:)，HTTP请求与响应报文格式，HTTP连接管理(HTTP请求响应步骤,短连接与长连接)，HTTP(方法,状态码,首部行)

cookie与session，WEB缓存，HTTPS，HTTP/2.0

[关于HTTP协议，一篇就够了](

运输层

运输层提供的服务

UDP/TCP特点

UDP/TCP首部格式

TCP三次握手四次挥手(过程与原因)

可靠传输，滑动窗口，流量控制，拥塞控制

网络层

IP协议(作用，数据报格式)

IP地址编址方式(分类，子网划分，构成超网)

数据链路层

通信方式：点对点(ppp)，广播

三个基本问题：封装成帧，透明传输，差错控制

物理层

通信方式(单攻，半双工，全双工)

算法

递归

递归：是将一个问题分成同样但更小的问题的子问题的求解过程。递归函数在函数体内调用自身以完成递归。
递归三定律：

1. 递归算法必须具有终止情况。即直接求解子问题的情况。
2. 递归算法必须改变其状态并向终止情况靠近。即问题规模应不断减小。
3. 递归算法必须以递归方式调用自身。

分治法

分治算法思想：

1）分解：将原问题划分为若干规模较小、相互独立、与原问题形式相同的子问题，子问题最好规模相同
2）解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题
3）合并：必要时合并子问题

贪婪算法

1贪婪算法思想：

在贪婪算法中，每一步要在一定的标准下做出一个最优决策。在每一步做出的决策，在以后的步骤中都不可更改。做出决策的依据称为贪婪准则

动态规划

1. 算法设计思想

对于具有重复子问题和最优子结构的问题，动态规划建议，与其对重复的子问题一次又一次地求解，还不如把每个较小的子问题求解一次并把结果记录在表中，这样就可以从表中得出原始问题的解。

使用场景

算法设计步骤

1)刻画一个最优解的结构特征
2)递归地定义最优解的值
3)计算最优解的值，通常采用自底向上
4)利用计算出的信息构造一个最优解
如果只需要一个最优解的值，而非最优解本身可以忽略步骤4

知识点

原文：https://www.cnblogs.com/xyq2515922813/p/10787676.html