知识点库

数据结构是相互之间存在特定关系的数据元素的集合，包括逻辑结构、存储结构和数据运算三要素。

算法是对特定问题求解步骤的描述；五个特性：有穷性、确定性、可行性、输入、输出。

顺序表用连续存储空间实现线性表，支持随机访问O(1)，插入删除需移动元素O(n)。

由节点通过指针串联的线性结构，插入删除 $O(1)$，随机访问 $O(n)$。

顺序表有静态和动态两种实现方式，InitList初始化，核心是连续存储和长度管理。

单链表插入必须先让新节点指向后继，再修改前驱指针，顺序不可颠倒。

单链表删除需找到待删节点的前驱，修改前驱指针跳过待删节点后释放空间。

双链表每个节点有prior和next两个指针，插入删除需同时维护前后两个方向的指针。

循环链表尾节点指向头节点形成环，常用尾指针表示以便O(1)访问首尾。

静态链表用数组模拟链表，游标代替指针，适用于不支持指针的语言环境。

顺序表适合频繁访问，链表适合频繁插入删除，选择取决于操作特征和存储需求。

线性表是n个相同类型数据元素的有限序列，有唯一首元素和尾元素，元素间一对一关系。

线性表应用包括多项式表示、有序表合并、稀疏多项式运算等综合算法设计题。

栈是只允许在一端（栈顶）进行插入和删除的线性表，后进先出LIFO。

顺序栈用数组实现，top指针指示栈顶位置，入栈top++再赋值或先赋值再top++。

链栈用链表实现栈，栈顶为链表头部，入栈出栈均在表头操作，无栈满问题。

队列是只允许在队尾插入、队头删除的线性表，先进先出FIFO。

循环队列用取模运算解决假溢出，判满条件常用牺牲一个单元：(rear+1)%MaxSize==front。

链队列用链表实现队列，front指向队头，rear指向队尾，适合队列长度变化大的场景。

双端队列允许两端都可入队出队，输入受限/输出受限双端队列是常考变体。

栈应用：括号匹配、表达式求值（后缀表达式）、递归实现；队列应用：BFS、调度。

栈、队列和数组在算法中的综合应用，包括递归消除、滑动窗口、单调栈等。

数组是按下标随机访问的数据结构，行优先/列优先存储决定地址计算公式。

对称矩阵、三角矩阵、对角矩阵可压缩存储，用一维数组存储非重复元素。

稀疏矩阵非零元素远少于零元素，用三元组表或十字链表存储以节省空间。

n维数组地址计算是一维的推广，需要知道各维长度和存储方式（行/列优先）。

串是由零个或多个字符组成的有限序列，基本操作包括求子串、拼接、比较等。

朴素模式匹配逐位比较，失配时主串回退到起始位+1，最坏时间O(mn)。

KMP算法利用已匹配信息避免主串回退，通过next数组确定模式串回退位置，时间O(m+n)。

nextval是next数组的优化，当T[j]==T[next[j]]时进一步回退，减少无效比较。

前序=根左右，中序=左根右，后序=左右根；已知任意两种（必含中序）可还原。

哈夫曼树是带权路径长度WPL最小的二叉树，用于构造最优前缀编码。

二叉树顺序存储用数组按层序编号，适合完全二叉树，一般二叉树会浪费空间。

二叉链表每个节点含lchild、data、rchild三个域，n个节点有n+1个空指针。

二叉树每个节点最多两个子树，具有n0=n2+1等重要性质。

先序(根左右)、中序(左根右)、后序(左右根)遍历，递归和非递归实现，可由两种序列重建树。

层次遍历用队列实现，按层从上到下、从左到右访问所有节点。

线索二叉树利用空指针域存储前驱/后继信息，ltag/rtag区分孩子和线索。

树的先根遍历对应二叉树先序，树的后根遍历对应二叉树中序。

并查集支持合并和查找操作，路径压缩+按秩合并后近似O(1)。

树是n个节点的有限集合，有且仅有一个根节点，其余节点构成若干互不相交的子树。

树的存储有双亲表示法、孩子表示法和孩子兄弟表示法三种。

树转二叉树：左孩子右兄弟；森林转二叉树：各树的根通过右指针相连。

堆是完全二叉树，大顶堆每个节点≥其孩子，建堆O(n)，堆排序O(n log n)。

DFS用栈/递归实现深度优先，BFS用队列实现广度优先，邻接表时间O(V+E)。

图由顶点集V和边集E组成，分有向图和无向图，核心概念包括度、路径、连通性。

邻接矩阵用二维数组存储，空间O(V²)，适合稠密图，无向图矩阵对称。

邻接表用链表存储每个顶点的邻接点，空间O(V+E)，适合稀疏图。

DFS从一个顶点出发尽可能深入，用visited数组避免重复访问，生成DFS树。

BFS从起始顶点逐层扩展，用队列实现，可求无权图最短路径。

最小生成树：Prim适合稠密图O(V²)，Kruskal适合稀疏图O(E log E)。

Dijkstra求单源最短路径(非负权)O(V²)，Floyd求所有顶点对最短路径O(V³)。

拓扑排序对DAG的顶点排序使所有有向边从前指向后，可用于检测有向图是否有环。

关键路径是AOE网中从源点到汇点的最长路径，决定工程最短完成时间。

十字链表用于有向图，邻接多重表用于无向图，都是边为主体的存储结构。

顺序查找逐个比较，ASL成功=(n+1)/2，可设置哨兵减少比较次数。

折半查找要求有序顺序表，每次比较排除一半，ASL≈log₂(n+1)-1，判定树是平衡BST。

分块查找将表分为若干块，块间有序块内无序，索引顺序查找ASL介于顺序和折半之间。

二叉排序树左<根<右，查找效率取决于树形，最好O(log n)最坏O(n)。

AVL树任意节点左右子树高度差≤1，通过LL/RR/LR/RL四种旋转保持平衡，查找O(log n)。

B树是多路平衡查找树，所有叶子在同一层，适合磁盘存储，减少I/O次数。

B+树所有关键字都在叶子节点，叶子用链表相连，支持高效范围查询。

通过散列函数将关键字映射到存储位置，平均 $O(1)$；需处理冲突和装填因子。

散列查找性能取决于装填因子α、散列函数和冲突处理方法，α越大冲突越多。

查找的基本概念包括查找表、关键字、ASL（平均查找长度）等核心术语。

红黑树是近似平衡的BST，满足5条性质，插入删除最多旋转3次，比AVL树调整代价低。

字符串模式匹配是在主串中查找模式串的位置，朴素法O(mn)，KMP法O(m+n)。

各查找算法适用场景不同，需根据数据特征（有序性、动态性、存储方式）选择。

直接插入排序将元素逐个插入已排序序列的正确位置，O(n²)，稳定，对近乎有序数据高效。

希尔排序按递减增量分组进行插入排序，突破O(n²)，不稳定，时间约O(n^1.3)。

冒泡排序相邻元素两两比较交换，每趟将最大元素"冒泡"到末尾，O(n²)，稳定。

分治：选枢轴分区，左小右大。平均 $O(n\log n)$，最坏 $O(n^2)$，空间 $O(\log n)$。

简单选择排序每趟选最小元素放到前面，比较次数固定n(n-1)/2，不稳定。

堆排序利用堆的性质选择最值，建堆O(n)，排序O(n log n)，不稳定，原地排序。

归并排序将序列递归二分再合并，O(n log n)，稳定，需O(n)辅助空间。

基数排序按位分配收集，不基于比较，时间O(d(n+r))，稳定，适合关键字位数少的情况。

外部排序用于数据量超过内存的情况，核心是多路归并，用败者树和置换选择优化。

排序的基本概念包括稳定性、内部/外部排序、基于比较排序的下界Ω(n log n)。

折半插入排序用折半查找确定插入位置，比较次数O(n log n)但移动次数仍O(n²)，稳定。

各排序算法在时间、空间、稳定性、适用场景上各有优劣，需综合选择。

计算机经历电子管、晶体管、集成电路、超大规模集成电路四代发展。

计算机性能指标包括CPI、MIPS、主频、CPU执行时间等，CPU时间=IC×CPI×T。

冯·诺依曼结构的核心是存储程序概念，由运算器、控制器、存储器、输入和输出五部分组成。

计算机系统分为多个层次，从硬件到应用层，通过编译/解释实现层间转换。

计算机系统由硬件和软件组成，软件分为系统软件和应用软件。

计算机硬件由CPU、主存、I/O设备通过总线连接构成，CPU=ALU+CU+寄存器组。

软件和硬件在逻辑功能上等价，固件是固化在ROM中的软件，介于软硬件之间。

计算机按存储程序方式工作，执行"取指→译码→执行"的指令周期循环。

定点数用固定小数点位置表示数值，分为定点整数和定点小数，补码表示范围最大。

浮点数用S×M×R^E表示，IEEE 754单精度32位(1+8+23)，双精度64位(1+11+52)。

$n$ 位补码表示范围 $[-2^{n-1}, 2^{n-1}-1]$，加减统一处理。

数制转换是不同进位制之间的相互转换，BCD码用4位二进制表示一位十进制。

原码直接表示，反码符号位不变其余取反，补码=反码+1，补码运算最方便。

补码加减运算统一为加法，溢出判断用双符号位法或进位法(C_n⊕C_{n-1})。

定点数乘法有原码一位乘和Booth补码乘法，硬件用移位和加法实现。

定点数除法有恢复余数法和加减交替法(不恢复余数法)，商逐位确定。

IEEE 754浮点数由符号位、阶码(移码)、尾数(原码)组成，隐含最高位1。

浮点数加减运算步骤：对阶→尾数加减→规格化→舍入→判溢出。

ALU是执行算术和逻辑运算的核心部件，基于加法器实现，有串行和并行进位两种。

无符号整数全部位表示数值，n位范围[0, 2^n-1]，溢出时高位丢失。

带符号整数用补码表示，算术移位保持符号位，符号扩展高位补符号位。

标志位CF/OF/ZF/SF由ALU运算自动生成，OF=C_n⊕C_{n-1}判断有符号溢出。

阵列乘法器用组合逻辑并行计算，迭代除法器逐位产生商，硬件结构规整。

直接映射 ($B \bmod C$) / 全相联 / 组相联，权衡命中率和比较器数量。

存储器按介质分为半导体/磁/光存储器，按存取方式分为RAM/ROM/SAM/DAM。

主存由存储体、MAR、MDR组成，存储周期=存取时间+恢复时间，带宽=数据宽度/周期。

主存扩展通过位扩展(加宽字长)、字扩展(增加单元数)或字位同时扩展实现。

Cache利用局部性原理，命中率h下平均访问时间=h×tc+(1-h)×tm，多级Cache提高性能。

Cache替换算法决定淘汰哪个块，LRU最常用，FIFO可能Belady异常，随机最简单。

Cache写策略解决Cache与主存数据一致性问题，写回法性能好，写直达法实现简单。

虚拟存储器用磁盘扩展主存容量，通过页表实现虚拟地址到物理地址的转换。

多模块存储器通过交叉编址实现并行访问，低位交叉可提高带宽至m倍。

SRAM用触发器存储速度快用于Cache，DRAM用电容存储需刷新用于主存。

Flash存储器是非易失性半导体存储器，写前需擦除，有擦写次数限制。

CPU通过地址总线、数据总线和控制总线与主存连接，总线宽度决定寻址和传输能力。

磁盘由盘面、磁道、扇区组成，访问时间=寻道时间+旋转延迟+传输时间。

SSD基于Flash芯片，无机械部件，随机读写快，但有写放大和寿命限制问题。

指令由操作码和地址码组成，按地址码个数分为零/一/二/三地址指令，可用扩展操作码。

寻址方式决定如何获取操作数，常见有立即、直接、间接、寄存器、变址、基址寻址。

CISC指令复杂数量多用微程序实现，RISC指令简单定长用硬布线实现适合流水线。

指令系统(ISA)是软硬件接口，定义了指令格式、数据类型、寻址方式和寄存器组织。

大端模式高字节存低地址，小端模式低字节存低地址；数据对齐提高访问效率。

编译器将高级语言翻译为汇编，汇编器翻译为机器码，链接器合并目标文件生成可执行文件。

if-else语句通过比较指令和条件跳转指令实现，编译器生成CMP+BEQ/BNE序列。

for/while循环通过条件判断+回跳实现，编译器可能将循环转为do-while形式优化。

函数调用通过CALL/RET指令实现，栈帧保存返回地址、参数、局部变量和寄存器现场。

中断是CPU暂停当前程序转去处理紧急事件的机制，通过中断向量表找到处理程序入口。

CPU由运算器(ALU+寄存器)和控制器(CU+PC+IR)组成，负责取指、译码、执行指令。

指令周期=取指+译码+执行(+访存+写回)，一个指令周期包含若干机器周期和时钟周期。

数据通路是数据在功能部件间传送的路径，有专用通路和总线型两种组织方式。

微程序控制器将指令执行过程用微指令序列描述，存储在控制存储器(CM)中，灵活但较慢。

硬布线控制器用组合逻辑电路直接产生控制信号，速度快但设计复杂不易修改。

指令流水线将指令执行分为多个阶段并行处理，理想加速比=流水段数k。

流水线冒险包括结构冒险(资源冲突)、数据冒险(数据依赖)和控制冒险(分支)。

异常是CPU内部产生的(同步)，中断是外部设备产生的(异步)，都通过向量表处理。

超标量处理器每周期发射多条指令，动态流水线支持乱序执行，提高ILP。

多处理器包括SIMD/MIMD/多核/SMT等形式，共享内存需要Cache一致性协议。

总线是连接各部件的公共通信线路，分为数据总线、地址总线和控制总线。

总线仲裁解决多个设备争用总线的问题，分为集中式(链式/计数器/独立请求)和分布式。

总线定时方式决定数据传输的同步方式，分为同步、异步和半同步三种。

常见总线标准包括ISA、PCI、PCIe、USB等，各有不同的带宽和应用场景。

总线事务是一次完整的总线操作过程，包括请求、仲裁、寻址、数据传输和结束五个阶段。

总线性能指标包括总线宽度、时钟频率和带宽，带宽=宽度×频率/每次传输周期数。

I/O接口是CPU与外设之间的桥梁，负责数据缓冲、格式转换、状态管理和地址译码。

程序查询方式CPU主动轮询设备状态，简单但CPU利用率低，适合慢速设备。

中断方式设备就绪后主动通知CPU，CPU可在等待期间执行其他程序，效率高于查询。

DMA方式由DMA控制器直接管理内存与设备间的数据传输，CPU只在开始和结束时介入。

通道是独立的I/O处理器，执行通道程序完成复杂I/O操作，进一步解放CPU。

I/O端口是接口中的寄存器，编址方式分为统一编址(内存映射)和独立编址(I/O映射)。

中断响应过程：关中断→保存断点→识别中断源→转中断服务程序；处理完后恢复现场返回。

多重中断允许高优先级中断打断低优先级中断服务，通过中断屏蔽字控制嵌套关系。

DMA控制器包含MAR、WC、DAR、CR等寄存器，支持停止CPU/周期窃取/交替访存三种传送方式。

操作系统是管理硬件资源、提供用户接口的系统软件，是硬件之上的第一层软件。

操作系统四大特征：并发(宏观同时)、共享(资源共用)、虚拟(物理变逻辑)、异步(不可预知)。

OS主要功能包括进程管理、内存管理、文件管理、设备管理和用户接口。

系统调用是用户程序请求OS内核服务的机制，通过trap指令从用户态切换到内核态。

中断是外部异步事件，异常是内部同步事件；两者都会导致CPU从用户态转入内核态。

OS经历批处理、多道程序、分时、实时等发展阶段，每个阶段解决不同的核心问题。

CPU有用户态和内核态两种运行模式，特权指令只能在内核态执行，通过中断切换模式。

OS结构有宏内核(整体式)和微内核两大类，宏内核性能好，微内核可靠性好。

操作系统引导是从加电到OS内核加载完成的过程，经历BIOS/UEFI→引导程序→内核加载。

虚拟机通过软件模拟硬件环境，分为Type-1(裸金属)和Type-2(宿主型)两类。

三态：就绪/运行/阻塞；阻塞不能直接变运行，必须先唤醒为就绪。

PCB是进程存在的唯一标志，包含PID、状态、PC、寄存器、内存信息、调度信息等。

进程是程序的一次执行过程，具有动态性、并发性、独立性和异步性。

进程控制通过原语实现创建(fork)、终止(exit)、阻塞(block)、唤醒(wakeup)等操作。

进程通信方式有共享内存(最快)、消息传递(最常用)和管道(半双工字节流)。

线程是CPU调度的基本单位，同一进程的线程共享地址空间和资源，切换开销小。

线程实现分为用户级线程(ULT)和内核级线程(KLT)，映射模型有多对一、一对一、多对多。

进程间通信的具体机制包括共享内存、消息传递、管道和信号，各有适用场景。

处理机调度分为高级(作业)、中级(内存)和低级(进程)三个层次，低级调度最频繁。

FCFS按到达顺序调度，非抢占，简单公平但对短作业不利，有护航效应。

SJF选择服务时间最短的作业优先执行，平均等待时间最优，但可能饿死长作业。

HRRN综合考虑等待时间和服务时间，响应比=(等待+服务)/服务，兼顾长短作业。

时间片轮转让就绪进程轮流使用CPU各一个时间片，适合分时系统，时间片大小是关键。

优先级调度选择优先级最高的进程执行，分静态和动态优先级，可能导致饥饿。

多级反馈队列设置多个优先级递减的队列，时间片递增，兼顾响应时间和吞吐量。

多处理机调度需要考虑负载均衡和处理器亲和性，可采用全局队列或每处理器队列。

上下文切换保存当前进程的寄存器状态并恢复下一个进程的状态，是纯开销。

同步是协调进程执行顺序，互斥是保证临界资源同一时刻只被一个进程访问。

临界区是访问临界资源的代码段，进入前需检查，遵循互斥、有空让进、有限等待原则。

信号量通过P(wait)和V(signal)操作实现同步互斥，P减1可能阻塞，V加1可能唤醒。

管程将共享数据和操作封装在一起，同一时刻只允许一个进程在管程内执行。

经典同步问题包括生产者-消费者、读者-写者、哲学家进餐，用信号量解决。

死锁是多个进程互相等待对方持有的资源而永远阻塞，需同时满足四个必要条件。

死锁预防通过破坏四个必要条件之一来防止死锁发生，但可能降低资源利用率。

死锁避免在资源分配前判断是否安全，银行家算法通过寻找安全序列来决定是否分配。

死锁检测用资源分配图简化判断是否死锁，解除方法有终止进程和资源剥夺。

软件实现互斥有Peterson算法等，通过共享变量和忙等待实现，不需要硬件支持。

硬件实现互斥有中断屏蔽、TestAndSet和Swap指令，原子操作保证不被打断。

锁是最基本的互斥机制，自旋锁忙等待适合短临界区，互斥锁阻塞等待适合长临界区。

条件变量配合互斥锁使用，wait释放锁并阻塞，signal/broadcast唤醒等待的线程。

分页将内存和进程都划分为固定大小的页/页框，通过页表实现地址转换，有内部碎片。

分段按逻辑意义划分为段(代码段/数据段等)，段长可变，有外部碎片，便于共享保护。

程序装入方式有绝对装入、可重定位装入和动态运行时装入，链接分静态和动态。

连续分配将进程放在连续内存区域，有单一连续、固定分区和动态分区三种方式。

分页存储管理通过页表实现地址转换，多级页表解决页表过大问题，TLB加速查表。

分段存储管理以段为单位分配内存，段表记录各段基址和长度，支持共享和保护。

段页式管理先分段再分页，兼具分段的逻辑性和分页的内存利用率，地址转换需三次访存。

内存管理负责地址转换、内存分配回收、内存保护和内存共享等基本功能。

FIFO 可能出现 Belady 异常；LRU/OPT 属栈式算法不会。

虚拟内存基于局部性原理，让程序使用比物理内存更大的地址空间，按需调入页面。

页面置换算法决定淘汰哪个页面，OPT最优但不可实现，LRU近似最优，FIFO有Belady异常。

页面分配策略决定给进程分配多少页框，有固定分配和可变分配，配合局部或全局置换。

请求分页系统在缺页时产生缺页中断，从外存调入所需页面，是虚拟内存的核心机制。

内存映射文件将文件映射到进程地址空间，通过内存访问方式读写文件，支持共享内存。

页框分配决定给进程多少物理页框，分配过少会频繁缺页(抖动)，过多浪费内存。

影响虚拟存储器性能的因素包括页面大小、TLB、页表组织和抖动，可通过多种方法改进。

索引分配为每个文件建立索引块，索引块中存放所有数据块的磁盘块号，支持随机访问。

FAT文件分配表将链接指针集中存放在一张表中，整个FAT常驻内存，支持随机访问。

文件保护通过访问控制列表(ACL)或能力表实现，Unix用rwx三类权限×三类用户。

文件系统实现包括引导块、超级块、inode区和数据区，超级块记录文件系统元信息。

文件是具有符号名的一组相关信息的集合，文件系统负责管理外存上的文件。

目录结构从单级发展到树形结构，树形目录通过路径名唯一标识文件。

文件共享通过硬链接(共享inode)或软链接(存路径名)实现，需要引用计数管理。

空闲空间管理方法有位图法、空闲链表法、成组链接法等，位图法最常用。

VFS是文件系统的抽象层，通过统一接口支持多种不同的文件系统共存。

inode存储文件元数据(大小、权限、时间、块指针等)，文件名存在目录项中不在inode中。

文件基本操作包括创建、删除、打开、关闭、读、写、定位等，打开后通过文件描述符访问。

文件逻辑结构分为无结构(字节流)、定长记录和变长记录文件，影响检索方式。

文件物理结构决定文件数据在磁盘上的存放方式，有连续、链接和索引三种分配方式。

目录操作包括创建、删除、搜索、列出内容、重命名和遍历目录树。

硬链接共享inode不能跨文件系统，软链接存路径名可以跨文件系统但可能悬空。

文件系统全局结构包括MBR、分区表、引导块、超级块、位图、inode表和数据块区。

文件系统挂载将一个文件系统关联到目录树的某个挂载点，实现统一的命名空间。

DMA(直接内存访问)由DMAC控制数据在内存和设备间直接传输，CPU只在开始和结束时介入。

设备驱动程序是OS中直接控制硬件设备的软件模块，向上提供统一接口，向下操作硬件。

磁盘调度算法决定磁头移动顺序，SCAN(电梯算法)和C-SCAN是常用算法。

I/O硬件包括设备控制器和设备本身，控制器通过寄存器与CPU交互。

I/O控制方式从程序查询到中断到DMA逐步减少CPU参与度，提高系统效率。

缓冲技术用于匹配CPU和设备的速度差异，有单缓冲、双缓冲和循环缓冲。

SPOOLing技术用软件模拟脱机I/O，将独占设备改造为共享设备，典型应用是打印机。

设备分配根据设备类型(独占/共享/虚拟)和分配策略将设备分配给请求的进程。

I/O软件分为用户层、设备无关层、驱动层和中断处理层四个层次，各层功能不同。

I/O应用程序接口分为块设备接口、字符设备接口和网络设备接口，提供阻塞/非阻塞模式。

设备驱动程序接口定义了驱动必须实现的标准函数集，使OS能统一管理不同设备。

磁盘物理格式化划分扇区，逻辑格式化建立文件系统结构，分区将磁盘划分为独立区域。

SSD无机械部件读写快，但有写放大和寿命限制，磨损均衡算法延长使用寿命。

计算机网络是将地理上分散的计算机通过通信线路互连，实现资源共享和信息传递的系统。

分层模型将网络功能划分为若干层次，每层只与相邻层交互，通过接口提供服务。

协议由语法、语义和时序三要素组成；服务分为面向连接和无连接两种。

网络性能指标包括带宽、时延(发送+传播+排队+处理)、吞吐量、时延带宽积和利用率。

计算机网络按覆盖范围分为LAN/MAN/WAN，按拓扑分为星形/总线/环形/网状。

OSI七层模型是理论标准，TCP/IP四层模型是实际使用的Internet协议体系。

信道复用技术让多个信号共享同一信道，有频分(FDM)、时分(TDM)、波分(WDM)和码分(CDM)。

数字数据的编码方式有NRZ、曼彻斯特编码和差分曼彻斯特编码，各有自同步特性。

物理层定义了机械、电气、功能和过程特性，负责在物理介质上传输原始比特流。

数据通信基础包括信号、信道、带宽等概念，通信方式分为单工、半双工和全双工。

数字数据可编码为数字信号或调制为模拟信号(ASK/FSK/PSK/QAM)进行传输。

传输介质分为有线(双绞线/同轴电缆/光纤)和无线(无线电/微波/红外)两大类。

物理层设备有中继器(放大信号延长距离)和集线器(多端口中继器，共享带宽)。

奈奎斯特定理给出无噪声信道容量C=2W·log₂V，香农定理给出有噪声信道极限C=W·log₂(1+S/N)。

电路交换建立专用通路延迟小但利用率低，分组交换存储转发利用率高但有延迟。

数据报方式每个分组独立路由可能乱序，虚电路方式先建立逻辑连接保证有序。

CSMA/CD载波监听多路访问/冲突检测，用于以太网，最小帧长=2×传播时延×数据速率。

数据链路层负责相邻节点间的可靠帧传输，功能包括组帧、差错控制、流量控制和访问控制。

组帧方法有字符计数法、字节填充法、比特填充法和违规编码法，确定帧的边界。

差错控制通过检错码(奇偶校验/CRC)发现错误，通过纠错码(海明码)纠正错误。

流量控制防止发送方过快，滑动窗口机制同时实现流量控制和可靠传输。

介质访问控制解决多个节点共享信道的问题，分为信道划分、随机访问和轮询三类。

以太网是最广泛使用的局域网技术，使用CSMA/CD，MAC地址48位，帧长64-1518字节。

广域网使用点对点链路，PPP协议是最常用的广域网数据链路层协议。

链路层设备有网桥和交换机，交换机通过学习MAC地址表实现按端口转发，隔离冲突域。

SR只重传出错的帧，接收方缓存失序帧，发送窗口和接收窗口都≤2^(n-1)。

CRC是最常用的检错码，海明码可以纠正1位错误，检错能力由海明距离决定。

停止等待协议发一帧等一个ACK，简单但信道利用率低，利用率=Tframe/(Tframe+2Tprop+Tack)。

GBN允许连续发送多帧，出错时从出错帧开始全部重传，发送窗口≤2^n-1。

信道划分将共享信道按频率/时间/波长/码字分为多个子信道，各用户独占子信道无冲突。

随机访问协议允许站点随时发送，可能冲突，包括ALOHA、CSMA及其变体。

令牌传递协议中令牌在环上循环，持有令牌的站才能发送数据，无冲突但有等待延迟。

IEEE 802.11无线局域网使用CSMA/CA避免冲突，用RTS/CTS解决隐藏终端问题。

VLAN通过交换机端口或802.1Q标签将物理LAN划分为多个逻辑LAN，隔离广播域。

32 位分网络号和主机号，掩码划分子网；网络地址 = IP AND 掩码。

网络层负责不同网络间的分组转发和路由选择，核心协议是IP。

路由算法分为距离向量(Bellman-Ford)和链路状态(Dijkstra)两大类，各有优缺点。

层次路由将Internet划分为自治系统(AS)，AS内用域内路由协议，AS间用域间路由协议。

IPv4地址32位，分为网络号和主机号，有A/B/C/D/E五类，私有地址不在Internet上路由。

IPv6地址128位，简化了头部，取消校验和和分片字段，支持即插即用。

ARP将IP地址解析为MAC地址，通过广播请求单播应答，ARP缓存加速后续查询。

ICMP用于报告网络错误和提供诊断信息，ping用回送请求/应答，traceroute用TTL超时。

NAT将私有IP地址转换为公有IP地址，NAPT还转换端口号，解决IPv4地址不足问题。

VPN利用公共网络建立加密隧道实现安全的私有通信，常用IPsec协议保护数据。

SDN将网络控制平面与数据平面分离，由集中式控制器统一管理网络转发策略。

网络层拥塞控制防止网络过载，分为开环(预防)和闭环(检测+恢复)两种策略。

子网划分借用主机位作为子网号，CIDR取消分类用前缀长度表示网络，支持路由聚合。

RIP使用距离向量算法，以跳数为度量(最大15)，每30秒交换路由表，适合小型网络。

OSPF使用链路状态算法和Dijkstra，支持区域划分和多种度量，收敛快适合大型网络。

BGP是域间路由协议，基于路径向量算法，使用TCP连接，考虑策略而非最短路径。

IP组播使用D类地址(224.0.0.0-239.255.255.255)，IGMP管理组成员，组播路由实现高效分发。

移动IP允许移动节点在切换网络时保持IP地址不变，通过家乡代理和外地代理实现。

路由器由输入端口、交换结构、输出端口和路由处理器组成，用最长前缀匹配转发分组。

UDP是无连接不可靠的传输协议，头部仅8字节，适合实时应用如DNS、视频流。

拥塞控制防止过多数据注入网络导致性能下降，TCP通过慢开始、拥塞避免等机制实现。

传输层提供端到端的逻辑通信，通过端口号实现进程间的复用和分用。

UDP数据报由8字节头部和数据组成，头部包含源端口、目的端口、长度和校验和。

面向连接的可靠传输，三次握手四次挥手，序号 32 位，有拥塞控制和流量控制。

TCP报文段头部最小20字节，包含序号、确认号、窗口大小、标志位等关键字段。

TCP三次握手建立连接(SYN→SYN+ACK→ACK)，四次挥手释放连接(FIN→ACK→FIN→ACK)。

TCP通过序号、确认、超时重传和快速重传机制实现可靠传输，保证数据无差错有序不丢失。

TCP流量控制通过滑动窗口机制实现，接收方通过rwnd字段告知发送方可接收的数据量。

TCP拥塞控制经历慢开始(指数增)→拥塞避免(线性增)→快重传→快恢复四个阶段。

端口号16位(0-65535)，分为知名端口(0-1023)、注册端口(1024-49151)和动态端口(49152-65535)。

无连接服务(UDP)不需要建立连接直接发送，面向连接服务(TCP)需要三次握手建立连接。

UDP校验和通过伪首部+UDP头部+数据计算反码求和，IPv4中可选，IPv6中必须。

HTTP是无状态的请求-响应协议，基于TCP，定义了GET/POST等方法和状态码。

网络应用模型有客户端-服务器(C/S)模式和对等(P2P)模式两种基本架构。

DNS将域名解析为IP地址，采用分层命名和分布式数据库，支持递归和迭代查询。

FTP使用两个TCP连接：控制连接(端口21)持久保持，数据连接(端口20)按需建立。

电子邮件系统由MUA、MTA、MDA组成，发送用SMTP协议，接收用POP3或IMAP协议。

WWW由URL(定位)、HTML(表示)和HTTP(传输)三大技术组成，是Internet最重要的应用。

HTTP从1.0(非持久)到1.1(持久+管线化)到2.0(多路复用)到3.0(基于QUIC/UDP)不断演进。

DHCP动态分配IP地址，通过discover→offer→request→ack四步完成，使用UDP端口67/68。

Telnet提供远程终端登录功能使用端口23明文传输，SSH是其加密替代品使用端口22。

P2P模型中每个节点既是客户端又是服务器，具有自扩展性，典型应用有BitTorrent。

SMTP用于发送邮件(端口25)是推协议，POP3用于接收邮件(端口110)是拉协议。