• 1. 数据结构
  • 1.1. 线性表
  • 1.2. 栈与队列
    • 1.2.1. 栈的应用
      • 1.2.1.1. 括号匹配
      • 1.2.1.2. 中缀转后缀
    • 1.2.2. 矩阵压缩存储
      • 1.2.2.1. 稀疏矩阵
  • 1.3. 串
    • 1.3.1. KMP算法
  • 1.4. 树
    • 1.4.1. 树和森林
      • 1.4.1.1. 双亲表示法
      • 1.4.1.2. 孩子表示法
      • 1.4.1.3. 孩子兄弟表示法（二叉树）
    • 1.4.2. 遍历
    • 1.4.3. 二叉排序树
    • 1.4.4. 赫夫曼树
  • 1.5. 图
    • 1.5.1. 存储
      • 1.5.1.1. 邻接矩阵法
      • 1.5.1.2. 邻接表法
      • 1.5.1.3. 十字链表法（有向图）
      • 1.5.1.4. 邻接多重表法（无向图）
    • 1.5.2. 图算法
      • 1.5.2.1. 拓扑排序
      • 1.5.2.2. 关键路径
  • 1.6. 查找
    • 1.6.1. 顺序查找、折半查找、分块查找
    • 1.6.2. B树
      • 1.6.2.1. 插入
      • 1.6.2.2. 删除
    • 1.6.3. 散列表
      • 1.6.3.1. 散列函数
        • 1.6.3.1.1. 直接定址法
        • 1.6.3.1.2. 除留余数法
        • 1.6.3.1.3. 数字分析法
        • 1.6.3.1.4. 平方取中法
      • 1.6.3.2. 冲突解决
        • 1.6.3.2.1. 开放定址法
        • 1.6.3.2.2. 拉链法
  • 1.7. 排序
    • 1.7.1. 内部排序
    • 1.7.2. 外部排序
      • 1.7.2.1. 置换选择排序（生成初始归并段）
      • 1.7.2.2. 最佳归并树（赫夫曼树）
      • 1.7.2.3. 败者树
• 2. 计算机组成原理
  • 2.1. 概述
    • 2.1.1. 性能指标
      • 2.1.1.1. 机器字长
      • 2.1.1.2. 主存容量
      • 2.1.1.3. 吞吐量
      • 2.1.1.4. 主频
      • 2.1.1.5. CPI
      • 2.1.1.6. MIPS
      • 2.1.1.7. MFLOPS、GFLOPS、TFLOPS
  • 2.2. 运算器
    • 2.2.1. 数据表示
    • 2.2.2. 浮点数
      • 2.2.2.1. IEEE 754
      • 2.2.2.2. 浮点运算
  • 2.3. 存储器
    • 2.3.1. DRAM刷新
    • 2.3.2. 高速缓冲存储器(Cache)
      • 2.3.2.1. 映射方式
        • 2.3.2.1.1. 直接映射
        • 2.3.2.1.2. 全相联映射
        • 2.3.2.1.3. 组相联映射
      • 2.3.2.2. 标记项
      • 2.3.2.3. 替换算法
        • 2.3.2.3.1. FIFO
        • 2.3.2.3.2. LRU
      • 2.3.2.4. 写策略
    • 2.3.3. TLB
      • 2.3.3.1. TLB、Cache、页缺失情况表
  • 2.4. 控制器
    • 2.4.1. 寻址方式
      • 2.4.1.1. 指令寻址
      • 2.4.1.2. 数据寻址
    • 2.4.2. CPU
      • 2.4.2.1. 指令周期
    • 2.4.3. 流水线
      • 2.4.3.1. 性能指标
  • 2.5. 总线
    • 2.5.1. 分类
      • 2.5.1.1. 传输
        • 2.5.1.1.1. 同步定时
        • 2.5.1.1.2. 异步定时
      • 2.5.1.2. 标准
  • 2.6. I/O
• 3. 操作系统
  • 3.1. 进程管理
    • 3.1.1. 调度
      • 3.1.1.1. FCFS
      • 3.1.1.2. SJF
      • 3.1.1.3. 优先级调度
      • 3.1.1.4. 高响应比优先
      • 3.1.1.5. RR
      • 3.1.1.6. 多级反馈队列
    • 3.1.2. 互斥同步
      • 3.1.2.1. 生产者消费者
      • 3.1.2.2. 理发师
      • 3.1.2.3. 读者写者
      • 3.1.2.4. 哲学家进餐
    • 3.1.3. 死锁
      • 3.1.3.1. 必要条件
      • 3.1.3.2. 处理策略
        • 3.1.3.2.1. 死锁预防
        • 3.1.3.2.2. 死锁避免
        • 3.1.3.2.3. 死锁检测与解除
  • 3.2. 内存管理
    • 3.2.1. 装入与链接
      • 3.2.1.1. 静态链接
      • 3.2.1.2. 装入链接
      • 3.2.1.3. 运行链接
      • 3.2.1.4. 绝对装入
      • 3.2.1.5. 重定位装入
      • 3.2.1.6. 运行装入（动态重定位）
    • 3.2.2. 内存分配
      • 3.2.2.1. 连续分配
        • 3.2.2.1.1. 单一连续分配
        • 3.2.2.1.2. 固定分区分配
        • 3.2.2.1.3. 可变分区分配
        • 3.2.2.1.4. 首次适应
        • 3.2.2.1.5. 最佳适应
        • 3.2.2.1.6. 最差适应
      • 3.2.2.2. 非连续分配
        • 3.2.2.2.1. 基本分页
        • 3.2.2.2.2. 基本分段
        • 3.2.2.2.3. 段页式
    • 3.2.3. 置换算法
      • 3.2.3.1. 最佳置换（OPT）
      • 3.2.3.2. 先进先出（FIFO）
      • 3.2.3.3. 最近最久未使用（LRU）
      • 3.2.3.4. 时钟置换、最近未用（CLOCK、NRU）
    • 3.2.4. 分配策略
      • 3.2.4.1. 固定分配局部置换
      • 3.2.4.2. 可变分配局部置换
      • 3.2.4.3. 可变分配全局置换
    • 3.2.5. 地址翻译
  • 3.3. 文件管理
    • 3.3.1. 逻辑结构
      • 3.3.1.1. 无结构文件（流式）
      • 3.3.1.2. 有结构文件（记录式）
    • 3.3.2. 目录结构
    • 3.3.3. 文件共享与保护
      • 3.3.3.1. 共享
      • 3.3.3.2. 保护
    • 3.3.4. 文件分配
    • 3.3.5. 空闲管理
    • 3.3.6. 磁盘调度
      • 3.3.6.1. 延时
      • 3.3.6.2. 调度算法
        • 3.3.6.2.1. FCFS
        • 3.3.6.2.2. 最短寻道距离优先
        • 3.3.6.2.3. 扫描（SCAN、电梯调度）
        • 3.3.6.2.4. 循环扫描（C-SCAN）
  • 3.4. 设备管理
    • 3.4.1. 控制方式
      • 3.4.1.1. 程序查询
      • 3.4.1.2. 中断驱动
      • 3.4.1.3. DMA
      • 3.4.1.4. 通道
    • 3.4.2. 层次结构
    • 3.4.3. 缓冲区
      • 3.4.3.1. 单缓冲
      • 3.4.3.2. 双缓冲
      • 3.4.3.3. 缓冲池
    • 3.4.4. 设备分配与回收
    • 3.4.5. SPOOLing技术
      • 3.4.5.1. 输入井输出井
      • 3.4.5.2. 输入缓冲输出缓冲
      • 3.4.5.3. 输入进程输出进程
• 4. 计算机网络
  • 4.1. 网络体系
    • 4.1.1. OSI
  • 4.2. 应用层
    • 4.2.1. DNS
    • 4.2.2. FTP
    • 4.2.3. SMTP、POP3
    • 4.2.4. HTTP
  • 4.3. 传输层
    • 4.3.1. 端口号
    • 4.3.2. UDP
    • 4.3.3. TCP
      • 4.3.3.1. 建立连接（三次握手）
      • 4.3.3.2. 释放连接（四次挥手）
      • 4.3.3.3. 超时重传
      • 4.3.3.4. 快速重传
      • 4.3.3.5. 流量控制
      • 4.3.3.6. 拥塞控制
  • 4.4. 网络层
    • 4.4.1. 拥塞控制
      • 4.4.1.1. 距离-向量路由算法(RIP)
      • 4.4.1.2. 链路状态路由算法(OSPF)
      • 4.4.1.3. 层次路由
    • 4.4.2. IPv4
      • 4.4.2.1. 分类IP
      • 4.4.2.2. 子网划分
      • 4.4.2.3. CIDR
    • 4.4.3. 地址解析协议(ARP)
    • 4.4.4. 动态主机配置协议(DHCP)
    • 4.4.5. 网际控制报文协议(ICMP)
    • 4.4.6. IPv6
    • 4.4.7. 组播
    • 4.4.8. 路由器
  • 4.5. 链路层
    • 4.5.1. 差错控制
      • 4.5.1.1. 奇偶校验
      • 4.5.1.2. CRC
      • 4.5.1.3. 海明码
    • 4.5.2. 流量控制
      • 4.5.2.0.1. 停等协议
      • 4.5.2.1. GBN
      • 4.5.2.2. SR
    • 4.5.3. 介质访问控制（MAC）
      • 4.5.3.1. ALOHA
      • 4.5.3.2. CSMA
      • 4.5.3.3. CSMA/CD
      • 4.5.3.4. CSMA/CA
      • 4.5.3.5. 令牌环
  • 4.6. 物理层
    • 4.6.1. 香农定理
    • 4.6.2. 奈氏准则
• 5. 数据库原理
  • 5.1. 关系代数
    • 5.1.1. $ \sigma_{cond}(tab) $
    • 5.1.2. $ \pi_{cols}(tab) $
    • 5.1.3. $ tab_1\times tab_2 $
    • 5.1.4. $ tab_1 \Join tab_2 $
• 6. 软件工程
  • 6.1. 设计模式
    • 6.1.1. 创建型模式
      • 6.1.1.1. 简单工厂模式 Simple Factory
      • 6.1.1.2. 工厂方法模式 Factory Method
      • 6.1.1.3. 抽象工厂模式 Abstract Factory
      • 6.1.1.4. 创建者模式 Builder
      • 6.1.1.5. 原型模式 Prototype
      • 6.1.1.6. 单例模式 Singleton
    • 6.1.2. 结构型模式
      • 6.1.2.1. 外观模式 Facade
      • 6.1.2.2. 适配器模式 Adapter
      • 6.1.2.3. 代理模式 Proxy
      • 6.1.2.4. 装饰模式 Decorator
      • 6.1.2.5. 桥接模式 Bridge
      • 6.1.2.6. 组合模式 Composite
      • 6.1.2.7. 享元模式 Flyweight
    • 6.1.3. 行为型模式
      • 6.1.3.1. 模板方法模式 Template Method
      • 6.1.3.2. 观察者模式 Observer
      • 6.1.3.3. 状态模式 State
      • 6.1.3.4. 策略模式 Strategy
      • 6.1.3.5. 职责链模式 Chain of Responsibility
      • 6.1.3.6. 命令模式 Command
      • 6.1.3.7. 访问者模式 Visitor
      • 6.1.3.8. 调停者模式 Mediator
      • 6.1.3.9. 备忘录模式 Memento
      • 6.1.3.10. 迭代器模式 Iterator
      • 6.1.3.11. 解释器模式 Interpreter

1. 数据结构 ​

1.1. 线性表 ​

1.2. 栈与队列 ​

1.2.1. 栈的应用 ​

1.2.1.1. 括号匹配 ​

1.2.1.2. 中缀转后缀 ​

• 操作数直接输出
• 操作符优先级高进栈，优先级低出栈

1.2.2. 矩阵压缩存储 ​

1.2.2.1. 稀疏矩阵 ​

三元组

1.3. 串 ​

1.3.1. KMP算法 ​

$ next[i]=\begin{cases}-1&,i=0\最大前后缀长度&,\text{otherwise}\end{cases} $

$ nextval[i]=\begin{cases}next[i]&,字符不同\nextval[next[i]]&,字符相同\end{cases} $

1.4. 树 ​

$ n-1=\sum\limits_{i=1}^kin_i $

1.4.1. 树和森林 ​

1.4.1.1. 双亲表示法 ​

1.4.1.2. 孩子表示法 ​

1.4.1.3. 孩子兄弟表示法（二叉树） ​

1.4.2. 遍历 ​

1.4.3. 二叉排序树 ​

LL RL LR RR

1.4.4. 赫夫曼树 ​

$ (n-1)\mod (k-1) = 0 $

1.5. 图 ​

1.5.1. 存储 ​

1.5.1.1. 邻接矩阵法 ​

1.5.1.2. 邻接表法 ​

1.5.1.3. 十字链表法（有向图） ​

1.5.1.4. 邻接多重表法（无向图） ​

1.5.2. 图算法 ​

1.5.2.1. 拓扑排序 ​

1.5.2.2. 关键路径 ​

1.6. 查找 ​

1.6.1. 顺序查找、折半查找、分块查找 ​

1.6.2. B树 ​

$ m $阶B树

• 根节点至少$ 2 $个叉
• 非叶节点至少$ floor(\frac m2) $，最多$ m $个叉
• 所有叶节点同层

1.6.2.1. 插入 ​

太多分裂

1.6.2.2. 删除 ​

太少借兄弟，没有还父母

1.6.3. 散列表 ​

1.6.3.1. 散列函数 ​

1.6.3.1.1. 直接定址法 ​

$ H(key)=a\times key+b $

1.6.3.1.2. 除留余数法 ​

$ H(key) = key%p $

1.6.3.1.3. 数字分析法 ​

1.6.3.1.4. 平方取中法 ​

1.6.3.2. 冲突解决 ​

1.6.3.2.1. 开放定址法 ​

$ H_i=(H(key)+d_i)%m $

线性探测法：$ {d_i}={0,1,\cdots,m-1} $

平方探测法：$ {d_i}={0^2,1^2,-1^2,\cdots,k^2,-k^2} $

再散列法：$ d_i=Hash_2(key)\H_i=(H(key)+i\times Hash_2(Key))%m $

伪随机散列法

1.6.3.2.2. 拉链法 ​

1.7. 排序 ​

1.7.1. 内部排序 ​

1.7.2. 外部排序 ​

1.7.2.1. 置换选择排序（生成初始归并段） ​

1.7.2.2. 最佳归并树（赫夫曼树） ​

1.7.2.3. 败者树 ​

总比较次数=(n-1)$ \log_2r $

2. 计算机组成原理 ​

2.1. 概述 ​

2.1.1. 性能指标 ​

2.1.1.1. 机器字长 ​

2.1.1.2. 主存容量 ​

2.1.1.3. 吞吐量 ​

2.1.1.4. 主频 ​

2.1.1.5. CPI ​

2.1.1.6. MIPS ​

2.1.1.7. MFLOPS、GFLOPS、TFLOPS ​

2.2. 运算器 ​

2.2.1. 数据表示 ​

原码、反码：$ 1-2^{n-1}\sim2^{n-1}-1 $

补码、移码：$ -2^{n-1}\sim2^{n-1}-1 $

正数都一样

负数

• 反码：取反
• 补码：取反加一
• 移码：补码符号取反

2.2.2. 浮点数 ​

$ E $：阶码

$ M $：尾数

$ 2 $：底

$ N=2^E\times M $

2.2.2.1. IEEE 754 ​

格式：数符(1)阶码(8)尾数(23)

隐藏尾数最高数位

阶码：移码，$ (0)_{10}=(0111_1111)_2 $

尾数：原码

2.2.2.2. 浮点运算 ​

1. 对阶
2. 尾数求和
3. 规格化
4. 舍入
5. 溢出判断

2.3. 存储器 ​

2.3.1. DRAM刷新 ​

所有芯片同时按行刷新

集中刷新：一个刷新周期内固定时间刷新（死区）

分散刷新：一个存储周期刷新一行（周期变长）

异步刷新：时间间隔$ t $刷新

2.3.2. 高速缓冲存储器(Cache) ​

2.3.2.1. 映射方式 ​

2.3.2.1.1. 直接映射 ​

标记、行号、块内地址

2.3.2.1.2. 全相联映射 ​

标记、块内地址

2.3.2.1.3. 组相联映射 ​

标记、组号、块内地址

2.3.2.2. 标记项 ​

标记、有效位、脏位（可选）、替换控制位（可选）

2.3.2.3. 替换算法 ​

2.3.2.3.1. FIFO ​

2.3.2.3.2. LRU ​

2.3.2.4. 写策略 ​

写命中：

• 写贯穿
• 写回

写不命中：

• 写分配
• 非写分配

2.3.3. TLB ​

2.3.3.1. TLB、Cache、页缺失情况表 ​

2.4. 控制器 ​

2.4.1. 寻址方式 ​

2.4.1.1. 指令寻址 ​

• 顺序寻址
• 相对寻址

2.4.1.2. 数据寻址 ​

• 隐含寻址
• 立即寻址
• 直接寻址$ EA=A $
• 间接寻址$ EA=(A) $
• 寄存器寻址
• 寄存器间接寻址$ EA=(R_i) $
• 变址寻址$ EA=R_i+offset $
• 基址寻址(同上)
• 堆栈寻址

2.4.2. CPU ​

指令周期>>>机器周期>>>时钟周期

2.4.2.1. 指令周期 ​

1. 取值周期
2. 间址周期
3. 执行周期
4. 中断周期

2.4.3. 流水线 ​

2.4.3.1. 性能指标 ​

吞吐率

加速比

效率

2.5. 总线 ​

2.5.1. 分类 ​

片内总线

系统总线：CPU、主存、I/O接口

局部总线：没有CPU

通信总线、设备总线

2.5.1.1. 传输 ​

申请分配阶段>>>寻址阶段>>>传输阶段>>>结束阶段

2.5.1.1.1. 同步定时 ​

统一时钟信号

2.5.1.1.2. 异步定时 ​

• 不互锁
• 半互锁
• 全互锁

2.5.1.2. 标准 ​

2.6. I/O ​

3. 操作系统 ​

3.1. 进程管理 ​

3.1.1. 调度 ​

周转时间=完成时间-提交时间

带权周转时间=周转时间/实际运行时间

平均周转时间$ =\frac1n\sum\limits_{i=1}^nt_i $

平均带权周转时间$ =\frac1n\sum\limits_{i=1}^nt_i $

3.1.1.1. FCFS ​

长进程有利，短进程不利

3.1.1.2. SJF ​

长进程不利，短进程有利

饥饿

3.1.1.3. 优先级调度 ​

3.1.1.4. 高响应比优先 ​

响应比$ R_P=\frac{\text{等待时间} + \text{要求时间}}{\text{要求时间}} $

3.1.1.5. RR ​

3.1.1.6. 多级反馈队列 ​

3.1.2. 互斥同步 ​

3.1.2.1. 生产者消费者 ​

samephore mutex = 1;
samephore empty = n;
samephore full = 0;
Producer{
    while(true){
        produce();
        P(empty);
        P(mutex);
        put();
        V(mutex);
        V(full);
    }
}
Consumer{
    while(1){
        P(full);
        P(mutex);
        get();
        V(mutex);
        V(empty);
        consume();
    }
}
cobegin{
    Producer();
    Consumer();
}

3.1.2.2. 理发师 ​

samephore mutex = 1;
samephore wait = 0;
samephore empty = n;
Customer{
    P(empty);
    V(wait);
    P(mutex);
    V(empty);
    cut();
    V(mutex);
}
Barber{
    while(1){
        P(wait);
        cut();
    }
}

3.1.2.3. 读者写者 ​

int count = 0;
samephore mutex_cnt = 1;
samephore mutex_file = 1;
samephore request = 1;
Reader{
    P(request);
    P(mutex_cnt);
    if(count == 0)
        P(mutex_file);
    count++;
    V(mutex_cnt);
    V(request);
    read();
    P(mutex_cnt);
    if(--count == 0)
        V(mutex_file);
    V(mutex_cnt);
}
Writer{
    P(request);
    P(mutex_file);
    write();
    V(mutex_file);
    V(request);
}

3.1.2.4. 哲学家进餐 ​

samephore chop = 5;
samephore request = 4;
Philosopher{
    while(1){
        think();
        P(request);
        P(chop[i]);
        P(chop[(i + 1) % 5]);
        eat();
        V(request);
        V(chop[i]);
        V(chop[(i + 1) % 5]);
    }
}

3.1.3. 死锁 ​

3.1.3.1. 必要条件 ​

• 互斥
• 不剥夺
• 请求保持
• 循环等待

3.1.3.2. 处理策略 ​

3.1.3.2.1. 死锁预防 ​

破坏必要条件

• 互斥：不能破坏
• 不剥夺：打印机等除外
• 请求保持：静态分配
• 循环等待：按递增序请求

3.1.3.2.2. 死锁避免 ​

避免进入不安全状态

银行家算法

3.1.3.2.3. 死锁检测与解除 ​

资源分配图

死锁定理

3.2. 内存管理 ​

3.2.1. 装入与链接 ​

3.2.1.1. 静态链接 ​

3.2.1.2. 装入链接 ​

3.2.1.3. 运行链接 ​

3.2.1.4. 绝对装入 ​

3.2.1.5. 重定位装入 ​

3.2.1.6. 运行装入（动态重定位） ​

3.2.2. 内存分配 ​

3.2.2.1. 连续分配 ​

3.2.2.1.1. 单一连续分配 ​

3.2.2.1.2. 固定分区分配 ​

3.2.2.1.3. 可变分区分配 ​

3.2.2.1.4. 首次适应 ​

3.2.2.1.5. 最佳适应 ​

3.2.2.1.6. 最差适应 ​

3.2.2.2. 非连续分配 ​

3.2.2.2.1. 基本分页 ​

3.2.2.2.2. 基本分段 ​

3.2.2.2.3. 段页式 ​

3.2.3. 置换算法 ​

3.2.3.1. 最佳置换（OPT） ​

3.2.3.2. 先进先出（FIFO） ​

Belady现象

3.2.3.3. 最近最久未使用（LRU） ​

3.2.3.4. 时钟置换、最近未用（CLOCK、NRU） ​

找$ A=0 $，改$ A=0 $

改进型

1. 找$ A=0,M=0 $
2. 找$ A=0,M=1 $，改$ A=0 $
3. GOTO 1

3.2.4. 分配策略 ​

3.2.4.1. 固定分配局部置换 ​

3.2.4.2. 可变分配局部置换 ​

3.2.4.3. 可变分配全局置换 ​

抖动

工作集

3.2.5. 地址翻译 ​

虚拟地址：虚拟页号+页内偏移/TLB标记+TLB索引+页内偏移

物理地址：物理页号+业内偏移/Cache标记+Cache索引+块内偏移

3.3. 文件管理 ​

3.3.1. 逻辑结构 ​

3.3.1.1. 无结构文件（流式） ​

3.3.1.2. 有结构文件（记录式） ​

• 顺序文件
• 索引文件
• 索引顺序文件
• 散列文件

3.3.2. 目录结构 ​

• 单级目录
• 两级目录
• 多级目录

3.3.3. 文件共享与保护 ​

3.3.3.1. 共享 ​

• 硬链接
• 软链接

3.3.3.2. 保护 ​

访问控制表：每个文件

口令

3.3.4. 文件分配 ​

• 连续分配
• 链接分配
  • 隐式链接（盘块末尾）
  • 显示链接（FAT）
• 索引分配

3.3.5. 空闲管理 ​

• 空闲表法
• 空闲链表法
• 位示图法
• 成组链接法

3.3.6. 磁盘调度 ​

3.3.6.1. 延时 ​

• 移臂时间
• 旋转时间
• 传输时间

3.3.6.2. 调度算法 ​

3.3.6.2.1. FCFS ​

3.3.6.2.2. 最短寻道距离优先 ​

3.3.6.2.3. 扫描（SCAN、电梯调度） ​

到端点转向

3.3.6.2.4. 循环扫描（C-SCAN） ​

单向

3.4. 设备管理 ​

3.4.1. 控制方式 ​

3.4.1.1. 程序查询 ​

3.4.1.2. 中断驱动 ​

3.4.1.3. DMA ​

3.4.1.4. 通道 ​

3.4.2. 层次结构 ​

• 用户层软件
• 设备独立性软件
• 设备驱动软件
• 中断处理程序
• 硬件

3.4.3. 缓冲区 ​

3.4.3.1. 单缓冲 ​

3.4.3.2. 双缓冲 ​

3.4.3.3. 缓冲池 ​

3.4.4. 设备分配与回收 ​

设备控制表（DCT）：表示设备，指向控制器控制表

控制器控制表（COCT）：表示控制器，指向通道控制表

通道控制表（CHCT)：表示通道，指向设备控制器列表

系统设备表（SDT）：一个系统一张，设备控制表列表

逻辑设备表（LUT）：逻辑设备名与物理设备名映射

3.4.5. SPOOLing技术 ​

3.4.5.1. 输入井输出井 ​

模拟脱机磁盘

3.4.5.2. 输入缓冲输出缓冲 ​

内存中

3.4.5.3. 输入进程输出进程 ​

模拟外围控制机

4. 计算机网络 ​

4.1. 网络体系 ​

4.1.1. OSI ​

• 应用层
• 表示层：编码、压缩、加密、解密
• 会话层：建立、管理、终止会话
• 传输层
• 网络层
• 链路层
• 物理层

资源子网：应用、表示、会话

通信子网：网络、链路、物理

4.2. 应用层 ​

4.2.1. DNS ​

根域名服务器：13个

顶级域名服务器

权限域名服务器（授权域名）

本地域名服务器

4.2.2. FTP ​

$ 21 $：控制端口

$ 20 $：数据端口

4.2.3. SMTP、POP3 ​

4.2.4. HTTP ​

4.3. 传输层 ​

4.3.1. 端口号 ​

4.3.2. UDP ​

• 无连接
• $ 8B $头部
• 不可靠
• 不分段

校验和：添伪首部，求和再取反

4.3.3. TCP ​

• 面向连接
• $ 20B $固定头部
• 可靠

4.3.3.1. 建立连接（三次握手） ​

1. SYN
2. SYN, ACK
3. ACK

4.3.3.2. 释放连接（四次挥手） ​

1. FIN
2. ACK
3. ACK, FIN
4. ACK

4.3.3.3. 超时重传 ​

4.3.3.4. 快速重传 ​

4.3.3.5. 流量控制 ​

拥塞窗口：cwnd

接收窗口：rwnd

由接收方告知rwnd

4.3.3.6. 拥塞控制 ​

发送窗口$ =\min{cwnd, rwnd} $

慢开始：乘性增，加性减

拥塞避免：加性增

$ cwnd < ssthresh $：慢开始

$ cwnd \ge ssthresh $：拥塞避免

拥塞的处理

门限减半，窗口重置

sshresh = cwnd / 2

cwnd = 1

快重传的处理

门限减半，窗口同值

sshresh = cwnd / 2

cwnd = sshresh

4.4. 网络层 ​

4.4.1. 拥塞控制 ​

4.4.1.1. 距离-向量路由算法(RIP) ​

• 分布式
• 相邻交换自己路由表
• 每隔$ 30 $秒
• 最多15跳
• 应用层协议，UDP

4.4.1.2. 链路状态路由算法(OSPF) ​

• 所有路由器发送链路状态
• 网络层协议，IP
• Dijkstra

4.4.1.3. 层次路由 ​

内部网关协议：RIP、OSPF

外部网关协议：BGP

• TCP

4.4.2. IPv4 ​

固定头部：$ 20B $

首部长度：$ 4 $位，单位$ 4B $

总长度：$ 16 $位，单位$ 1B $

MF：还有切片

DF：禁止切片

片偏移：$ 13 $位，单位$ 8B $

校验和：只校验头部

TTL：

以太网最大载荷：$ 1500B $

4.4.2.1. 分类IP ​

A：$ 0... $，网络号$ 1..8 $

B：$ 10... $，网络号$ 2..16 $

C：$ 110... $，网络号$ 3..24 $

D：$ 1110... $，多播

E：$ 1111... $，保留

4.4.2.2. 子网划分 ​

4.4.2.3. CIDR ​

4.4.3. 地址解析协议(ARP) ​

$ IP\to MAC $

4.4.4. 动态主机配置协议(DHCP) ​

4.4.5. 网际控制报文协议(ICMP) ​

ping：应用层，直接使用IP

tracert：网络层

4.4.6. IPv6 ​

4.4.7. 组播 ​

MAC：$ 01-00-5E-... $

4.4.8. 路由器 ​

• 输入端口
• 交换结构
• 输出端口

4.5. 链路层 ​

4.5.1. 差错控制 ​

4.5.1.1. 奇偶校验 ​

4.5.1.2. CRC ​

$ r $次多项式$ G(x) $

$ m $位帧

1. 低位补$ r $个$ 0 $
2. 模$ 2 $除法（异或）

4.5.1.3. 海明码 ​

$ n $位信息，$ k $位校验

$ n+k\le2^k-1 $

4.5.2. 流量控制 ​

4.5.2.0.1. 停等协议 ​

$ W_T=1\W_R=1 $

4.5.2.1. GBN ​

$ 1\le W_T\le2^n-1\W_R=1 $

4.5.2.2. SR ​

$ W_R+W_T\le2^n $

一般的，$ W_R\le2^{n-1} $

4.5.3. 介质访问控制（MAC） ​

4.5.3.1. ALOHA ​

4.5.3.2. CSMA ​

4.5.3.3. CSMA/CD ​

以太网：最短帧长$ 64B $，即数据$ 46B $

4.5.3.4. CSMA/CA ​

预约信道

ACK

4.5.3.5. 令牌环 ​

4.6. 物理层 ​

4.6.1. 香农定理 ​

$ W $：带宽

信噪比$=10\log_{10}\frac SN,(dB)$

$ W\log_2(1+\frac SN) $

4.6.2. 奈氏准则 ​

$ W $：带宽

$ V $：每个码元二进制位数

$ 2W\log_2V,b/s $

5. 数据库原理 ​

5.1. 关系代数 ​

5.1.1. $ \sigma_{cond}(tab) $ ​

SELECT *
FROM tab
WHERE cond

5.1.2. $ \pi_{cols}(tab) $ ​

SELECT cols
FROM tab

5.1.3. $ tab_1\times tab_2 $ ​

SELECT *
FROM tab_1, tab_2

5.1.4. $ tab_1 \Join tab_2 $ ​

SELECT *
FROM tab_1
JOIN tab_2

6. 软件工程 ​

6.1. 设计模式 ​

6.1.1. 创建型模式 ​

6.1.1.1. 简单工厂模式 Simple Factory ​

class Product{

};

class ConcreteProductA : public Product{

};

class ConcreteProductB : public Product{

};

class Factory{
public:
    enum ProductKind{
        ProductA,
        ProductB
    };
    Product *createProduct(ProductKind){
        switch(ProductKind){
        case ProductA:
            return new ConcreteProductA();
        case ProductB:
            return new ConcreteProductB();
        }
    }
};

6.1.1.2. 工厂方法模式 Factory Method ​

class Product{

};

class ConcreteProduct : public Product{

};

class Factory{
public:
    virtual Product *factoryMethod() = 0;
};

class ConcreteFactory : public Factory{
public:
    Product *factoryMethod() override{
        return new Product();
    }
};

6.1.1.3. 抽象工厂模式 Abstract Factory ​

class AbstractProductA{

};

class ProductA1 : public AbstractProductA{

};

class ProductA2 : public AbstractProductA{

};

class AbstractProductB{

};

class ProductB1 : public AbstractProductB{

};

class ProductB2 : public AbstractProductB{

};

class AbstractFactory{
public:
    virtual AbstractProductA *createProductA() = 0;
    virtual AbstractProductB *createProductB() = 0;
};

class ConcreteFactory1 : public AbstractFactory{
public:
    AbstractProductA *createProductA() override{
        return new ProductA1();
    }
    AbstractProductB *createProductB() override{
        return new ProductB1();
    }
};

class ConcreteFactory2 : public AbstractFactory{
public:
    AbstractProductA *createProductA() override{
        return new ProductA2();
    }
    AbstractProductB *createProductB() override{
        return new ProductB2();
    }
};

6.1.1.4. 创建者模式 Builder ​

class Product{

};

class Builder{
public:
    virtual void buildPartA() = 0;
    virtual void buildPartB() = 0;
    virtual Product *getProduct() = 0;
};

class ConcreteBuilder : public Builder{
public:
    void buildPartA() override{
        // build part A
    }
    void buildPartB() override{
        // build Part B
    }
    Product *getProduct() override{
        return product;
    }
private:
    Product *product;
};

class Director{
public:
    Product *construct(){
        builder->buildPartA();
        builder->buildPartB();
        return builder->getProduct();
    }
private:
    Builder *builder = new ConcreteBuilder();
};

6.1.1.5. 原型模式 Prototype ​

6.1.1.6. 单例模式 Singleton ​

class Singleton{
public:
    static Singleton *getInstance(){
        if(instantce == nullptr){
            instantce = new Singleton();
        }
        return instantce;
    }
private:
    static Singleton *instantce = nullptr;
};

6.1.2. 结构型模式 ​

6.1.2.1. 外观模式 Facade ​

6.1.2.2. 适配器模式 Adapter ​

class Adaptee{
public:
    void specificRequest(){
        // specific request
    }
};

class Target{
public:
    virtual void request() = 0;
};

class Adapter : public Target{
public:
    void request() override{
        adaptee->specificRequest();
    }
private:
    Adaptee *adaptee;
}

class Adaptee{
public:
    void specificRequest(){
        // specific request
    }
};

class Target{
public:
    virtual void request() = 0;
};

class Adapter : public Target, public Adaptee{
public:
    void request() override{
        specificRequest();
    }
};

6.1.2.3. 代理模式 Proxy ​

6.1.2.4. 装饰模式 Decorator ​

6.1.2.5. 桥接模式 Bridge ​

class Implementor{
public:
    virtual void operationImpl() = 0;
}

class ConcreteImplementor : public Implementor{
public:
    void operationImpl() override{
        // operation implement
    }
};

class Abstraction{
public:
    virtual void operation(){
        impl->operationImpl();
    }
private:
    Implementor *impl;
};

class RefinedAbstraction : public Abstraction{

};

6.1.2.6. 组合模式 Composite ​

6.1.2.7. 享元模式 Flyweight ​

6.1.3. 行为型模式 ​

6.1.3.1. 模板方法模式 Template Method ​

6.1.3.2. 观察者模式 Observer ​

6.1.3.3. 状态模式 State ​

6.1.3.4. 策略模式 Strategy ​

6.1.3.5. 职责链模式 Chain of Responsibility ​

6.1.3.6. 命令模式 Command ​

6.1.3.7. 访问者模式 Visitor ​

6.1.3.8. 调停者模式 Mediator ​

6.1.3.9. 备忘录模式 Memento ​

6.1.3.10. 迭代器模式 Iterator ​

6.1.3.11. 解释器模式 Interpreter ​