# 数据结构

# 查找算法

1. 二叉查找树的查找时间复杂度是: $O(log_n)$。

2. 二叉排序树插入和删除元素不需要调整。

   与 AVL 数相比 BST 不需要进行自调整，这也是为什么会有 AVL 的一个主要原因

# 排序算法

1. 稳定排序算法有: 冒泡排序，插入排序，基数排序，归并排序。

2. 算法复杂度与初始状态无关的有: 选择排序，堆排序，归并排序，基数排序。

3. 元素总比较次数与初始状态无关的有: 选择排序，希尔排序，归并排序，基数排序。

4. 元素总移动次数与初始状态无关的有: 归并排序，基数排序。

5. 每趟必有一个元素到达目的地: 冒泡排序，选择排序，插入排序，堆排序。

6. 不到最后一刻不会有序: 快速排序，希尔排序，归并排序。

7. 快速排序在找到比基准大的元素或找到比基准小的元素会与基准元素分别交换位置。

   无论基准大还是比基准小时，都直接赋值到基准所在位置实现交换.
   遇到 给定 基准，求一趟之后题目直接模拟

# 组成原理

# 中断

1. 中断隐指令需要保存通用寄存器 {.gap}。

   中断隐指令：保存源程序的 PC 值，并让 PC 指向中断服务程序的第一条指令
   通用寄存器由操作系统进行保存
   相关参数由用户自行传入和保存

2. 中断服务程序的执行流程是: 保存现场，处理中断，恢复现场。

   保护现场：保存通用寄存器，栈指针，程序计数器，可以存在堆栈中
   处理中断：完成中断需要做的事情
   回复现场：恢复通用寄存器，栈指针，程序计数器，程序继续运行

3. 中断服务程序是由硬件完成的 {.gap}。

   只有中断隐指令才由硬件执行
   需要区分 OS 和 硬件 各自负责的部分

# 存储系统 (Cache)

1. 全相联是指主存块可以随意存储在 Cache 中。

   全相联：所有主存块都可以存储在 Cache 中，无需进行地址转换
   直接映射：只能存储在指定位置的 Cache 中
   组相联: Cache 被分为多个组，每个组中存储相同的块，每个组中的块数称为路，地址 mod 组确定存储在哪个组，组内随意存储

2. 高位交叉编址不仅可以扩容还可以提升。

   高位交叉编址：体号在高地址，会进行译码，轮流访问各个存储器，本质上还是串行，但是提升了空间
   低位交叉编制：体号在低地址，地址模存储体数量，可以使各个存储体并行访问，可以提升速率

3. 高速缓存的作用是: 减少主存访问次数，提高系统性能。

4. 影响 Cache 命中的因素有: 块大小，块数目，置换算法，缓存一致性策略，数据和指令局部性。

   Cache 越大，命中率越高
   Cache 存储体组织结构：直接映射，组相联，全相联
   置换算法：最佳置换算法，先进先出，最近最久未使用，时钟置换算法，随机置换算法，空间置换算法
   缓存一致性策略：写策略

# 操作系统

# 死锁

1. 死锁产生的必要条件是: 互斥，持有并等待，不可抢占，循环等待。

2. 死锁处理基本思想是: 预防，避免，检测和恢复。

3. 死锁预防的策略有: 破坏互斥，破坏不剥夺，破坏请求保持，破坏循环等待。

4. 死锁避免的策略有: 银行家算法。

5. 死锁检测会进行资源剥夺。

   死锁解除方法有三种：资源剥夺法，进程回退法，撤销进程法.
   这三种方法都需要对资源进行剥夺

6. 银行家算法的目标是实现系统安全状态。

   银行家算法是一种死锁预防算法，它通过破坏互斥条件和请求保持条件来避免死锁的发生.

7. 死锁避免预防和检测的折中方案，不需要进行剥夺。

   死锁避免通过找到安全序列，避免系统进入不安全状态.
   无需进行资源剥夺

8. 死锁检测的基本思想是: 监视资源分配图。

   用于检测死锁的资源分配图，它是一种图形表示法，用来表示系统中资源的分配情况.
   它包括进程，资源，资源请求，资源分配，资源回收，进程阻塞，进程唤醒等信息.
   死锁检测算法通过监视资源分配图，发现资源分配图中存在环路，即存在死锁.
   死锁检测算法的基本思想是：系统中存在环路，则说明存在死锁.
   死锁定理：资源分配图不可化简，则系统中存在死锁

9. 死锁恢复的基本思想是: 资源剥夺法，撤销进程法，进程回退法。

   资源剥夺法：进程选择剥夺资源，直到释放足够资源为止.
   撤销进程法：进程选择终止，直到释放足够资源为止.
   进程回退法：进程选择回退，直到释放足够资源为止.

# 计算机网络

1. 网络层的主要功能是: 数据报传输，路由选择，数据包分组，差错控制。

2. TTL 值为 0 表示路由器不再转发数据包。

   TTL: 存活时间，路由器每转发数据包，TTL 值减 1, 当 TTL 值为 0 时，数据包丢弃

3. 网络层的协议有: IP, ICMP, ARP, RARP, OSPF, IGMP。

4. 直接交换是指: 不经过路由器直接将数据包发送给目的主机。

   源主机和目的主机必须处于同一子网内，即它们的 IP 地址具有相同的网络部分，这通常是通过子网掩码来判断的
   源主机通过 ARP（地址解析协议）获取目的主机的 MAC 地址（物理地址），然后将数据包直接发送到这个 MAC 地址。

5. 间接交换是指: 数据包必须通过一个或多个路由器来转发。

   源主机和目的主机位于不同的网络或子网

6. IP 报文在传输过程中不会改变的是: 源 IP 地址，目的 IP 地址，协议地址。

7. Ping 命令使用的协议是: ICMP。

   Ping 命令是 ICMP 协议的应用，它是一种用于测试网络连接的工具.
   Ping 命令发送 ICMP Echo Request 报文，并等待 ICMP Echo Reply 报文的返回.
   如果 Ping 命令在指定的时间内没有收到 ICMP Echo Reply 报文，则会显示超时信息.

8. ICMP 的功能有: 差错控制，路由选择，网络管理。

   ICMP 的主要功能是差错控制，它用于处理网络中出现的差错，如网络分组丢失，数据包重排序，数据包损坏等.
   ICMP 的另一个功能是路由选择，它用于选择数据包的最佳路径.
   ICMP 的第三个功能是网络管理，它用于诊断网络的状态，如网络连接，路由表，网卡故障等.

大道五十，天衍四十九，人遁其一！