背景
我是8月份中旬开始复习的，快考试的时候整理出来的这篇文档，本意是帮助自己冲刺复习用的，再加上我是计算机科学与技术专业的，所以很多知识平时都要用到，所以对我来说，需要了解的东西就会少很多，下面这些内容是我觉得需要注意的，原文档我放在GitHub上：408冲刺复习提纲.md，大家如果有补充可以提PR，能帮助到有需要的人就最好了。复习不易，大家加油。
数据结构
KMP算法，next数组：对应位置前缀和后缀的最长公共部分长度排序
排序算法关键字比较次数与原始序列无关：简单选择排序、二分插入排序不稳定排序算法：快排、希尔排序、选择排序、堆排多路归并排序 置换-排序最佳归并树败者树 基数排序 最高位优先：逐级排序最低位优先：分配，收集图论
不给定存储结构的图遍历是不唯一的；而给定了存储结构的图的深度遍历和广度遍历都是唯一的图的基本概念 连通分量：极大连通子图强连通图：任意结点直接都有双向路径极小：再加一条边就有环；极大：不能再扩充顶点 最短路径，最小生成树的生成过程关键路径十字链表存储有向图；邻接多重表存储无向图查找
哈希冲突解决方法
开放定址法
线性探测法
平方探测法
d+12,d−12,d+22,d−22,...d + 1^2,d - 1^2,d + 2^2,d-2^2,... d+12,d−12,d+22,d−22,...
链地址法
哈希装填因子：关键字个数和表长度比值
B树
性质 每个结点最多m个分支，根结点最少两个分支，非根结点最多ceil(m / 2)个分支有n个分支的节点有n - 1个关键字叶结点处于同一层，可以用空指针表示，表示查找失败的结点 B树的查找叫多路查找，同二叉树的查找；新插入的结点总是出现在终端结点上插入过程中破坏了B树特性，需要进行结点的拆分删除过程中破坏了B树特性，如使得结点关键字个数少于最少需求，就要进行关键字的交换，或者分支合并插入只会使得B树逐渐变高，而不会改变叶子结点在同一层的特性删除可能会引起B树的连锁反应，这个影响是有可能传递到根的
B+树
具有n个关键字的结点有n个分支叶子结点包含信息，且包含了所有的关键字所有叶子结点串成链表非叶子结点只起到一个索引作用
平衡二叉树的旋转
计算机组成原理
基本概念
计算机性能
IPCCPI
215=32768,216=655362^{15}=32768,2^{16}=65536 215=32768,216=65536
FLOPS，K->M->G->T->P->E->Z
数据表示与运算
原码，补码，移码比较
IEEE754浮点数格式， float，double，浮点数范围，浮点数表示
float 8 位阶码，double 11 位阶码
1.m∗2M−127,M∈[0,255]1.m*2^{M-127},M\in[0, 255] 1.m∗2M−127,M∈[0,255]
阶码全0表示无穷小(-127)，全1表示无穷大(128)，因此阶码范围[-126, 127]
绝对值最小规约数
±1.0∗2−126\pm 1.0*2^{-126} ±1.0∗2−126
绝对值最大规约数
±(2−2−23)∗2127\pm (2-2^{-23})*2^{127} ±(2−2−23)∗2127
NaN：指数全一，尾数非全零
浮点数加法
对阶，small -> big尾数相加尾数规格化 左归，阶码减少，不可能溢出右归，阶码增加，有可能溢出 舍入溢出判断 上溢，异常，中断下溢，机器零处理
两个无符号数相加OF可能为1（溢出），相减CF可能为1（小-大，借位）
定点补码溢出判断（机器级判断）
单符号：操作数符号相同，结果符号与操作数符号不同双符号：双符号位符号不同表示溢出，且最高符号位表示最终运算结果符号
乘法就是加法和移位共同作用，比如4位数相乘就进行了4次加法和4次移位
存储系统
SRAM，DRAM，ROM，随机，只读
SRAM：双稳态触发器DRAM：电容，需要刷新ROM：Flash，常用于U盘，固态硬盘，写入前得先擦除
主存与CPU的连接，特别是DRAM片选时，行列地址线复用
双端RAM：可同时读，不可同时写，不可同时读写
交叉存储器连续读区n个字的时间
t=T+(n−1)τt=T+(n-1)\tau t=T+(n−1)τ
DRAM的刷新
集中刷新：存在死时间分散刷新：不存在死时间异步刷新：死时间只是一个读写周期
Cache替换策略LRU算法需要加额外的位
log2nlog_2n log2n
Cache相关计算
h命中率tc命中时间tc访问主存时间ta平均访问时间=h∗tc+(1−h)∗tme访问效率=tctah命中率\\t_c命中时间\\t_c访问主存时间\\t_a平均访问时间=h*t_c+(1-h)*t_m\\e访问效率=\frac{t_c}{t_a} h命中率tc命中时间tc访问主存时间ta平均访问时间=h∗tc+(1−h)∗tme访问效率=tatc
指令系统
寻址方式，间址扩大寻址范围
立即寻址（操作数），直接寻址（地址）寄存器间接寻址，存储器间接寻址基址寻址（程序段），变址寻址（数组）相对寻址，注意取指后PC会+1，偏移位置的计算堆栈寻址，参数传递
指定地址码可能的情况
寄存器编号设备端口地址主存地址数值
不定长操作码指令格式：注意前缀一定不能相同（同哈夫曼编码）
CPU
运算器构成元素
ALU累加寄存器通用寄存器PSW暂存寄存器
控制器构成元素
PCIRMARMDR指令译码器
用户可见寄存器
通用寄存器PCACCPSW
CPU控制方式
同步控制 统一节拍（统一的时序信号）不统一节拍（通过增加冗余节拍来达到统一节拍）中央控制和局部控制相结合的方法（乘、除和浮点运算） 异步控制（采用应答机制，一般用于高速主机和低速设备中，如I/O）
指令周期包含若干机器周期，机器周期包含若干时钟周期
控制存储器（ROM）
微指令的编码方式
直接编码，长度长n字段直接编码：互斥指令归一类，长度短log (n + 1)，需要译码字段间接编码
微指令序列地址形成
断定方式译码方式，根据操作码增量计数器，(CMAR) + q -> CMAR分支转移，根据外部转移条件转移硬件直接产生
| 需要的微指令条数 | 少 | 多 |
| 和机器指令的相似程度 | 差别大 | 相似 |
| 备注 | 用较短的微程序结构换较长的微指令结构 | 用较长的微程序结构换较短的微指令结构 |
指令流水线
超标量流水线超极流水线超长指令字
流水线阻塞因素
结构相关：竞争同一资源导致，解决： 指令和数据分离延后时钟周期 数据相关：同步问题，解决： 延后时钟周期数据旁路 控制相关：跳转指令，解决： 分支预测指令预取
流水线性能分析
吞吐率
加速比
k=不使用流水线的时间使用流水线的时间k=\frac{不使用流水线的时间}{使用流水线的时间} k=使用流水线的时间不使用流水线的时间
流水线效率
E=n个任务总面积实际面积E=\frac{n个任务总面积}{实际面积} E=实际面积n个任务总面积
总线
总线分类（按功能划分） 片内总线：CPU内部系统总线：计算机系统内通信总线：计算机之间 总线两种定时方式 同步通信：统一时钟信号管理异步通信：”握手“，”应答“。常用于通信双方速度差异较大的设备之间 不互锁：啥也不管半互锁：半双工全互锁：三次握手 总线性能指标 总线时钟周期：机器时钟周期总线时钟频率：总线时钟周期的倒数总线工作周期：一次总线操作需要多少个总线时钟周期总线工作频率：总线工作周期的倒数 总线复用：地址/信号线复用总线标准（趋势：串行总线代替并行总线） 系统总线，FBS，QPI（串行总线，Intel提出）局部总线，PCI（并行总线），PCI-E（串行总线）设备总线 并行总线：SCSI，IDE串行总线：USB，SATAI/O系统
RAID RAID0：内容分开存RAID1：内容冗余存RAID2：海明码校验纠错RAID3~5：奇偶校验 I/O接口，设备中断码传递通过数据总线，CPU检测中断信号通过控制总线，I/O接口有很多I/O端口I/O接口中的控制寄存器和状态寄存器可以复用中断处理过程 中断向量，中断向量地址，硬件产生向量地址，由向量地址找到向量中断隐指令 关中断保存断点（PC，PSW）找到中断服务程序 保存现场*（和 PSW（多重中断））*中断服务程序关中断（多重中断）恢复现场*（和 PSW（多重中断））*开中断中断最后一条指令为返回指令 中断到来顺序和中断响应顺序没有关系，中断响应顺序根据硬件排队器和中断屏蔽字实现中断检查发生在每条指令执行末端，也就是中断周期内检查。所以外中断有延时，而异常没有延时DMA 一次DMA请求对应与总线的使用权争夺，一次DMA请求传送一个字的数据，一次DMA传送操作中对应多次DMA请求DMA的优先级比程序中断的优先级高操作系统
操作系统发展历程
体系结构 微内核，代表Windows宏内核，代表Linux 核心态转向用户态由一条指令实现，这条指令是特权指令，一般是中断返回指令进程管理
进程状态转换
进程创建就通过原语完成，PCB大小和内存容量决定进程创建数量，PCB是进程存在唯一标志进程阻塞是主动行为，进程唤醒是被动行为
处理机调度
高级调度：作业调度中级调度：内存调度（挂起，激活）低级调度：进程调度
调度指标
周转时间：作业完成时间-作业提交时间平均周转时间带权周转时间：作业周转时间/作业实际运行时间平均带权周转时间等待时间响应时间：从用户提交作业到首次响应的时间
进程调度优先级
系统高于用户前台高于后台I/O高于CPU
作业调度算法
进程同步互斥原则
空闲让进忙则等待有限等待让权等待
互斥软件实现方法
单标志法，特点：确保进程互斥访问临界区；两个进程必须交替进入临界区双标志先检查法，特点：进程不必交替进入，但是不能保证互斥访问双标志后检查法，特点：确保进程互斥访问临界区，但是会发生饥饿现象皮特森算法，特点：单标志法和双标志后检查法的结合，其中单标志表示优先哪个进程进入临界区（谦让），特点：效果好，互斥且不饥饿
皮特森算法不满足让权等待原则，信号量机制也不满足让权等待原则，记录型信号量机制满足让权等待原则
生产者-消费者问题：生产者和消费者是互斥关系，生产者和生产者或消费者和消费者是同步关系
读写问题，写写和读写互斥，读读不互斥
设置读进程数count变量，同时还要设置mutex保护count为写互斥单独设置mutex写饥饿的处理：设置写优先互斥变量
哲学家进餐问题
用lock同时锁左右（AND型信号量）用互斥量同时锁左右
死锁条件
互斥不剥夺请求保持循环等待
死锁解决
预防死锁：破坏死锁条件避免死锁：防止系统进入不安全状态死锁检测和解除，允许死锁发生，不过可以检查出来且可以解除
管道通信，半双工通信
临界区：访问临界资源的代码
管程：语法层面，组成如下
管程名称数据结构的说明函数（过程）初始化语句
内存管理
连续分配方式 单一连续分配固定分区分配动态分区分配 动态分区分配算法 首次适应循环首次适应最优适应（碎片最多）最差适应（利用率低） 虚拟存储器的容量取决于地址空间的大小页面分配策略 固定 局部 可变 全局局部抖动，颠簸，原因：对换过多，内存不足，置换算法不当同一进程中，段表只有一个，而页表可能多份文件管理
逻辑文件，有结构文件，顺序文件，索引文件，索引顺序文件物理结构，顺序存储，显式链式存储，隐式链式存储，索引存储（i节点）相对路径有利于加快检索速度文件控制块FCB：存放控制文件需要的各种信息的数据结构，FCB的有序集合就是目录，一个目录项就是一个FCB文件打开，需要路径，返回句柄，之后的所有读写删除都是利用这个句柄进行操作磁盘调度寻道算法 先来先服务（公平算法）最短寻道优先电梯算法（扫描算法）循环扫描算法改进的电梯算法，循环扫描算法 目录实现，具体实现方法的优劣根据题目具体分析 线性列表哈希法 空闲文件管理 索引表法位示法（注意起始点是0还是1）成组链接法（UNIX超级块） 系统对文件操作函数第一步就是要用名字open，得到一个句柄，之后的所有操作都是用句柄操作，而不使用名字I/O管理
I/O层次
用户层（库函数）设备独立层（系统调用，设备分配和回收）驱动（抽象转具体，型号上报）中断（进程上下文切换，中断信号源测试，读取设备状态）设备控制器（硬件）
DMA
通道：专门负责输入/输出的处理机
指令单一无自己的内存，与CPU共享内存所执行的通道程序也是放在内存中
缓冲（充满缓冲区的时间T，充满用户区的时间M，CPU处理时间C）
单缓冲
M+max{C,T}M+max\{C,T\} M+max{C,T}
双缓冲
max{C+M,T}max\{C+M,T\} max{C+M,T}
设备分配
数据结构 设备控制表DCT控制器控制表COCT通道控制表CHCT系统设备表SDT 策略（设备分配，过三关） 分配设备分配控制器分配通道分配过程中访问的数据结构顺序：SDT -> DCT -> COCT ->CHCT
计算机网络
前置知识
协议模型，ISO，TCP/IP
码元：离散状态，波特率：码元速率
公式
奈奎斯特定理：无噪声极限速率
2Wlog2M2Wlog_2M 2Wlog2M
香农定理：有噪声极限上限速率
Wlog2(1+SN)dB=10log10SNWlog_2(1 + \frac{S}{N}) \\ dB = 10log_{10}\frac{S}{N} Wlog2(1+NS)dB=10log10NS
两公式都可用
min{奈奎斯特，香农}min\{奈奎斯特，香农\} min{奈奎斯特，香农}
编码，曼切斯特编码，差分曼切斯特编码（同1异0，与前一码元比较）
编码过程（典型例子，PCM）
采样量化编码
调制
调幅调频调相
分组交换
物理接口特性
机械特性电气特性：电压，电相关的东西功能特性：电平，信号线（数据线，控制线）用途过程特性：时序
数据链路层
零比特填充法：五个连续的1插入一个0
奇偶校验码，添加冗余位后1的个数定奇偶
循环冗余码CRC：多项式除多项式
海明码
检错d位，码距d + 1；纠错d位，码距2d + 1
数据位m，冗余位r，满足
2r≥m+r+12^r \ge m + r + 1 2r≥m+r+1
争用期，经典公式
信道利用率=L数据v发L确认帧v发+L数据v发+2τ信道利用率 = \frac{\frac{L_{数据}}{v_发}}{\frac{L_{确认帧}}{v_发}+\frac{L_{数据}}{v_发}+2\tau} 信道利用率=v发L确认帧+v发L数据+2τv发L数据
后退N帧（GBN）协议
接收方可累计确认（捎带确认），ACKn表示对n号及以前的帧全部正确收到，且期待接受n+1号帧
发送窗口
1≤WT≤2n−11 \le W_T\le2^n-1 1≤WT≤2n−1
接受窗口：1
选择重传（SR）协议，滑动窗口
接收方对每一帧逐一确认
发送窗口和接受窗口
WT+WR≤2nmostlyWR=WT=2n−1W_T + W_R \le 2^{n}\\ mostly \quad\quad\quad W_R=W_T=2^{n-1} WT+WR≤2nmostlyWR=WT=2n−1
静态划分信道
FDM，TDM，WDM码分多路复用（CDMA）
动态划分信道
CSMA（载波监听多点接入）
CSMA/CD（碰撞检测）
Lv≥2τ\frac{L}{v} \ge 2\tau vL≥2τ
帧长度范围[64,1518]
CSMA/CA（碰撞避免）
发送方：发送前检测信道是否空闲发送方：空闲则发RTS，否则则等待接收方：接受到RTS后，则响应CTS发送方：接受到CTS后，开始发数据（同时预约信道）接收方：接受到数据后，响应ACK
802.11的MAC帧头格式，注意四个地址
地址1：接受端地址2：发送端地址3：目的地址地址4：源地址
网桥
透明网桥源路由网桥
交换机
直通交换机：只需检查6B的目的地址就直接发走存储转发式交换机
网络层
IGP动态路由算法
全局性：链路状态算法OSPF分散性：距离向量算法RIP
EGP外部网关协议：BGP
常用路由协议区分
IP数据包分片
变长子网划分（可得到最小子网）：参考ABC三类IP地址划分
ICMP
ICMP差错报文 终点不可达源点抑制超时重定向 ICMP询问报文 回送请求和回答（ping）
IPv6
首部固定40字节，且首部长度必须是8字节整数倍原地址，目的地址128位IPv6只能在主机进行分片，而IPv4可以在主机和路由器分片IPv6地址的写法，零压缩 连续的0000可以用0表示0:0:0可以用::表示
移动IP：移动结点以固定的网络IP地址，实现跨越不同网段的漫游功能
移动结点：设备归属代理（本地代理）永久地址外部代理（外地代理）
路由器
路由选择：根据路由选择协议和路由表进行处理分组转发：构建转发表，根据转发表转发
