408
数据结构
1 线性表
2 栈、队列和数组
3 串
4 树
树 ### 二叉树 满二叉树 完全二叉树 二叉排序树 平衡二叉树 线索二叉树 哈夫曼树 森林 并查集 #### 性质 #### 存储结构 顺序存储 链式存储 #### 遍历
5 图
6 查找
7 排序
计算机组成原理
1 数据的表示和运算
2 存储系统
3 指令系统
4 中央处理器
5 总线
6 输入输出系统
操作系统
1 进程与线程
2 内存管理
\(2^3=1B=8bit\) \(2^{10}=1K\) \(2^{20}=1M=2^{10}K\) \(2^{30}=1G=2^{10}M\)
虚拟内存
置换算法
缺页率=缺页次数/访问次数
最佳置换算法 OPT
最后再访问的先淘汰
先进先出置换算法 FIFO
最先放内存的先淘汰 Belady 异常：当为进程分配的物理块增大时，缺页次数不减反增的现象。
最近最久未使用置换算法 LRU
最近没访问的先淘汰
时钟置换算法 CLOCK
改进型时钟置换算法
3 文件管理
4 输入输出（I/O）管理
计算机网络
1 计算机网络体系结构
1.1 概述
1.1.1 概念
1.1.1.1 计算机网络是互联的、自治的计算机集合。
1.1.2 组成
1.1.2.1 从组成部分
- 4.2.2.1.1. 软件
- 4.2.2.1.2. 硬件
- 4.2.2.1.3. 协议
1.1.2.2 从工作方式
- 4.2.2.2.1. 边缘部分
- 4.2.2.2.2. 核心部分
1.1.2.3 从功能组成
- 4.2.2.3.1. 通信子网
- 4.2.2.3.2. 资源子网
1.1.3 功能
1.1.3.1 数据通信
1.1.3.2 资源共享
1.1.3.3 分布式处理
1.1.3.4 提高可靠性
1.1.3.5 负载均衡
1.1.4 分类
1.1.4.1 按分布范围
- 4.2.4.1.1. WAN 广域网
- 4.2.4.1.2. MAN 城域网
- 4.2.4.1.3. LAN 局域网
- 4.2.4.1.4. PAN 个人区域网
1.1.4.2 按传输技术
- 4.2.4.2.1. 广播式网络
- 4.2.4.2.2. 点对点式网络
1.1.4.3 按拓扑结构
- 4.2.4.3.1. 总线型
- 4.2.4.3.2. 星型
- 4.2.4.3.3. 环型
- 4.2.4.3.4. 网状型
1.1.4.4 按交换技术
- 4.2.4.4.1. 电路交换网络
- 4.2.4.4.2. 报文交换网络
- 4.2.4.4.3. 分组交换网络
1.1.4.5 按使用者
- 4.2.4.5.1. 公用网
- 4.2.4.5.2. 专用网
1.1.4.6 按传输介质
- 4.2.4.6.1. 有线网络
- 4.2.4.6.2. 无线网络
1.1.5 标准化
1.1.5.1 分类
- 4.2.5.1.1. 法定标准
- 4.2.5.1.2. 事实标准
1.1.5.2 组织
- 4.2.5.2.1. IETF 互联网工程任务组
- 4.2.5.2.2. RFC 征求意见稿
- 4.2.5.2.3. ISO 国际标准化组织联盟
- 4.2.5.2.4. ITU 国际电信联盟
- 4.2.5.2.5. IEEE 国际电气电子工程师协会
1.1.6 性能指标
1.1.6.1 速率（数据率、数据传输率、比特率）
- 4.2.6.1.1. 2.6.1.1.
- 2.6.1.1.1. 连接在计算机网络上的主机在数字信道上传送数据位数的速率
- 4.2.6.1.2. 单位
- \(b/s\)
- \(kb/s=10^3b/s\)
- \(Mb/s=10^3kb/s=10^6b/s\)
- \(Gb/s=10^3Mb/s=10^6kb/s=10^9b/s\)
- \(Tb/s=10^3Gb/s=10^6Mb/s=10^9kb/s=10^{12}b/s\)
1.1.6.2 带宽
- 4.2.6.2.1. 网络设备支持的最高速率
1.1.6.3 吞吐量
- 4.2.6.3.1. 表示单位时间内通过某个网络（或信道、接口）的数据量。
- 4.2.6.3.2. 受网络带宽和网络的额定速率的限制。
1.1.6.4 时延
- 4.2.6.4.1. 2.6.4.1.
- 2.6.4.1.1. 数据（报文/分组/比特流）从网络（或链路）的一段传送到另一端所需要的时间。
- 2.6.4.1.2. 单位 s
- 2.6.4.1.3. 总时延=发送时延+传播时延+处理时延+排队时延
- 4.2.6.4.2. 发送时延
- 2.6.4.2.1. \(发送时延=\frac{数据长度}{信道带宽}\)
- 4.2.6.4.3. 传播时延
- 2.6.4.3.1. \(传播时延=\frac{信道长度}{电磁波在信道上的传播速率}\)
- 4.2.6.4.4. 排队时延
- 4.2.6.4.5. 处理时延
1.1.6.5 时延带宽积
- 4.2.6.5.1. 发送端发送的第一个bit即将到达终点时，发送端已经发出了多少个bit
- 4.2.6.5.2. 单位 bit
- 4.2.6.5.3. \(时延带宽积=传播时延\times带宽\)
1.1.6.6 往返时延RTT
- 4.2.6.6.1. 从发送方发送数据开始，到发送方收到接收方的确认，总共经历的时延
- 4.2.6.6.2. \(往返传播时延=传播时延\times2\)
- 4.2.6.6.3. \(RTT=末端处理时间+传播时延\times2\)
1.1.6.7 信道利用率
- 4.2.6.7.1. \(信道利用率=\frac{有数据通过时间}{(有+无)数据通过时间}\)
1.2 体系结构和参考模型
1.2.1 分层结构
1.2.1.1 为什么分层
1.2.1.2 怎么分层
- 4.2.8.2.1. 协议
- 4.2.8.2.2. 服务
- 4.2.8.2.3. 接口
1.2.2 OSI 参考模型（7层）
1.2.2.1 通信子网
- 4.2.9.1.1. 物理层
- 4.2.9.1.2. 数据链路层
- 4.2.9.1.3. 网络层
1.2.2.2 传输层
1.2.2.3 资源子网
- 4.2.9.3.1. 会话层
- 4.2.9.3.2. 表示层
- 4.2.9.3.3. 应用层