408知识内容

22 Nov 2020 15436字 52分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

计算机组成原理

  1. 浮点数的加减，对阶，溢出问题

    浮点数：阶符，阶码 数符，尾数。

    规格化的浮点数：

    • 定义：充分利用尾数的有效位数，即规定最高位数位是一个有效值。要保证 $ 尾数 \ge \frac{1}{r} $, 其中 r 是基数。机器零的含义是指约等于 0。
    • 左规：尾数算术左移，即小数点不动，尾数左移，直观上数变大了，阶码就要减小。
    • 右规：尾数算术右移（一般是尾数溢出时，需要进行操作），即小数点不动，尾数右移，直观上数变小了，阶码就要增加。
    • 无论补码还是原码表示尾数，规格化后符号位和最高位必定不同。
    • 上溢出：往负无穷或正无穷方向
    • 下溢出：往0方向。

    754标准:

    1,8,23, 127。1-254

    1,11,52, 1023

    1, 15, 64, 80, 16383

  2. 主存，Cache 的映射，以及回写（Write Back) 和直写（Write Through) 方式

    Cache: 按数据块和主存交换数据，存的是实实在在的数据；

    Cache 一行一行划分，每一行里面的数据的长度称为行长；

    Cache 组成：

    • 有效位
      • 还可能有脏位（比如使用写回法的时候），替换控制位
    • 标记号
    • 数据
    $ 有效位，脏位，替换控制位 标记号 数据块 $

    映射方式：

    • 直接映射：内存中每一块只能装入 Cache 中唯一位置，采用字节低位决定放到某一行；空间利用率最低；
    • 全相联：Cache 每个位置直接和对应的存储器位置用线连起来，然后需要顺序进行比较；
    • 组相联：m 路组相联，是说每组有 m 个行。组内采用全相联映射。

    写策略：

    • 写命中时：
      • 全写法：write through, 即写缓存的时候，也写回内存；
      • 写回法：write back, 即只写缓存，被换出时再写回内存，需设置脏位，即表示该数据是否被CPU修改过；
    • 写未命中时：
      • 写分配法：加载主存中块至缓存，然后更新缓存。所以这种方法和写回法配合使用；
      • 非写分配法：直接更新内存，不对缓存做调块处理。配合全写法使用。（靠读操作把该块调入缓存）

  3. 存储器交叉编址

    属于双端口、多模块的内容。

    双端口：

    • 多个CPU访问同一个RAM, 考虑冲突：写冲突，读写冲突，读读不冲突，前提是访问地址相同。

    多模块：

    • 主要思想：同时从存储器中取出 n 条指令。

    • 单体多字，一个地址存多条指令。只有一个存储体。

    • 多体交叉，多个存储体。

      • 高位交叉：本质就是多个存储体并成一个存储体而已，就是高地址选中一个存储体，然后低位地址表示在选中的存储体内的地址，就是一个顺序的存储体；

        纠正认识：高位交叉也是一次从多个存储体里面取，比如遇到这样一种情况，需要访问连续 n 个间隔恰好为一个存储体的大小的地址，那么这个时候高位交叉就派上用场了。它没有空间局部性！

      • 低位交叉：就是低位用来选中存储器，（交叉的含义，大概就是低位上连线连到所有存储体上，所以就交叉了吧），高位用来表示存储体内地址。其实也是顺序，不过就是存储器按行来连续了。即 addr % m 的值来选中，可以使得连续地址分布在不同存储器上，可以进行流水线访问。

        模块存取一个字的周期为 T, 总线传输周期为 r，则为了实现流水线方式，存储器的个数 m >= T/r。

        总线周期 r 就是，存储体占用总线传送数据的时间，这个表达式的意思就是说，当第一个存储器没有被存取完之前，需要有足够的存储体来接受 CPU 发出的地址访问，可以类比计算机网络里面的滑动窗口协议。

  4. TLB 方式，就是逻辑地址映射这一块要重点掌握：要做到计算快，且准确。

  5. 补码和原码数值对应关系：

    M 为一个补码，二进制形式为 101111……01；怎么快速求出其对应的 10 进制值呢？如果是正数直接求，但是如果是负数呢？

    用最高位符号位当作数值，$\sum_{i=0}^{n-2}a_i2^i - signed * 2^{n-1}$, n 位的补码.

    补码和移码关系：符号位取反即完成转换。

    补码的符号位显然是要参与运算的。

  6. MAR寄存器的位数：是由主存空间大小相对应的，换句话说，应该是MAR寄存器的位数决定了主存空间最大大小，它的位数与实际内存大小无关！！

  7. 总线：

    系统总线的结构：

    • 单总线结构：

      • 单总线结构将 CPU, 主存，I/O 设备都挂在一组总线上，允许 I/O 设备之间、I/O 设备与主存之间直接交换信息。就是相当于所有设备连接一组线上，那么一个所有设备都只能互斥的使用总线。
      • 成本低，易于接入新设备

    • 双总线结构：

      • 以 CPU 为中心：一条是主存总线，CPU和主存，以及通道之间传数据；另一条是 I/O 总线，用于设备和通道之间传数据；

    • 三总线结构：

      以存储器为中心：

      • 主存总线：CPU 和存储器之间
      • I/O 总线（系统总线）：CPU和各种外设之间通信
      • 存储总线（DMA总线）：设备和主存之间。

    计算机是时钟频率由两种：内频率和外频率。内频率是与CPU相关的频率，外频率是I/O等控制器的总线频率等等。而且，一般内频率是外频率的整数倍。另外，个人基本认为：时钟周期（时钟频率的倒数）是最小的节拍单位。另外无论啥周期都是时钟周期的整数倍。另外，需要明白 CPU 的时钟周期基本指得是时钟周期，换句话说，时钟周期就是指 CPU 的时钟周期，内频率基本就是指主频。这和CPU的指令周期有啥区别？

    • 指令周期应该是时钟周期的整数倍；即执行一条指令所需的总时间，为时钟周期的整数倍；

    总线的标准：

    • PCI 总线标准：与 CPU 时钟频率无关；即插即用；采用猝发传送方式；扩展性好，可以采用多级 PCI 总线，竟然是一种并行总线标准？？

  8. SPOOLing 技术

    假脱机技术。以空间换时间的技术。

    输入数据通过内存的输入缓冲区然后送到输入井；然后CPU处理输入的数据，直接从输入井内取数据，处理完毕又送到磁盘上的输出井里。然后外围设备需要数据时，从输出井上读数据到输出缓冲区，然后送到外围设备上。

  9. 中断

    中断的过程：中断分内中断和外中断。

    几个基本的概念：

    • 中断服务程序：就是为啥要中断啊，中断的目的就是去执行别的程序，那个别的程序就是中断服务程序。

    • 中断向量：就是指 $cs,ip$ 构成的一个数据，它的数据指示的是欲执行的程序的起始地址，这个欲执行的程序就是中断服务程序，这个起始地址也称中断服务程序入口地址。
    • 中断向量的地址：即指向中断向量；
    • 中断服务程序的入口地址：即中断向量保存的内容，见上两条。

    中断是怎么产生的呢？整个过程是怎样？

    先说外中断：

    • 首先，我们知道 CPU 的指令执行的周期中，有一个中断周期，在中断周期，CPU会检查是否有中断信号产生（以x86处理器为例，处理器会检查来自 NMI 线(不可屏蔽中断)和 INTR（可屏蔽中断）线上的信号），并且结合位于CPU内部的 FLAGS 寄存器中 IF 标志位的状态值是否为 1 来判断是否响应中断（当然，非屏蔽中断上的信号若产生，则需要响应，不受 IF 的影响），若响应，首先保存当前程序的地址（即 cs,ip，也就是PC的内容），然后这个时候 CPU 结合中断的类型号（这个信息的获取估计是靠传过来的 INTR 或 NMI 线上的信息来的？当然，貌似是通过一种称为 8259A 的芯片，该芯片上会记录中断源产生的中断的各种信息？这里，不太清楚，所以只是猜想……）得到中断向量的地址，然后从中断向量里面取出中断服务程序的入口地址，跳转至它进行执行。

      然后具体谈谈这个过程做了哪些事情：

      • 中断隐指令的过程：保存当前程序的 PC（一般是保存在栈上），同时需要保存 PSW寄存器（emmmm, 貌似实际的 x86 处理器中，对应的汇编中这个寄存器是叫 FLAGS 寄存器的，也叫标志寄存器，因为 PSW 叫程序状态字貌似在操作系统里面可以指代一个程序的状态字，是指一个程序所有的通用寄存器的组合，反正感觉怪怪的，好像每本书说法不一……），然后寻找到中断向量，并取出里面的内容，即中断服务程序的入口地址，并跳转之 (jmp)。
      • 中断服务程序：现在到了中断服务程序，
        • 首先，保护现场（是保存上一个程序，即被中断的那个程序的现场信息，比如通用寄存器组的信息，一般保存至进程控制块PCB里面）
        • 开中断（当然，这是允许嵌套中断才要，如果涉及嵌套中断就需要考虑中断的优先级了，所以相应的中断屏蔽字可能也需要更新，所以可能有一个送中断屏蔽字的过程）
        • 服务处理
        • 关中断
        • 恢复现场（以及屏蔽字）
        • 开中断
        • 中断返回

    再说内中断：

    • 是由 CPU 内部执行过程中直接产生的，什么意思？一般是一些程序主动的行为或者是异常行为；

      • 主动行为：比如程序访问一个系统调用，其实内部原理是基于中断实现的（因为涉及内核态和用户态之间的切换几乎都是靠中断实现的），比如退出进程吧，int 23(好像是这个)，就是程序主动发起一个中断，或者说让CPU直接执行一条中断语句，这个过程其实和上面差不多，并没有太大差别。
      • 异常行为：比如程序缺页异常，出现除 0 异常，访问越界异常等等，程序就不能再继续正常往下执行了，然后将原来执行过程打断。

      多说一点，就个人经验而言，如果是这些内中断，其实服务中断程序都是由开发操作系统的人来写的，一般并不会包含上述的外中断的中断服务程序的全部过程，就比如数组访问越界异常，可能直接就是在服务程序那里直接让程序直接退出。

    另外，毫无疑问，内中断是肯定不能被屏蔽的，因为它是主动行为（就下一条语句就是这个）或者是严重的错误，如果不执行想必会造成大麻烦，而且其优先级也是最高的。

  10. 流水线

    • 装入时间：
    • 排空时间：
    • 超标量技术：配备多个部件，取多条指令，并行执行；它不能改变指令的顺序，所以可以通过编译优化来提高并行性。
    • 超流水线：一个时钟周期再分段，一个部件在一个时钟周期内使用多次。靠编译优化解决优化问题。
    • 超长指令字：由编译程序挖掘并行性，将多条能并行操作的指令组合成一条具有多个操作码字段的超长指令字，需要多个处理部件。

  11. 寻址方式：

    • 直接得到内容的：
      • 立即寻址：立即数即为数据
      • 寄存器寻址：寄存器内容即为数据
      • 堆栈寻址：寄存器堆栈里为内容，内存堆栈为内容
    • 间接得到内容的，即先得到地址的
      • 直接寻址：直接得到地址
      • 间接寻址：访问内存后得到地址
      • 寄存器间接寻址：寄存器里面的内容为地址
      • 基址寻址：基寄存器的内容 + 偏移得到地址
      • 相对寻址：相对 (PC) 得到地址
      • 变址寻址：和一个数 A 为首地址 + DX 寄存器的内容得到地址

  12. CISC, RISC

    CISC 主要目标是精简指令嘛。

  13. 判断是否溢出

    如果两个负数相减定不溢出。溢出位和进位如何判断？

  14. 微程序的存储器的容量：

    graph TD
a(一条机器指令) --> b(一个微程序) --> c(多条微指令)
subgraph 微指令
	c --- d(微操作)
	c --- e(微命令)
	d ==一一对应=== e
end

    微指令的三种格式：

    一般来说，一条微命令应该包含两部分：控制字段和下一条微指令的地址的信息（可以直接是下地址即断定方式，也可以是通过微指令地址形成部件形成即根据操作码形成）

    • 水平型

      编码方式有三种：

      • 直接编码：字段中每一位就代表一个微操作
      • 字段直接编码：互斥微命令放同一个字段
      • 字段间接编码：某些微命令需要另一个字段的微命令来解释，即受到另一个字段的译码输出的影响

      常考的就是直接编码和字段直接编码，假如定长，需要多少位，以及控制存储器的容量的问题。值得注意一点是：假如采用字段直接编码方式，需要留出一种状态来表示该字段不发出信号，比如是 3 位，则只能表示 7 种微操作，其中一种状态比如 000 表示该字段不发出信号。

      直接字段编码、地址断定方式下，微指令的格式为 ` 控制字段 判断测试字段 下地址 `， 值得注意，测试字段的外部条件决定的，n 个外部条件对应 n 位。

    • 垂直型：

      类似机器指令一样，op | source_addr | des_addr

    • 混合型: 前两种的综合。

  15. 统一编址：

    即二者地址空间一致，用我喜欢的数学的语言来描述就是：两个空间中的地址向量可以互为表示，维度一样。

    • Cache 和主存的编址：不一样，不共享一个地址空间

  16. CPU的过程

    取指周期：PC -> MAR,

  17. 乘法

    高位和低位，要求低位寄存器的最高位和高位寄存器上所有的位都相同时，才不溢出。

操作系统

  1. 位图表示法是啥?(操作系统里面的外存管理)：

    文件系统里面用来记录磁盘空间哪些块是否空闲的方法。每个盘块用一个 bit 表示，1 表示已分配。可以采用二维的形式，就是一个 bit<M,N> map 的数组，然后行和列表示第几个磁盘块，数值表示是否被分配。

    顺便提及一下其他几种空闲空间的管理方法：

    • 空闲表法：
      • 把磁盘块的按第一个空闲块的起始位置 Addr，以及以此为开始连续空闲块的个数 N, 按 Addr 的递增顺序存在一个表里面。然后操作系统给文件分配空间的方法可以采用最佳适配、首次适配、最坏适配、当前首次适配等方法；
    • 空闲链表法：
      • 把所有空闲盘块组成一个链表，分配时只需要取下相应的块给用户，然后在链表上删除这些块。回收时，把磁盘块链接到表尾。
    • 成组链接法：
      • 以上的空闲表和空闲链表法都不适应于大型文件系统。UNIX 结合这两种方法，大致思想为：第 0 个空闲扇区不存实际的空闲位置，而是存储另外的 n 个空闲扇区的地址，可以理解成一种索引（类似与 Unix 里面的一级索引块），然后第二层的 n 个空闲扇区，然第 n 个重复第 0 个的操作，另外的 n-1 个直接存真正的空闲块的地址。然后依次类推，直到把所有空闲位置全部链接起来。

  2. 磁盘的扫描算法，以及寻找到一个特定扇区时间的计算；

    一次磁盘平均读写操作时间：

    $T = T_{寻道} + T_{延迟} + T_{传输时间}$

    $T_{延迟}$ 为转一圈的时间的一半，平均时间嘛。

    $T_{传输时间} $ 取决于磁头旋转经过某个扇区的时间。

    磁盘扫描算法，是针对寻道而言：

    • FCFS: 先来先服务，谁先来服务谁，公平
    • SSTF: 最短时间优先，离当前磁头就近的优先，不公平，可以产生饿死；
    • SCAN,(电梯算法)：就是规定磁头的移动方向，在当前磁头方向上离它最近的优先，对最近扫过的区域不公平。还有Look 优化，即不用走到磁头终点，走到最右的一个请求即可；
    • CSCAN：优化一下，到达终点后，不是返回，而是迅速走到初始磁头位置，然后开启下一次的 SCAN 算法。偏向处理最外或最离的那些请求。

  3. 磁盘的管理：

    一个新的磁盘只是一个含有磁性记录的空白盘。需要进行以下操作：

    • 低级格式化（物理分区）：把磁盘分成扇区，每个扇区对应的数据结构为：
      • 头、数据区域（通常为 512 B的整数倍）和尾部。这其实也很好理解，头部应该包含了该扇区的一些描述信息，比如数据区域从哪开始，尾部在哪等等，甚至一些校验信息。这部分内容是出厂之前就完成的。
    • 操作系统分区：操作系统为了记录数据，还需要把自己的数据结构记录在磁盘上，首先就是将磁盘按不同的柱面分成多个区（即所谓的 C 盘，D 盘），这也属于物理分区，为什么呢？因为按不同柱面划分，柱面是实实在在存在的，是物理的。
    • 对物理分区进行逻辑格式化：由逻辑格式化程序完成，对于每个物理分区，创建文件系统上去，比如扫描所有的块呀，填入空闲表之类或分配表之内，然后规定每个块的数据结构之类，还有创建一个空的文件目录表等等。

    磁盘的块和扇区啥关系？

    • 块应该是若干个扇区的集合，块一般是一次 I/O 的基本单位，一般一个扇区就是一个块（块可能单纯指扇区上数据部分的信息）

    引导块的概念：磁盘中块有以下分类：

    • 引导块：一般是磁盘的第一个扇区，存放引导程序，目的是把操作系统从外存中加载到内存并执行之；（就开机的时候，RAM都是掉电消失的，这时候第一步是要把操作系统加载到内存，然后怎么做呢？这就需要存在 ROM 里面的 BIOS 的功能了，它会依次扫描磁盘、光盘、U 盘（当然，这个优先顺序需要自己设定？emmmm，如果说设定是不是意味着其实是可编程的？）的第一个扇区，然后如果发现操作系统（比如以 0xAAAAA 结尾），就把该扇区内的内容加载至内存 0x7C00 处，并跳转到 0x7C00 执行。所以设计操作系统的人，会把一个只有不到一个扇区大小即512B的引导程序写入到第一个扇区，然后有了这个程序，这个程序再把操作系统的其他部分，内核啊、其他东西呀一并加载至内存等等。
    • 分区控制块：

  4. 页面分配策略： 操作系统给进程页面分配的策略：

    • 固定分配，局部置换。就是给定一个进程固定的页框数，每次调页只对它自己拥有的页面数进行置换；
    • 可变分配，全局置换。操作系统自身维护一个全局内存空闲的页框表，每次进程需要引入新的页时，直接从页框表中取下一个分配给它；
    • 可变分配，局部置换。先预先给定一个进程一定数目的页框数，开始时缺页时只是在进程已经分配的那些页框里面进行置换，如果发现进程的缺页率升高，则从全局内存空闲表里取下一定数目的页框给它。

  5. 虚拟存储器

    要和文件管理区分开来，虚拟存储器虽然也是和文件一样是针对外存而言，但是虚拟存储器本质是针对内存而言的，即针对进场的内存管理，这是需要注意的。

    虚拟存储只能基于非连续分配技术。

    请求内存分页和内存分页是不同的：

    • 内存分页是内存管理的一种形式
    • 请求内存分页就涉及虚拟内存管理了：增加了请求调页和页面置换功能。

  6. I/O 是数据总线

    I/O 数据总线上传数据。CPU对I/O控制命令也是通过数据总线来进行

    I/O 控制总线只传送读/写信号。（其实也是显然的，因为I/O接口中含有译码器，不可能CPU直接把控制信号直接传给I/O设备，否则需要I/O译码器做什么？）

  7. I/O 接口的层次执行

    • 用户级I/O软件：库函数啊，给用户使用的一些比如打开文件 open 之类的库函数

    • 设备无关软件层：其实照我理解，应该就是一层和设备无关的软件层，只是这一层软件层的面向对象不是用户而是操作系统，或者开发操作系统的程序员，就是这一些可能包含打开某个设备，控制设备的命令，申请设备、释放设备的命令等等，但是并不设计实实在在的物理设备。

      设备独立性指：

      • 操纵设备的所有公有性操作
      • 向用户层提供统一接口

    • 设备驱动程序：真正的操纵设备的程序。感觉就是应该是每种设备都要有一个驱动程序（想想以前英伟达就好像不给 Linux 给驱动程序）。这个驱动程序是 I/O 进程与设备控制器之间的通信程序，直接控制设备的各种操作，一般可能是它向上层提供一些接口，比如 write 和 read, 然后这一层对这些接口做了具体实现，控制设备工作；同时也会把设备控制器的信号传给上层软件。

    • 中断处理程序：保存被中断的程序现场，转入相应的中断处理程序，并在处理完之后恢复被中断进程的现场后，返回被中断进程。

    • 硬件：设备控制器和设备本身。

  8. 处理机啥时候能调度的问题：

    • 进行结束时可以，创建可以，处于临界区也可以系统调用完成并返回用户态时也可以

  9. 双缓冲区的复习：

    这个需要花一些时间来详细了解，并且把它的计算过程弄流畅！！！

    双缓冲就是指设置两个缓冲区。

  10. 死锁:

    死锁预防：就是破坏死锁的四个条件：

    • 环路等待
    • 互斥访问
    • 持续请求并占有
    • 不可剥夺

    死锁避免：利用银行家算法来避免进入某种不安全状态

    死锁检测：使用资源分配图来检测：不可完全化简时称死锁。

  11. 多道程序等概念：

    • 单道批处理，也称单道程序系统：作业按顺序存储在磁带上，然后由计算机自动按顺序读取一个作业进内存，然后运行，只有一个作业在内存中，只有当该作业完成或异常后再换下一个；
    • 多道批处理：多道程序系统。多个程序同时进入内存，交替在 CPU 中执行。
    • 分时系统：时间片轮转，可交互，同时性，独立性，及时性；
    • 实时操作系统：紧急任务可优先。

  12. 文件访问：

    是通过路径名得到的，然后访问控制是通过用户访问权限和文件属性共同限制的。

  13. 重定位的几种技术：

    页式存储的特点是不连续，离散的，只能使用动态重定位技术。

  14. 管程：

    为了解决信号量分散使用的缺点，使用不当会造成死锁等问题，所以提出管程。管程集中定义了一组只能互斥访问的资源和在该资源上可以进行的操作。

    至多一个进程进入管程。

    基本数据：

    • 共享数据，定义好共享数据
    • 条件变量，用来使进程释放管程的变量，因为一个管程被阻塞时，如果不释放管程，其他进程就无法进入管程

    操作：

    • 定义一些对共享资源的操作，进程也只能通过这些操作来访问资源
    • 条件变量上对应的操作：比如定义条件变量 Condition x
      • x.wait : 调用的进程把自己插入到 x 条件的等待队列上，并且释放管程
      • x.signal: 调用的进程唤醒一个因 x 被阻塞的进程。

  15. 文件逻辑结构、物理结构。

    为了理解这个，可以从文件系统的分层架构入手，从上到下：

    • 用户调用接口
    • 文件目录系统
    • 存取验证控制模块
    • 逻辑文件系统和文件信息缓冲区
    • 物理文件系统
      • 辅助分配模块
      • 设备管理程序模块

    注意到，访问一个文件的时候，其实一直到逻辑文件系统那一层都是逻辑上找到需要访问的文件的数据所在的逻辑块号，之后再再物理文件系统上转换成相应的物理块号。

  16. 簇：数据存储在硬盘的时候都是以簇为单位，所以无论文件大小是多少，除非正好是簇大小的倍数，否则文件所占用的最后一个簇或多或少都会产生一些剩余的空间，且这些空间又不能给其它文件使用，即使这个文件只有0字节，也不允许两个文件或两个以上的文件共用一个簇，不然会造成数据混乱。

    关于混合索引：一级索引的指向问题，一级索引应该是指向下一个存索引的块（或簇）。2018年 408 出现过索引节点和簇大小不同的情况，所以要指出一级或 n 级索引应该是指向簇大小的一个索引块，而不是和原本索引节点大小相同。

  17. 通道和 DMA 执行过程：

    通道：

    • 用户使用访管指令使用 I/O
    • 进入 I/O 处理程序，编制通道程序
    • 启动 I/O 通道，这个时候，通道程序和 CPU 并行
    • 组织 I/O 操作，就是通道程序来负责进行 I/O 操作
    • 通道程序结束后，发出中断，告诉 CPU。

  18. 哲学家就餐问题：

    n 位哲学家围着圆桌就餐的问题，只要限制至多同时 n-1 位哲学家拿筷子，那么就必定不会形成死锁。

  19. 多级页表

    • 顶级页表最多占一个页。
    • 顶级页表和二级页表的页大小相同
      • 页表项是不是也是一样呢？
    • 记住规则即可：二级页表的拥有多少页框是由一级页表的表项数决定的。
    • 二级页表的拥有的表项数就是进程最多拥有的页框数。

  20. 页表的映射方式：

    或者Cache的映射方式，一定要搞清楚啊！！！！

    • 标记，脏位，算法控制位，数据等等。

      其中映射到哪一个块的那部分数据是不用存的！！！

数据结构

  1. 森林，树转换成二叉树的规则：

    • 树转化成二叉树规则：

      • 根的第一个左孩子，依次和它的兄弟节点进行连接，然后除第一个左孩子，其余兄弟节点断开与其父亲节点的连接。然后此时的子树(即以左孩子为根的）绕着左孩子为轴，顺时针旋转 45°，即可。

    • 森林转换成二叉树：

      • 把森林中每一颗树转换成二叉树，然后以第一棵树的根节点为根节点，把第二棵树的根节点连到第一棵树上，第三棵连到第一棵，…, 第 n 棵连到第 n-1 棵的根上。

        它们构成一棵树，然后利用转二叉树的方法把它们转换成二叉树即可。（实际上只需要以第一棵树的根为轴心顺时针旋转45°即可）

    它们遍历的对应关系：

    • 树的先根遍历，对应二叉树的先序遍历
    • 树的后根遍历，对应二叉树的中序遍历
    • 森林的先序遍历：对应二叉树先序遍历
    • 森林的中序遍历：对应二叉树的中序遍历

  2. 图的度：

    • 有向图和无向图的度

  3. AOE网的问题

    Activity on Edge: 找出所有的关键路径，缩短包含在所有关键路径上的活动的时间可以缩短工期。

    还是没有了解清楚这个。我觉得还是详细了解一下AOE为好，就彻底掌握它。

    具体的操作：

    • 首先，找到源点（入度为0）和汇点（出度为0）
    • 然后利用修改过的拓扑排序算法来求解以下的一些量：
      • 每个节点的最早开始时间 ve[…]，每个节点的最晚开始时间 vl[…]
        • 具体怎么做呢？首先，ve[0] = 0, 假设 0 号节点是源点，从源点出发。
        • 然后对于之后的每一个节点 i（拓扑排序会选出，当前节点负责更新 以它出发的有向边 连接的另一端的节点 j 的 ve[] 值），更新为 $ve[j] = \max(ve[j], ve[i] + w_{i\rightarrow j}), w 为边权重$。
      • 求完了最早开始时间后，再逆向拓扑求解最迟开始时间：
        • 汇点的 vl[n-1] = ve[n-1], 假设 n-1 为汇点的
        • 对于一个节点 i, 找到和它有有向边的节点 j，且节点 i 是作为有向边的发出一端。则 $ vl[i] = \min(vl[i], vl[j] - w_{i\rightarrow j})$
    • 之后，求解事件（即边）的最早开始时间 ee[] 和最晚开始时间 el[]
      • 边$w_{i \rightarrow j }$ (这里 $w$ 既表示权重，也表示边本身）的最早开始时间 $ee_{w_{i\rightarrow j}} = ve[i]$, 最晚开始时间 $el_{w_{i\rightarrow j}} = vl[j] - w_{i \rightarrow j}$
    • 最后判定关键活动：
      • 关键活动（就是边）就是那些边的最早时间和最晚时间相等的边所对应的活动；
      • 关键路径：一条从源点到汇点的简单路径，且路径上所有的边代表的活动均是关键活动。

  4. 基数排序，以及各种排序的问题

    基数排序算法的基本原理：简单来说就是按位比较的思想。比如给定一系列整数，假设均为3位，那么可以先比较个位，按个位比较排一次序（过程就是，构造 10 个链表，编号从0-9，然后依次把数按照它们的个位 num % 10 = i 填入到第 i 个链表中。然后按需把链表中所有数按头至尾串起来），然后按十位、按百位排序，完成之后，整个数据就有序了。

    稳定的，空间复杂度：O(r), (r 为链表数)，时间复杂度O(d(n+r)), d为趟数，与序列起始状态无关。

    冒泡排序：

    • 基本思想是：每次从最后面选一个数，一直往前进行冒泡，使小的数一直往前走的去（就是每次和前一个数比较，如果前面更大就交换位置，让小的数一直往前走，大的往后挪）。

      也可以反过来！每次大的往后冒泡啊！！

      void bubleSort(vector<int>& arr){
    bool flag = false;
    for(int i=0;i<arr.size()-1;++i){
        flag = false;
        for(int j=arr.size()-1;j>i;j--){
            if(arr[j-1]>arr[j]){
                swap(arr[j-1],arr[j]);
                flag = true;
            }
        }
        if(!flag) return; // 没有发生交换，说明已经有序，直接返回
    }
}

    • 选择排序

      基本思想：第 i 次选择出第 i 小的元素。

      void selectSort(vector<int>& arr){
    for(int i=0;i<arr.size()-1;i++){
        int minIndex = i;
        for(int j=i+1;j<arr.size();++j){
            if(arr[j]<arr[minIndex]){
                minIndex = j;
            }
        }
        if(i != minIndex) swap(arr[i],arr[minIndex]);
     
    }
}

  5. 堆排序：

    1. 首先，初始化为一棵完全二叉树；

    2. 然后调整它的前 $i, i <= N/2 $ 个节点：调整的过程为，以选中的节点 $node_i$ ，调整它的两个孩子节点 $node_{2i}, node_{2i+1}$(如果只有单个孩子节点，则直接选中 $node_{2i}$) ，如果是建大顶堆，那么先比较两个孩子，较大的节点 $node_{max}$ 再和当前节点 $node_i$ 比较，如果当前节点更大，那么不调整，转第 3 ；若当前节点更小，则把当前节点和对应的 $node_{max}$ 进行交换，同时在沿着交换后的 $node_{max}$ 所在子树继续调整，重复上述过程至到节点不和孩子节点发生交换，然后转3。

    3. $i$–，若 $i \geq 1 $转 2

    4. 以上过程已经建好了一个堆，之后排序：排序过程很简单，把堆顶元素和堆最后一个元素 j 交换，然后调整堆，并且 j–；一直到 j == 1为止（其中，交换了的元素，即堆顶元素交换到的那个节点不视为堆的一部分，所以调整的时候不涉及它们。）

  6. 查找

折半查找法的二叉判定树。折半查找从几开始的问题。书上都是从 1 开始。

  1. 归并排序：

    • 每个段都有序。

  2. AVL 树的操作：

    • RR 旋转：竟然是左单旋转！
    • LL 旋转：竟然是右单旋转！
    • LR: 正常的左单选右旋转，反正一定涉及三个节点，其中第三个节点是要被转上去了。
      • 旋转轴首先是对第三个节点而言，其中旋转对象是第二个节点；
      • 最后的右旋，还是以第三个节点为轴，然后旋转对象为第一个节点。
    • RL旋转：同LR旋转。

  3. 哈夫曼树：

    • 最小带权和的树，可能有多颗，是一种二叉树，不一定是完全二叉树。
    • 具体而言：
      • 每次选取权值之和最小的两个节点，然后构造它们的父节点，其中左右孩子节点顺序没有规定

  4. 三对角矩阵：

    对角矩阵也称为带状矩阵。三对角矩阵：非零元素全部集中在三条对角线上。

  5. 关于缺失率的计算：

    • 首先要明确进行了访存的次数 N；
    • 然后再计算缺失的次数 M
    • M/N，即为缺失率。

  6. 十字链表：

    存有向图。就是每个顶点和边都有相应的一个数据结构来对应它们，比如是顶点节点和边节点（弧节点），然后它是一种类似于邻接链表的数据结构，首先是顶点节点顺序存储，然后每个顶点节点的数据结构包含顶点的data，两个指针，第一个 firstIn 指向一个弧节点，该弧节点的弧尾是该顶点；另一个指针是 firstOut 指向的弧头是该顶点的弧节点。然后弧节点也有两个指针，第一个指向弧尾和该弧节点的弧尾一样的弧节点，另一个指向弧头和它一样的弧节点。然后可见，每条弧只会存一遍。

  7. 关于树或图等的结论：

    • 树的所有节点的度数之和 == 节点数 - 1（因为度的含义是某个节点的孩子个数，然后度数之和漏算了根节点）
    • 完全二叉树或哈夫曼树（即除了叶子节点，其他节点的度为2的树）：$ 2*n_{非叶子} = n_{叶子节点} + n_{非叶子节点} -1 $，即 $n_{叶子节点} = n_{非叶子节点} + 1$， $n_{叶子} = \frac{n_{总}+ 1}{2}$

  8. 连图子图等等概念：

    • 子图：就是它的一部分
    • 生成子图：就是包含所有的节点
    • 无向图的连通分量：极大连通子图，极大连通子图包含所有的节点和边，可能有多个。
    • 有向图的强连通分量：极大的连图子图
    • 生成树：连通图的生成树是极小连通子图（边数最少保持连通，一般是每个连通分量的一个极小连通图）
    • 有向树：一个顶点的入度为 0，其余顶点的入度均为 1 的有向图。

  9. 查找：

    查找的成功和失败，先说失败吧，失败要构造失败节点。

  10. 外排序：

    • 置换选择排序：用于生成初始归并段。用于解决内存的缓冲区的大小限制了初始归并段的最大段长的问题。简单来说就是有三部分组成 FI, WA, FO：WA填满，取一个最小值记为 MAXMIN 出来，输入到 FO, 同时从 FI 输入一个到 WA。然后从 WA 中找比MAXMIN 大的最小的那个数，输出到 FO，同时更新 MAXMIN 为那个数；然后从 FI 输入一个数到 WA，重复上述操作，直到 WA 中没有数比 MAXMIN 大，然后 FO 中就构成了一个初始段。然后清空 FO，重复之前操作，重新选 MAXMIN 。

    • 最佳归并树：

      k 路归并，则 $n_{叶} = n_{内} * (k-1) + 1$， 则 $ n_{内} = \frac{n_{叶} - 1}{k-1}$:

      • 整除时，则不需要添加虚拟段，按照哈夫曼树的思想构造最佳归并树
      • 余数为 u 时，则需添加 k - u - 1 个虚拟段，段长为 0

  11. 带权路径的定义：

    WPL = 从根到所有叶节点的路径长度 * 叶子节点的权值的和。

  12. 注意满二叉树和完全二叉树的定义区别

  13. 随机查找和顺序查找定义：

    顺序查找是对关键字有序的线性表进行查找。

    随机查找：姑且认为树的查找方式就是随机查找，查阅资料，并无定义啊，估计是王道习题瞎编的概念。

计算机网络

  1. 计算机网络里面，那个数据链路的带宽到底怎么算的问题。

    • 各种协议下如何计算，选择性重传（SR), GBN，停等协议；

      计算方法，均考虑第一帧从发出到收到确认的这段时间T0。为什么这样？因为无论是选择性重传还是滑动窗口协议，都是采用流水线方式，那么流水线方式就意味着可以一下子发送很多，比如 N 帧，而只有当第一帧收到确认后，才能下一次发送第 N+1 帧，可以想象成如果第 N 帧未被确认，后续第 N+1 帧就会被阻塞一样，所以是这样。

      根据以上分析，$T_0 = RTT + T_{传输延迟}$。

    • 另外，几个协议的的序号问题：

      • GBN: 接收窗口大小为1，n 比特的编号，发送窗口大小 W_T:

        1 <= W_T <= 2^n - 1;

      • SR选择性重传，接收窗口不为1；

        W_s = W_r;

        W_s = 2^(n-1);

    • 信道利用率：发送了比特的时间/一个发送时间周期；是一个百分比；

    • 信道的吞吐量 = 信道利用率 * 发送方的发送速率；

    • 还是这个问题，它会变形，求知少的帧号位数，这里就需要考虑发最短的帧还是最长的帧，显然应该发最小的帧，这样才能多发。

  2. HDLC 协议

    遇到连续 5 个 1 就在后面插入0， 它的帧的标志字段为 01111110

  3. OSI七层模型：

    从上至下为：

    • 应用层
    • 表示层
    • 会话层
    • 传输层
    • 网络层
    • 数据链路层
    • 物理层

  4. 各类应用使用的协议：

    数据链路层：

    • CSMA/CD, CSMA/CA，属于MAC 控制子层。
    • PPP 协议、HDLC 协议，SR等协议，属于 LLC 子层。

    网络层：

    • IP 协议
    • IGMP 协议（网络组播管理协议）
    • OSPF 协议 (属于内部网关协议，它自己又可以分区)
    • ARP 协议
    • ICMP 协议（网际控制报文协议），PING 命令直接使用了 ICMP (但 PING 工作在应用层)，Traceroute 工作在网络层

    传输层：

    • UDP/TCP

    应用层：

    • RIP (UDP): 距离向量路由协议，属于 IGP (内部网关协议)
    • BGP (TCP)：边界网关协议，属于 EGP (外部网关协议)
    • DHCP协议（UDP)
    • DNS (UDP)
    • SNMP(UDP)

  5. 奈奎斯特采样定理

    无噪声情况下，极限带宽 $2*W \log_2V$ (bps)

    香农定理：$W* \log_2(1+S/N) bps$, 其中 $S/N$ 是信道的传输信号的平均功率/ 高斯噪声的功率，其中定义 $10\log_{10}(S/N)$ 为信噪比，单位为 dB，即 10dB，对应 S/N = 10, 30dB时，为S/N = 1000.

  6. ICMP报文类型：有两种：差错报告报文和 ICMP 询问报文。

    其中差错报告报文用于报告差错和异常情况：有以下 5 中类型：

    • 终点不可达：主机或路由器不能交付数据报，就像源点发送终点不可达报文
    • 源点抑制。路由器或主机由于拥塞而丢弃数据报时，限制源点的发送数据
    • 时间超时：TTL减为零
    • 参数问题：首部有不正确的值
    • 改变路由（路由重定向）：发现更好的路由

  7. 以太网的帧：

    最短是 64 B，其中数据部分为 64B - 18B = 46B

    最长是 1500B + 18B，其中数据部分为 1500B。

  8. TCP协议：

    TCP协议是面向字节流的，虽然应用程序和 TCP 的交互是一次一个数据块，但 TCP 把从应用程序交付下来的数据视为无结构的数据流。

    其中，关于 TCP 协议的慢启动算法和拥塞避免算法的发送窗口和拥塞窗口。首先，这些算法都是针对拥塞窗口的大小而言，一般发送窗口的大小 $W_{send} = \min(W_{receive}, W_{crowded})$ 。

    注意几个 TCP 协议的慢启动算法和拥塞避免算法：

    • 慢启动算法：每收到一个 MSS 段的 ack 帧后，$W_{crowded} += MSS$, 时间上的表现就是每过一个 RTT 就翻倍，超过阈值时就等于阈值。
    • 拥塞避免算法：等于阈值后，就是收到一次全部发出去的报文段的 ack 后，$W_{crowded} += MSS$， 时间上的表现就是每过一个 RTT就加一。

  9. CSMA协议：

    CSMA协议中，有 1-坚持，p-坚持，非坚持。

    • 1-坚持：先说坚持含义，坚持就是指信道空闲的时候，依然持续监听信道；所谓的 1 就是指当监听到信道空闲的时候，以概率为 1 发送消息，即马上发送消息。

    • p-坚持：根据 1-坚持的含义，不难知道这是指的是监听到信道空闲的时候以概率 p 发送消息

    • 非坚持：就是信道空闲的，随机延迟一段时间之后再监听信道。

  10. 语义、语法、规则：
    • 语义：规定需要完成的功能
    • 语法：规定传输数据的格式
    • 规则：规定了各种操作之间的时序关系、操作条件。
  11. 计算机网络中的数据传输方式：
    • 电路交换：需建立专用的物理通信路径，然后有序传输数据，传输完成后释放连接。不分组，直接传送数据。
    • 报文交换：无连接，每次直接发送一个大报文
    • 分组交换：是报文交换的改进，可以把要发的数据切分成一段一段的更小的分组（package）。其中，分组交换又可以细分以下两种数据传输方式：
      • 面向连接的虚电路方式：虚电路有永久虚电路和零时虚电路两种。
        • 在逻辑上，发送方和接收方建立一条虚电路；开始需要花时间建立虚电路，开销有点大；建立阶段将确定唯一的一条传输路径（第一次的路由选择），然后后面的通信将直接通过该路径进行通信。
        • 建立好虚电路后，通信的分组将采用虚电路标识来进行通信，而不是目的 IP 或目的 IP 地址，这样或许可以减少数据量；
        • 传输数据是有序的，可靠的，面向连接的；
        • 致命弱点：若该虚电路中某一个节点出现故障，则整条虚电路将瘫痪。
      • 无连接的数据报方式：
        • 不可靠，无连接，尽力交付
        • 不保证是否有序到达，（IP数据报就是这种）
  12. 数据链路层：
    • 功能：增强在物理层传输原始比特流的能力，比如提供链路管理功能（建立信道，使用信道，释放信道）、组帧和帧界定功能、差错控制、流量控制与可靠传输控制、介质访问控制，为上层提供服务。
    • 介质访问控制：
      • CSMA/CD:

  13. ARQ协议

    auto repeat request: 自动重传请求协议，有三种：

    • 停等协议，Stop and Wait
    • GBN: 回退 N 协议
    • SR: 选择性重传协议

    后两种是和滑动窗口进行组合，又称连续 ARQ 协议。

  14. 802.11 无线局域网的 CSMA/CA 协议

    CSMA/CA: 无线局域网使用该介质访问控制协议，解决隐蔽站和暴露站的问题。

    • 每个节点在发送数据之前，监听信道，如果信道空闲，则先等待一个帧间间隔 IFS，然后等待完之后，信道仍然空闲，运行随机退避避免算法，即再过一段时间后，如果此时信道仍然空闲，则开始发送数据。
    • 根据要发送的数据的帧不同，等待的 IFS 长短不同，一般而言越高级的帧（ACK，CTS）的，IFS越短，而低级的越长，比如 RTS。
    • 一般来说，如果一个节点 A 要向另一个节点 CA 发送数据，需要进行如下操作来解决隐蔽站和暴露站的问题，先说明无线下通信都是采用广播方式：
      • 先预约信道：A 向 CA 发送 RTS 帧（实际上是广播），A周围的节点也会收到 RTS 帧，然后它们知道有人要发数据，所以在一段时间内不发送数据，处于缄默状态。RTS 帧表明自己要发数据且指明自己发送数据所需的时间，然后 CA 返回一个 CTS 帧（清除发送帧），告诉 CA 周围的设备在这段时间不要发送消息，然后其他节点也进入缄默状态，并且告诉 A 可以开始发送数据；
      • ACK帧：接收方 CA 接受到数据后，需要反馈一个ACK帧，确保数据正确接收到。然后其他节点收到 ACK 后，缄默状态解除，表示可以发数据。同时还会超时重传。

  15. IP上网

    在公网里面上网的 IP 都是全局 IP，如果是私有 IP 需要进行 NAT 映射。

    NAT 映射有两种：

    • 源映射：就是一个内网的主机需要访问互联网时（别的子网），需要在路由器进行 NAT 映射，把源地址变换为公网 IP 地址；
    • 目的地映射：访问的主机实际上也是在内网，需要在到达目的地那台路由器时进行目的 IP 的映射。