数据结构
C语言标识符需要 字母 / 下划线 开头，不能数字开头
中序和层序才能构成唯一的二叉树，先序和层序不能。
完全二叉树的叶子节点不一定在最后一层，最后两层都可能。下(n/2)为最后的父节点。
查找
分块查找，块内取√n长度，ASL达到最小值。
Hash表删除元素，不能简单地删除，而是标记为删除。因为在开放定址法里面，会影响到后面的元素查找。 Hash表平均失败长度是对mod出的位置算，不是对所有表的位置都算。
B树支持随机查找，B+支持随机和顺序。注意基础的是随机查找，特有的是顺序查找。
折半查找判定树 是一种平衡二叉排序树，判定树的结构和总节点数N一一对应。 高度H=下(log2 n)+1=查找成功最多比较次数=查找失败最多比较次数 N节点建树方法： - 先判断高度H，构建好H-1层的满二叉树 - 对于剩下的节点： - mid向下取整时，从根节点开始，按照先右后左的顺序判断往哪边挂新节点。对子树也是递归同样的规则判断。 - mid向上取整时，先左后右 - 最后按照中值遍历的顺序填充节点值。 >向上取整和向下取整体现在树中就是哪侧会多一个节点。
排序
所有元素相等时的排序：简单选择排序是n^2, 基数排序是nd。
插入排序，注意n趟之后是有n+1个元素有序。初始一个不算趟数。
堆排序向下调整，先找出两个子节点中最厉害的那个，再换，递归继续向下。
平衡二叉树[节点最少/层数最多]情况的递推：N1=1 N2=2 Nh=N(h-1)+N(h-2)+1
排序序列原始状态只影响快排的效率，不影响趟数，事实上每一趟确定一个数的位置。
计组
小心，CPI和时钟频率无关，只和执行速度有关
RISC的体系结构并不等同于早期计算机的简单结构
数据总线的位数一般等于机器字长，但也不绝对。大于的时候CPU可以分两次取数。
翻译程序 - 编译程序：将高级语言程序一次全部翻译成目标程序。每次执行只执行目标程序文件 - 解释程序：将源程序每条语句翻译成机器目标代码，并立即执行。不产生文件。 - 汇编程序：将汇编语言翻译成机器语言，和机器语言一一对应。
编码
不是所有十进制小数都可以用二进制表示，如0.3
浮点数
浮点数运算，阶码双符号位判断溢出，尾数双符号位决定正负。 阶码上溢需要中断处理，阶码小于最小阶码即下溢，看作机器零处理。
最简单的浮点数舍入处理方法是直接截断法。
IEEE754浮点数乘法运算结果肯定不需要左规处理。左规是数往左移动，好让小数点前面有个1。因为754尾数必然≥1，尾数运算结果也必然≥1，显然不会需要左规。
IEEE754 阶码全1尾数全0是±∞，阶码全0尾数全0是±0。如果尾数此时不是0，则是NaN非规格数。
存储系统
Cache Cache不能作为指令地址码，一般都是主存单元作为地址码，系统自动在Cache中查找，Cache对程序员透明。 指令地址码一般是 主存单元/数据寄存器。
Cache每行位数：数据bit+Tag位+(LRU 1)+(修改位 1)+(有效位 1)。注意不需要组号位，假如是组相联映射，主存地址结构中间几位是组号，但是Cache每行里面不需要装组号，多路分组是地址结构解析的事。
Cache采用N路组相联映射：组内有N行，组数=数据区容量/每组容量
Cache完全由硬件实现，且Cache透明。 虚存由软硬件实现。虚存对系统程序员不透明，对应用程序员也透明。虚存大小≤内存+外存 Cache和TLB缺失都可以由硬件处理。
对a[k]=a[k]+32; 赋值也需要访问Cache，即需要访问两次Cache里的a[k]。
RAM RAM都是易失性存储器 SRAM 非破坏性读出，DRAM 破坏性读出，。 SRAM 双稳态触发器，不需要再生，DRAM电容存储，需要再生。 SRAM 更贵，功耗更大，集成度更低，速度更快。 DRAM 地址复用，分两次送行列地址。
高位交叉存储器也可能在一个存储周期内连续访问几个模块，只不过概率比较小...
存取周期和存取时间是不同的概念，周期是连续两次操作的间隔，时间是一次操作的时间。周期＞时间。
分页管理和虚拟存储器 TLB里存的是页表，访问完TLB还要访存访问页面。 注意在统计TLB和主存访问次数的时候，缺页中断后，对原数据重新访问一次。
分页存储解决的是不连续存储的问题，注意虚拟存储器的请求分页机制才是逻辑扩充容量。
页面置换算法中，只有FIFO会出现Belady现象，队列类算法。 LRU性能好，但需要寄存器和栈的硬件支持，是堆栈类算法。 NRU=CLOCK，用较小的开销接近LRU性能。
工作集窗口k是从当前时刻往前k个之内，是集合。不需要因为重复继续往前延伸。重复时工作集大小就小于k了。
指令系统
指令字长通常都是存储字长的整数k倍，k≥1。注意只说一样长是错误的。
CPU
CPU数据通路由控制部件控制，因此数据通路内不包括控制部件。
无论执行什么指令，CPU在指令周期首先是 取指，(PC)->MAR。
CM控制存储器存储的是 所有机器指令的微程序，也即所有微程序的所有微指令。 CM容量=微指令数X微指令字长 注意水平型微指令字长 - 操作控制字段，字段直接编码——互斥性微命令放在同一段进行编码，相容性微命令放在不同段。 - 判断测试字段位数=外部条件数。比如外部条件3个，应该是3位，而不是2位。 - 下地址字段位数N：即2^N≥所有微指令数。
总线
地址总线是单向的，数据、控制总线是双向的。
异步定时方式适合速度差异较大的设备之间。完全依靠双方的握手信号来实行定时控制。
IO
DMA中断只用来向CPU提出传输结束，可能报告数据错误，不会检查数据错误，不用来实现数据传送和申请总线。
DMA中断请求可以在每个机器周期介乎，而普通中断需要在每条指令执行后。
初始化中断向量表由操作系统完成，找中断向量由隐指令硬件完成。
CPU通过IO指令控制通道。通道在通道程序执行结束产生IO中断向CPU报告。 程序中断和通道都是软硬件结合的方式
设备独立性=设备无关性=用户程序独立于具体物理设备=使用逻辑设备号 设备驱动程序：与硬件直接相关，隐藏同类设备的设备控制器之间的差异。 虚拟设备是指把一个物理设备变换成多个逻辑设备，但不是指把独占设备改成共享设备。
操作系统
微内核比起单一大内核效率更低，因为需要频繁切换核心态和用户态，开销大。
从操作系统内核空间读数据或指令是静态的，不需要保护。
进程管理
线程共享进程的虚拟地址空间，但每个线程有自己的栈空间。 子进程不共享父进程的虚拟地址空间，仅共享一部分资源。创建子进程时会分配相关资源。
进程打开定时器是需要保护的操作，否则可能修改时间片。
设备分配不会创建新进程，只是设置对应数据结构。
死锁处理 - 死锁避免：银行家算法，在进程执行过程中动态规避可能导致死锁的分配。 - 死锁预防：从根本上破坏死锁条件，使死锁不可能成立。如限制进程申请资源的顺序，给资源编号分配。 - 死锁检测：啥都不管，真死锁了检测到了，就强行处理掉...
内存管理
地址变换时，可能因缺页、地址越界、内存保护发生中断，不会发生内存溢出。
文件系统
Open()系统调用打开文件，读入文件的控制管理信息。文件内容是在打开之后，需要使用文件的时候，再读入。 FAT表是在挂载文件系统的时候就读入到系统了。 超级快是系统自举用，启动系统时读入。
逻辑记录是对文件进行存取的基本单位。
索引文件的表项装的是记录逻辑地址，不是物理地址，因为索引文件是逻辑结构。
对文件访问权限的管理，通常由用户访问权限+文件属性限制，注意和用户优先级无关。
直接存取是介于随机存取和顺序存取（磁带）之间的方式，直接存取存储器，例如磁盘，一般也可以顺序访问，但是比较低效。
磁盘调度算法中，不会导致磁臂黏着的只有FCFS，考虑同一个磁道不停地申请。
磁盘初始化：物理/低级格式化：扇区+校验码————柱面分磁盘区————逻辑格式化：文件系统+空闲盘块数据结构
计网
虚电路分为永久性虚电路和交换型虚电路，所以不是所有虚电路都会在会话结束释放链接。
网络线路吞吐量=单位时间内通过的数据量=发送bit/(发送时延+往返时延)
OSI 网络层两种方式，传输层仅面向连接。 TCP/IP 网络层无连接，传输层两种方式。
交换机和路由器的线路，即没有主机的线路，也算交换机分割的一个冲突域。
按照对等层通信原则，IP分组的重组由网络层完成，而排序则由传输层完成。
端到端是指进程端口到进程端口，即TCP/IP传输层。 点到点是网络节点到网络节点，数据链路层。
计算信道最高数据传输率的时候，注意看清给的是信道频率还是信道带宽。两个公式要求的W都是带宽。例如给频率3.5~3.9MHz，带宽=3.9-3.5=0.4MHz
数据链路层
CSMA/CD 冲突时间=往返时间，最小帧长=最大帧碎片长
以太网冲突时间=2τ=51.2μs 10Mb/s以太网最小帧长=10Mb/s X 51.2μs=512bit=64B
连续ARQ包括两种：GBN和SR选择重传
以太网最小数据长度46B，因此封装的IP数据包总长度字段要≥46
无线局域网 CTS和ACK确认帧的IFS都是SIFS。RTS之前有DIFS。 帧格式地址：RA(BSSID)+SA+DA = 目的地接入站地址+ 源地址 + 目的地址
网络层
ARP请求是广播的，ARP响应是单播的。作为对比，DHCP是四个广播：DHCP发现，DHCP提供，DHCP请求，DHCP确认。
路由表中配置到互联网的路由即一般默认路由项：目的IP 0.0.0.0 + 子网掩码 0.0.0.0 + 下一跳IP + 接口
传输层
TCP连接时，默认只有第一个序号是消耗的，第三次握手的序号也可以用作数据传送。
注意IP分片需要是8B整数倍，偏移量=x/8B
应用层
HTTP 服务器是80端口，客户端不确定。
WWW高速缓存将最近的一些请求和响应暂存在本地磁盘中，可以有效降低WWW延迟。