10年 平衡二叉树的调整 LL调整 RR调整 RL调整 例如（原谅我图画的难看😂）：
LR调整 二分查找的次数（成功失败）、折半查找判定树与二叉搜索树的关系 平衡二叉树是一种特殊的二叉查找树，它要求任何节点的两棵子树的高度差不超过1（同一棵树的不同节点的子树高度差可以为1、0、-1）。平衡二叉树通过在插入和删除节点时做旋转来维持树的平衡。
折半查找判定树是一种特殊的平衡二叉树，它要求更加严格。同一棵树节点的左子树和右子树的差不能同时存在1和-1（即为统一向上取整或统一向下取整）。查找时，根据比较的结果折半排除一边的树。折半查找判定树中，只有最下面一层才可以不满。 根据完全二叉树的高度计算公式，元素个数为n时，树高 $h=\lceil log_2(n+1)\rceil$ 或 $h=\lfloor log_2(n)\rfloor+1$ 。在折半查找中，
查找成功的最小比较次数为1，最大比较次数为$h$； 查找失败的最小比较次数为：若$n=2^h-1$，则为$h$，否则为$h-1$，最大比较次数：$h$。 数据类型转换造成的精度丢失等问题 将高精度数转换为低精度数可能会引起：
精度丢失：高精度数通常能够表示更大范围和更高精度的数字，但当将其转换为低精度数时，可能会导致小数部分被截断或丢失，从而引起精度丧失。 溢出：如果高精度数的值超出了低精度数所能表示的范围，会导致溢出。 将整型数转换为浮点数一般不会出现问题，但特殊情况下会导致精度丢失，对于非常大或非常小的整数，可能无法精确表示。如int类型数据二进制表示有32位，但是对于float类型，在IEEE 754格式下，尾数部分只有23位，可能无法完全表示某一个int类型数，造成精度的丢失。 单精度与双精度浮点数的运算也有可能会有一些问题，例如10年真题$T_{14}$，$f=1.5678e3,d=1.5e100$，进行$(d+f)-d$运算，在$d+f$时，需要先进行对阶（小阶向大阶对齐），由于格式中的尾数限制，对阶后，$f$的尾数被舍去而变成了0，故$d+f$仍然为$d$，再减去$d$结果为0，而不是$f$。
字扩展、位扩展与相关的芯片最低地址问题 位扩展
位扩展是指用若干片位数较少的存储器芯片构成给定字长的存储器，容量改变，位数改变，地址单元个数不变。
在袁春风老师的《计算机系统基础》中的一个例子如下：
注意到8个$16M\times8bit$的芯片扩展构成一个128M内存条。在进行扩展之前，对于单个芯片，地址位数为24bit。即地址单元个数为$16M=2^{24}$ 。每个地址单元存储8bit。
在进行扩展之后，$128M=2^{27}$，而行列地址位数加起来一共$24bit$，$2^{24}=16M$，则说明此次扩展为位扩展。一个地址单元中的数据位数增加，但是总的地址单元个数并未改变。
12位行地址$i$和12位列地址$j$分别送到DRAM芯片内部的行地址译码器和列地址译码器，选择行列地址交叉点$(i,j)$的8位数据同时进行读写，8个芯片就可以同时读取64bit，组合成总线所需要的64位传输宽度，再通过存储器总线进行传输。
字扩展
字扩展，容量改变，地址单元个数改变，即地址位数会改变，位数不会改变。
另外，对于某一存储器，由多个DRAM经过字扩展而成，那么对于单个DRAM芯片来说，其行地址RAS位数、列地址CAS位数也不会变，但是整体存储器的总地址位数会变，会增加片选信号位数。 此时，对于一个主存地址，可以理解为芯片序号+芯片内的位置 。 也就是说，无论是位扩展还是字扩展，对于单一的DRAM芯片，其行列地址位数均不含会改变。（14年T15）
引起进程状态改变的一些典型事件 进程状态可以在以下情况下发生改变：
创建新进程：当操作系统启动一个新的程序时，会创建一个新的进程，并将其状态设置为就绪状态。
进程等待：当一个进程等待某些事件发生，例如等待用户输入、等待某个文件就绪等，它的状态会从运行状态变为阻塞状态。
时间片用完：如果一个进程在分配给它的时间片用完之后，调度器会将其状态从运行状态变为就绪状态，降低其进程优先级，然后选择下一个要执行的进程。
I/O操作完成：当一个进程等待的I/O操作完成后，它的状态会从阻塞状态变为就绪状态。
进程终止：当一个进程完成了它的任务，或者由于某种原因需要被终止，它的状态会从运行状态变为终止状态。
进程被阻塞的资源可用：当一个进程等待的资源（如锁或信号量）变为可用时，它的状态会从阻塞状态变为就绪状态。设备分配是在一个已经存在的进程中进行的，不会导致创建新进程。
进程被唤醒：在多任务环境中，一个进程可能会被另一个进程唤醒，使得它从阻塞状态变为就绪状态。
进程被挂起或恢复：操作系统可以将一个进程从内存中挂起（暂时移出内存）或者从挂起状态恢复（重新加载到内存中）。
父进程等待子进程：当一个父进程等待其子进程结束时，它的状态可能会从运行状态变为阻塞状态。
发生错误或异常：当一个进程遇到错误或异常情况时，它的状态可能会从运行状态变为终止状态或者阻塞状态（如果它在等待某些事件发生时发生了错误）。
IO系统的分层结构 碰撞域、广播域 冲突域：在同一个冲突域中，每一个结点都能收到所有其他结点发送的帧。简单地说，冲突域为同一时间内只能有一台设备发送信息的范围。 广播域：网络中能接收任意设备发出的广播帧的所有设备的集合。即，如果站点发出一个广播信号，所有能接收到这个信号的设备范围被称为一个广播域。 通常一个网段为一个冲突域，一个局域网为一个广播域。
磁盘的调度策略 磁盘调度算法是操作系统中用于管理磁盘上的I/O请求的一种策略。以下是一些常见的磁盘调度算法：
先来先服务（FCFS）：最简单的磁盘调度算法，按照请求的到达顺序依次执行。但可能会出现“早来的请求等待时间长”的问题。 最短寻道时间优先（SSTF）：选择当前磁头位置最近的请求进行服务，以最小化寻道时间。但可能会导致某些请求长时间等待。 SCAN算法：扫描算法，也称为电梯算法，类似于电梯的运行方式，磁头按一个方向移动，直到最后一个磁道后再改变方向。 C-SCAN算法：循环扫描算法，磁头按同一个方向移动，直到到达最后一个磁道后，立即直接返回到磁道0处，再继续扫描。 LOOK 算法：类似于扫描算法，但在到达最远的请求后不会立即返回，而是根据当前请求的方向决定下一个服务的磁道。在朝一个给定方向移动前查看是否有请求。 C-LOOK 算法：类似于 C-SCAN 算法，但在到达最远的请求后不会立即返回，而是直接返回到最远端的有请求的磁道。 注意，在做题时，若无特别说明，也可以默认SCAN算法和C-SCAN算法为LOOK和C-LOOK调度。...