2018
1. 完全二叉树结点分析
设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是_。
结点总数 = 边数 + 1 = 各节点度数之和
法一：画图法
非叶结点的度均为 2，且所有叶结点都位于同一层的完全二叉树就是满二叉树。对于一棵高度为h的满二叉树（空树h=0），其最后一层全部是叶结点，数量为2^h；总结点数为2^h - 1。因此当2^h-1 = k 时，可以得到2^h - 1 = 2k - 1。
2. B树关键字个数分析
高度为5的3阶B树含有的关键字个数至少是
3阶b树的关键字书 = [1,2]
每个结点的关键字都为1可以达到最少的情况，形成高度为5的满二叉树，2^5 - 1 = 31
3. 平均查找长度
现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字 22，43，15依次插入到 HT后，查找成功的平均查找长度是
22%7 =1 、43%7 = 1、15%7 = 1
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 22 | 43 | 15 |
查找22 查找1次、查找43 查找2次、查找15 查找3次
平均查找长度 = 1 + 2 + 3 / 3 = 2
4. IEEE最小规格化正数
IEEE最小规格化正数 = 1.0 * 2^-126
最大 = 1.1111111(23个1) *2^127= (2-2^-23) x 2^127 = 2^128 - 2^104
5. 小端存储
-64 表示成 32 位的十六进制数是FFFFFF CO, 根据小端方式的特点，高字节存储在低地址， 就是CO FF FF FF
6. 变址寻址（数组）
按字节编址的计算机中，某double 型数组A的首地址为2000H，使用变址寻址和循环结构访问数组 A，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地址为变址值乘以 sizeof（double），取完后变址寄存器内容自动加 1。若某次循环所取元素的地址为2100H，则进入该次循环时变址寄存器的内容是。
double 64位 = 8字节
2100H = 2000H + sizeof(double) * k
k = 256 / 8 = 32
7. CF&OF
减法指令 “sub RI, R2, R3” 的功能为“（RI） -（R2）-> R3”，该指令执行后将生成进位/借位标志 CF 和溢出标志OF。若（R1） =FFFF FFFFH，（R2） = FFFF FFFOH，则该减法指令执行后，CF 与 OF分别为_。
R2补码 = 0000 0010H R1 - R2 = R1 + R2补码 = FFFF FFFF + 0000 0010 =
最高位进位=1，次高位进位=1，sub = 1
CF = 最高位进位 异或 次高位进位 = 0
OF = 最高位进位 异或 sub = 0
异或 => 同0异1
8. 平均周转时间(‼️)
周转时间：指从作业被提交给系统开始，到作业完成为之的这段时间间隔称为作业周转时间。
包括四个时间：作业在外存后备队列上等待调度的时间，进程在就绪队列上等待进程调度的时间，进程在 CPU 上执行的时间，以及进程等待 I/O 操作完成的时间。
带权周转时间：作业的周转时间 T 与系统为它提供服务的时间 Ts 之比
某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为 1us。在t时刻就绪队列中有3个进程P1、P2和 P3，其在就绪队列中的等待时间、需要的 CPU 时间和优先权如下表所示。
| 进程 | 等待时间 | 需要的 CPU 时间 | 优先权 |
|---|---|---|---|
| P1 | 30us | 12us | 10 |
| P2 | 15us | 24us | 30 |
| P3 | 18us | 36us | 20 |
为若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，系统的平均周转时间
优先级: p2 > p3 > p1
p2: 1us调度 + 15us等待 + 24us执行 = 40us
p3: 1usp2调度 + 24usp2执行 + 1us调度 + 18us等待 + 36us执行 = 80us
p1: 1usp2调度 + 24usp2执行 + 1usp3调度 + 36usp3执行 + 1us调度 + 30us等待 + 12us执行 = 105us
平均周转时间 = (40 + 80 + 105) / 3 = 75us
9. 时钟中断服务程序
时钟中断的主要工作是处理和时间有关的信息以及决定是否执行调度程序，和时间有关的所有信息，包括系统时间、进程的时间片、延时、使用CPU的时间、各种定时器。
10. 磁臂黏着(磁盘调度算法)
磁臂黏着：系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求
当系统总是持续出现某个磁道的访问请求时， 均持续满足最短寻道时间优先、 扫描算法和循环扫描算法的访问条件，会 一直服务该访问请求。因此，先来先服务按照请求次序进行调度， 比较公平。
11. 让权等待
**让权等待：**即当进程不能进入临界区时， 应立即释放处理器， 防止进程忙等待
只有信号量才能实现让权等待
12. CSMA/CA预约信道
所有站完成发送后，必须等待一段很短的时间(继续监听)才能发送下一帧。这段时间称为帧间间隔(InterFrameSpace,IFS)。帧间间隔的长短取决于该站要发送的帧的类型。802.11标准使用了下列三种IFS。
1️⃣ SIFS(短IFS):最短的IFS，用来分隔属于一次对话的各帧，使用SIFS的帧类型有ACK帧、CTS帧、分片后的数据帧，以及所有回答AP探询的帧等。
2️⃣ PIFS(点协调IFS):中等长度的IFS，在PCF操作中使用。
3️⃣ DIFS(分布式协调IFS):最长的IFS，用于异步帧竞争访问的时延。
CSMA/CA协议进行信道预约的方法：
源站要发送数据帧之前，先监听信道，若信道空闲，则等待时间DIFS后，广播一个请求发送**RTS(RequestToSend)**控制帧，它包括源地址、目的地址和这次通信所需的持续时间。
若AP正确收到RTS帧，且信道空闲，则等待时间SIFS后，向源站发送一个允许发CTS(ClearToSend)控制帧，它也包括这次通信所需的持续时间，源站收到CTS帧后，再等待时间SIFS，就可发送数据帧。