易错易混与冷门考点

补充知识点

原理、适用条件与辨析

头结点不存放有效数据。计算表长、遍历和删除时，起点必须与题设一致；若允许 L 本身为空，还要先做空指针保护。

简短例子

带头结点的空表仍有一个头结点，但有效元素个数为 0。

补充知识点

原理、适用条件与辨析

逆置和删除都会改变链路。先保存 next = p->next，再改链接或释放 p，最后用 next 继续。

简短例子

头插逆置中若先令 p->next = L->next，再用 p = p->next，会回到新链而不是原链。

相关真题：2024 · 第 1 题

补充知识点

原理、适用条件与辨析

不同约定不能混用。牺牲一格的数组长度 M 只能存 M−1 个元素；rear 通常指向下一插入位置。

简短例子

M=5 的牺牲一格循环队列，最大有效容量为 4。

补充知识点

原理、适用条件与辨析

扫描左括号入栈，右括号时栈空或类型不符则失败；扫描结束栈须空。后缀二元运算第一次弹出的是右操作数。

简短例子

([)] 数量相等但嵌套不合法；后缀 a b − 的运算是 a−b。

相关真题：2025 · 第 2 题

408 章节补全

原理、适用条件与辨析

尾插在容量足够时可 O(1)，扩容会产生额外开销。只给下标与只给值的操作成本不同；复杂度必须包含定位。

简短例子

长度 n 的表头插入，需要把原有 n 个元素后移。

408 章节补全

原理、适用条件与辨析

典型 p 后插 q：q->next=p->next，q->prior=p，再更新旧后继 prior 和 p->next。带/不带头结点及空表不同，单独处理边界。

简短例子

有头结点的双向循环空表可令 head->next=head->prior=head。

近期代码批改：中序遍历与加括号条件

原理、适用条件与辨析

根可省最外层括号；括号必须在左递归前打开、右递归后关闭。若题设含一元运算符，应按其孩子约定处理，不能把“仅有右孩子”误当叶子。

简短例子

a+b 的子树应输出 (a+b)，而不是 (a)+(b)。根是乘号时，可输出 (a+b)*c。

代码对照

typedef struct Node {
    char data;
    struct Node *left, *right;
} Node;

void printExpr(const Node *p, int isRoot) {
    if (p == NULL) return;
    int nonLeaf = p->left != NULL || p->right != NULL;
    if (!isRoot && nonLeaf) putchar('(');
    printExpr(p->left, 0);
    putchar(p->data);
    printExpr(p->right, 0);
    if (!isRoot && nonLeaf) putchar(')');
}
/* #include <stdio.h>；调用 printExpr(root, 1)。
   本例结点 data 为单字符，二元或右孩子承载的一元表达式。 */

近期批改：树高与最少结点公式的变量约定

原理、适用条件与辨析

AVL 的左右子树高度差至多 1。最少结点时取高度 h−1 与 h−2；N(0)=0、N(1)=1。B 树或红黑树不能直接套此式。

简短例子

h=3 时普通二叉树可只有 3 个结点，AVL 至少 4 个，满二叉树有 7 个。

补充知识点

原理、适用条件与辨析

中序有序是键值约束，不是高度约束。插入有序序列到普通 BST 可以产生单链。

简短例子

依次插入 1、2、3、4 到普通 BST，可能形成全右链。

相关真题：2024 · 第 7 题

补充知识点

原理、适用条件与辨析

常用约定 tag=0 为孩子、tag=1 为线索，但要以题设为准。把线索当孩子可形成重复访问或环。

简短例子

中序线索树中，右线索可以直接指向中序后继；右孩子则要找其子树的最左结点。

补充知识点

原理、适用条件与辨析

B+ 树叶结点按键值链接，便于范围扫描。m 阶的键数/孩子数约定需看题目，尤其根的下限。

简短例子

查一个很靠近根索引键的记录，B+ 树仍需走到叶结点。

相关真题：2022 · 第 8 题；2025 · 第 8 题

补充知识点

原理、适用条件与辨析

n 个叶结点的二叉哈夫曼树（n>1）有 2n−1 个结点，不含度为 1 的结点。前缀性允许无需分隔符逐字解码。

简短例子

交换某结点左右子树可改变码字，但不改变对应路径长度与 WPL。

相关真题：2022 · 第 5 题；2025 · 第 5 题

408 记忆与概念补充

原理、适用条件与辨析

同一高度下，填满得到最大关键字数，稀疏得到最小关键字数。由两端反解 h，并按整数高度取整。空的失败结点不计入 h；空树另行约定。

简短例子

m=5、h=3：最少 2×3²−1=17 个关键字，最多 5³−1=124 个。n=17 时只能 h=2 或 3；不是唯一高度。

参考：高校 B 树讲义：定义与高度推导

408 记忆与概念补充

原理、适用条件与辨析

内部结点有 k 个关键字就有 k+1 个实际孩子。仅含根的非空树有 1～m−1 个关键字；不能把“非根内部孩子下限”机械套给根或数据叶结点。

简短例子

5 阶 B 树的非根结点至少 2 个关键字；非叶根可以只有 1 个关键字、2 个孩子。

参考：高校 B 树讲义：定义与高度推导

408 记忆与概念补充

原理、适用条件与辨析

n=n₀+n₁+n₂；边数 n−1=n₁+2n₂，联立得到结论。适用于普通二叉树，不要求满或完全；一般多叉树另有关系。

简短例子

只有一条长度 4 的单链：n₀=1、n₂=0，仍满足。

408 记忆与概念补充

原理、适用条件与辨析

完全二叉树最后一层可不满但从左连续排列；最后一个非叶结点编号 ⌊n/2⌋，叶从 ⌊n/2⌋+1 开始。0 起始数组需改为 2i+1、2i+2。

简短例子

n=6：高度 3，叶编号为 4、5、6；结点 3 只有左孩子 6。

408 记忆与概念补充

原理、适用条件与辨析

相邻红结点被禁止，所以红结点数量受黑结点间隔限制。黑高是否计入当前根和 NIL 需按题设，不能直接把不同教材的数字相加。

简短例子

同一条路径可穿插红结点，但不能出现红→红。

408 记忆与概念补充

原理、适用条件与辨析

每次合并使对应子树中的叶子深度增加 1，所以它们的权之和贡献一次。根深度取 0，不能按根为第 1 层的层号直接相乘。

简短例子

叶权 1、2、3：先合并 1+2=3，再合并 3+3=6，WPL=3+6=9。

408 章节补全

原理、适用条件与辨析

先序首元素/后序末元素确定根，中序根位置分左右子树。重复标签可能破坏唯一性；只有一个孩子时先后序不能分辨它在左还是右。

简短例子

两个结点 a→b，b 为左孩子或右孩子，先序都是 ab，后序都是 ba。

408 章节补全

原理、适用条件与辨析

转换保留的是孩子和兄弟关系，二叉树中的度和原树的度不同。原树的先根遍历对应转换后二叉树的先序；原树后根对应中序（按常见约定）。

简短例子

原树根有 3 个孩子，可表示成首孩子和连续右兄弟链，不要求二叉根有 3 个指针。

408 章节补全

原理、适用条件与辨析

名称描述从最低失衡祖先出发经过的两段方向，不是最终旋转方向。旋转只改局部指针，需保持中序顺序；删除可能需要向上继续调整。

简短例子

依次插入 3、2、1，根 3 为 LL 失衡，对 3 右旋使 2 成为局部根。

408 章节补全

原理、适用条件与辨析

根表示集合代表，不一定是某种数值最小顶点。优化后的摊还复杂度近似常数，但不能把任意一次未压缩查找都宣称严格 O(1)。

简短例子

Kruskal 中边两端已属同一集合，加入该边会形成环，可跳过。

408 章节补全

原理、适用条件与辨析

若所有非叶恰为 m 个孩子，则 n=mI+1、叶数 L=(m−1)I+1，I 为非叶数；无此条件不能套。B 树关键字数与树结点数仍是不同量。

简短例子

一棵普通三叉树可以是一条长链，因此高度可为 n，不能套 B 树的对数高度界。

补充知识点

原理、适用条件与辨析

BFS 按层扩展而不比较累计权值。标记通常应在入队时完成，防止同一顶点重复入队。

简短例子

一条直接边权 10，两条间接边各权 1：BFS 边数最少路径的权值却为 10。

相关真题：2025 · 第 6 题

补充知识点

原理、适用条件与辨析

Dijkstra 的已确定最短距离可能被后来负边推翻。Floyd 的 k 必须作为最外层，表示允许的中间顶点集合。

简短例子

含负边且无负环的图可以使用 Floyd；不能只因负边就判它失效。

补充知识点

原理、适用条件与辨析

两种优化目标不同。Prim/Kruskal 用于无向带权图；非连通图得到最小生成森林。负权不会破坏 MST 的适用性。

简短例子

三角形边 AB=2、BC=2、AC=3：MST 可选 AB、BC，但 A 到 C 路径为 4，比直接边 3 长。

补充知识点

原理、适用条件与辨析

关键路径可能有多条。只缩短一条关键路径上的某活动，未必缩短总工期；延长任一关键活动则可能延长工期。

简短例子

两个独立顶点可以任意先后，拓扑序不唯一，但图无环。

相关真题：2022 · 第 7 题；2025 · 第 6 题

408 记忆与概念补充

原理、适用条件与辨析

一条无向边贡献两个端点的度；一条有向边贡献起点出度与终点入度各一次。允许自环时无向自环计度 2，简单图通常不含自环。

简短例子

有向图有 6 条边，所有顶点出度之和为 6，不是 12。

408 章节补全

原理、适用条件与辨析

无向邻接矩阵通常对称；有向邻接表可方便找出边，入边可用逆邻接表；十字链表把入/出链接汇于同一边结点。

简短例子

有向矩阵按 A[i][j] 表示 i→j，则第 i 行关联出边、第 i 列关联入边。

408 章节补全

原理、适用条件与辨析

DFS 栈/递归与 BFS 队列的最大空间通常 O(V)。访问标记不能在每个新起点前清空，否则可能重复；BFS 通常在入队时标记。

简短例子

一个图有两个互不相连的三角形，从第一个三角形出发无法到达另一分量。

408 章节补全

原理、适用条件与辨析

有向图已访问的顶点可能已完成，单纯 visited 无法区分回边。无向图需考虑边模型，含重边时不能仅按顶点父亲排除所有同向连接。

简短例子

DAG 的两个分支汇合到同一已访问点，并不意味着存在环。

408 章节补全

原理、适用条件与辨析

朴素矩阵 Prim 为 O(V²)，邻接表+堆常为 O(E log V)；Kruskal 主要排序 O(E log E)。边权重复可能产生多个同权 MST，不代表不存在解。

简短例子

Prim 不能选两端都在树外的全局最轻边来扩展当前树。

近期算法批改：分区、返回值、递归终止与额外空间

原理、适用条件与辨析

划分方案有不同返回约定，Hoare 分割点不一定是枢轴最终位置，不能混套区间。必须保存枢轴值并保证扫描前进。

简短例子

长度为 1 或全相等数组是必须检查的边界；不缩小区间可能无限递归。

相关真题：2022 · 第 11 题；2024 · 第 8 题

代码对照

int partition(int a[], int low, int high) {
    int pivot = a[low];
    while (low < high) {
        while (low < high && a[high] >= pivot) --high;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}
void quickSort(int a[], int low, int high) {
    if (low >= high) return;
    int p = partition(a, low, high);
    quickSort(a, low, p - 1);
    quickSort(a, p + 1, high);
}
/* 调用 quickSort(a, 0, n-1)。
   此首元素枢轴实现平均 O(n log n)，最坏 O(n²)；
   递归栈平均 O(log n)，最坏 O(n)。 */

补充知识点

原理、适用条件与辨析

常见稳定：直接插入、冒泡、归并、LSD 基数；常见不稳定：希尔、简单选择、堆、快排。稳定性受实现影响。

简短例子

两条记录键都为 5，分别附带 a、b；排序后 a 仍在 b 前才保持该对稳定。

相关真题：2022 · 第 11 题

补充知识点

原理、适用条件与辨析

自底向上建堆中，多数结点接近叶子，调整高度很小。不能把所有结点都按根的高度估计为紧确界。

简短例子

堆只保证父子大小关系，中序遍历并不有序。

相关真题：2024 · 第 9 题

补充知识点

原理、适用条件与辨析

折半减少比较次数不等于减少定位时间。分块索引可折半，但块内通常顺序查找。

简短例子

链表不断找中点，不能直接宣称总时间 O(log n)。

相关真题：2024 · 第 5 题；2025 · 第 7 题

补充知识点

原理、适用条件与辨析

nextval 在回退后字符仍相等时继续跳转，减少重复比较；不能把最长相等前后缀长度直接当所有版本的 next 下标。

简短例子

先写清 i、j 的初值和 j=next[j] 的含义，再推数组；避免差 1。

相关真题：2024 · 第 6 题

补充知识点

原理、适用条件与辨析

结构图的根与额外冠军结点须按题设区分。提高归并路数减少归并趟数和外存 I/O，但比较及缓冲区开销也要考虑。

简短例子

置换选择生成的初始归并段可长于工作区容量，不应按固定块数机械分段。

相关真题：2024 · 第 11 题

408 记忆与概念补充

原理、适用条件与辨析

冲突记录可能被探测到后面的槽，清成空槽会截断探测链。插入可利用删除槽，但必须保证查重和停止规则正确；链地址法删除是另一机制。

简短例子

关键字 A、B 冲突，B 存在 A 后面；删 A 后若查找立即停止，可能漏掉 B。

408 章节补全

原理、适用条件与辨析

前驱是左子树最大值，后继是右子树最小值，它们在原位置至多有一个孩子，便于链接修复。键值与附带记录应一起处理。

简短例子

用右子树最小结点替代后，其原父结点应接上该结点可能存在的右孩子。

408 章节补全

原理、适用条件与辨析

有序顺序查找遇更大的元素可提前失败；折半查找的失败叶/间隙也有不同路径长度。不能未说明均匀概率就直接平均。

简短例子

某元素概率高而位置靠后，会显著提高顺序查找 ASL。

408 章节补全

原理、适用条件与辨析

性能还依赖散列函数与冲突处理。线性探测可在未满时按完整步进找到空位，但可能聚集；二次探测能否覆盖全部槽取决于表长和探测规则。

简短例子

一个被冲突挤到槽 4 的记录，可以与初始散列地址为 4 的另一记录发生冲突。

408 章节补全

原理、适用条件与辨析

直接插入/冒泡对已排序输入可为 O(n)（冒泡须设置早停）；简单选择通常始终 Θ(n²)。递归栈算空间；LSD 基数的每趟分配/收集需稳定。

简短例子

比较排序最坏时间下界 Ω(n log n) 不适用于利用键位数的基数排序。

408 章节补全

原理、适用条件与辨析

若初始 r 段且每趟最多合并 k 段，k≥2 时归并趟数通常为 ⌈log_k r⌉。I/O 次数还看初始生成与末次输出是否计入，不能用趟数代替总读写量。

简短例子

输入近乎升序可产生很长初始段，逆序时可能较短；段长取决于输入。

408 章节补全

原理、适用条件与辨析

同一种逻辑结构可有多种存储方式。算法依赖访问接口和存储代价，不应仅按逻辑关系判断复杂度；ADT 可隐藏具体实现。

简短例子

线性表可用顺序表或链表实现，逻辑上都是线性关系。

408 章节补全

原理、适用条件与辨析

i 每轮翻倍而内层循环 i 次时，总量可为 1+2+4+…=O(n)，不是 O(n log n)。O 是渐近上界，不总代表紧确界；平均、最好、最坏要分开。

简短例子

递归遍历一棵退化树，栈深 h=n，辅助空间为 O(n)。

408 章节补全

原理、适用条件与辨析

若 top 指栈顶，空栈 top=−1，入栈通常 a[++top]=x；若 top 指下一个空位，则 a[top++]=x。函数递归用调用栈，不能省略终止条件。

简短例子

两端共享栈若 top1+1==top2，表示两栈之间无空槽。

408 章节补全

原理、适用条件与辨析

子串是连续字符，子序列可以不连续。朴素匹配失配后需重新尝试位置，最坏 O(nm)；KMP 用模式信息减少回退，O(n+m)。

简短例子

"a b" 长度为 3；"" 为 0；存入 C 数组还要留结束标志位。

408 章节补全

原理、适用条件与辨析

若行下标起点 r₀、列下标起点 c₀，行数 R、列数 C，行优先偏移=[(i−r₀)C+(j−c₀)]L；列优先=[(j−c₀)R+(i−r₀)]L。L 为元素字节数。

简短例子

C 的普通二维数组通常行优先，a[i][j+1] 与 a[i][j] 相差一个元素大小。

408 章节补全

原理、适用条件与辨析

上/下三角、行/列优先、0/1 起始都会改变地址公式。三元组保存行、列、值，顺序不当会影响访问；十字链表提供行链和列链。

简短例子

n 阶对称矩阵存下三角含对角线需 n(n+1)/2 个元素，而非 n²。

近期错题：机器字长及相关宽度

原理、适用条件与辨析

变长指令可以跨多个字；总线可分多次传送一个字。寻址范围取决于地址位数与按字/按字节编址约定。

简短例子

32 位机器并不意味着每条指令均为 32 位，也不意味着所有总线都是 32 位。

近期错题：MSB/LSB 与数值解释

原理、适用条件与辨析

大端低地址存最高有效字节，小端低地址存最低有效字节；一个字节内部的位权不会因大小端而反转。

简短例子

0x12345678：大端低地址为 0x12，小端为 0x78。

相关真题：2025 · 第 15 题

近期错题：有符号与无符号的比较

原理、适用条件与辨析

同等级 signed int 与 unsigned int 常转为 unsigned；若更高等级有符号类型能表示较低等级无符号类型的全部值，则可转为该有符号类型。

简短例子

同宽 int 与 unsigned int 比较：-1 通常转为最大的 unsigned int。不能把这一例推广到所有类型组合。

相关真题：2025 · 第 12 题

补充知识点

原理、适用条件与辨析

补码符号扩展保持数值不变。低位截取只有原值在目标范围内才保持数值；浮点扩精度有不同格式转换规则。

简短例子

8 位补码 11111111 表示 −1，扩为 16 位应为 1111111111111111。

相关真题：2024 · 第 12 题；2025 · 第 12 题

408 记忆与概念补充

原理、适用条件与辨析

正规数=(−1)^s×(1.F)₂×2^(E−127)；非正规非零数=(−1)^s×(0.F)₂×2^(−126)。不要把 E=0 的指数写成 −127。

简短例子

E=0、F=0 表示 ±0；E=255、F=0 表示 ±∞；E=255、F≠0 表示 NaN。

408 章节补全

原理、适用条件与辨析

移码是给真值加偏置；只有特定偏置下才可与补码用翻最高位建立简单关系。IEEE 阶码偏置不是任意普通移码例题的偏置。

简短例子

8 位补码能表示 −128，8 位原码通常不能。

408 章节补全

原理、适用条件与辨析

若要同时实现单错纠正和双错检测，常加整体奇偶位成为扩展海明码。理论能力由最小码距决定：检 d−1 位、纠 ⌊(d−1)/2⌋ 位。

简短例子

翻转两位可能让普通奇偶校验仍满足，而不是一定被检出。

近期批改回顾：补码移位与数值范围

原理、适用条件与辨析

逻辑右移补 0。题目若指定 C 语言而非机器移位，应注意版本和实现规则，不把硬件题的结论无条件套到源语言。

简短例子

8 位补码 −3 算术右移一位常得到 −2，而不是 −1。

近期错题：浮点左规

原理、适用条件与辨析

保持数值不变需要尾数和阶码反向变化。舍入可能再次引起右规，不能只在开始检查阶码范围。IEEE 与题设补码尾数格式的规格化判据不同。

简短例子

尾数左移一位放大 2 倍，阶码减 1 才抵消该变化。

相关真题：2022 · 第 14 题；2025 · 第 13 题

补充知识点

原理、适用条件与辨析

同一位串运算可按有符号或无符号解释。补码加法同号相加结果异号发生有符号溢出；不能仅看最高位进位。

简短例子

8 位 127+1 得位串 10000000：有符号溢出，未产生第 9 位进位。

相关真题：2025 · 第 14 题

补充知识点

原理、适用条件与辨析

单精度可连续精确表示的整数范围通常到 ±2^24；超过后并非所有整数可精确表示。双精度有 53 位有效精度。

简短例子

2^24 可精确表示，但 2^24+1 在单精度中通常不能精确表示。

相关真题：2024 · 第 14 题

408 记忆与概念补充

原理、适用条件与辨析

图采用无符号组合右移模型：M 保存被乘数，Q 初始保存乘数，A 初始为 0；Q₀=1 则 A+M，经 C:A:Q 联合逻辑右移。保留加法进位 C，进行 n 轮，最终 A:Q 是 2n 位乘积。

简短例子

4 位无符号 15×15 需要 8 位保存 225；若丢掉加法进位可能算错。

参考：高校计组讲义：移位加法与除法硬件

408 记忆与概念补充

原理、适用条件与辨析

阵列实现可减少迭代轮次但组合延迟更长、硬件更多；是否一拍完成取决于电路、时钟周期和流水化。不能把算法步骤数直接当任意机器的周期数。

简短例子

同一乘法指令可由组合阵列、多周期迭代或流水化单元实现。

408 记忆与概念补充

原理、适用条件与辨析

Q₋₁ 初始为 0，用相邻位变化编码连续 1。必须保留符号，并给 −M 留出可表示的位宽，尤其 M 为最小负数时；不同教材若写 Q₋₁Q₀，表的方向须转换。 若中间 A 扩成 n+1 位，最终去掉冗余符号扩展位，按题设取 2n 位乘积。

简短例子

Q₀=1、Q₋₁=0 对应 10，所以 A←A−M，不是 A+M。

参考：IIT Kharagpur：Booth 乘法虚拟实验

408 记忆与概念补充

原理、适用条件与辨析

图采用恢复余数的无符号迭代模型：A:Q 左移→A−M→若负则恢复并写商位 0，非负写商位 1。A 需留足试减的额外位，迭代 n 轮，最终 Q 为商、A 为余数。

简短例子

13÷3 的最终商为 4、余数为 1，满足 13=3×4+1。

参考：UC San Diego：乘除法与恢复/不恢复余数

408 记忆与概念补充

原理、适用条件与辨析

无符号标准移位版本：旧 A≥0 时下一轮左移后减 M；旧 A<0 时左移后加 M，再据结果设置商位。若最终 A<0，补加 M 修正。补码有符号算法另看题设。

简短例子

“下一轮用加法替代立即恢复”不等于永远没有任何恢复或末尾校正。

参考：UC San Diego：乘除法与恢复/不恢复余数

408 记忆与概念补充

原理、适用条件与辨析

对双字长被除数/单字长商，也需专门检查商位宽。机器整数除法和浮点除法的异常处理不同，不能混用。

简短例子

8 位补码 −128÷(−1) 的数学商为 128，无法装入 8 位有符号结果。

408 章节补全

原理、适用条件与辨析

位宽固定时结果截取低位，但有符号溢出仍要检查。形成 −B 时注意最小负数边界；借位、进位、OF、符号位不能混称。

简短例子

正数减负数可能正溢出，而不同号相加通常不会有有符号加法溢出。

408 章节补全

原理、适用条件与辨析

两者都执行相同二进制加法，但延迟和硬件代价不同。多级先行进位还按组组织，不能只按全宽线性级数估算。

简短例子

8 位加法的最高位不必在先行结构中等 7 次逐位传播才得到进位。

408 章节补全

原理、适用条件与辨析

对阶尾数右移可能丢位，需保护/舍入/粘滞信息。舍入进位可能需要再次右规；阶码上溢与尾数暂时超范围不同，下溢可能转为非正规数或按题设处理。

简短例子

两个尾数相加超过正规范围，可右移尾数并增加阶码。

近期错题：过程调用、PC 与 RET

原理、适用条件与辨析

“下一条执行的指令”可以是转移目标，而“内存中紧邻的下一条”指顺序后继。即使两个数值恰好相同，也不改变地址来源和指令语义。

简短例子

CALL 的目标可恰好紧邻，但它仍按调用语义执行；RET 通常返回对应调用后的指令。

近期错题：控制部件的组成

原理、适用条件与辨析

IR 不一定在每个执行微操作中变化。ALU 完成运算，控制器生成相应微操作控制信号；具体组成以题设模型为准。

简短例子

指令取出后送入 IR，随后译码；执行期间 PC 可能已指向后继。

相关真题：2025 · 第 19 题

近期批改回顾：寻址与数据通路

原理、适用条件与辨析

直接寻址 EA=A；一次间接寻址 EA=M[A]；基址/变址/相对寻址还需叠加相应寄存器。计算时须区分地址、地址处的指针和最终操作数。

简短例子

一次间接寻址：A=100，M[100]=200，M[200]=7，操作数是 7。

补充知识点

原理、适用条件与辨析

相同 ISA 可由不同处理器实现，性能和内部结构可以不同。某些状态寄存器或扩展特性是否可见仍要看具体 ISA。

简短例子

支持相同指令集的两个 CPU 可以有不同 Cache 和不同主频。

相关真题：2025 · 第 16 题

408 章节补全

原理、适用条件与辨析

多地址指令耗较多地址字段，留给短操作码的位数较少。已使用的短操作码前缀会占用对应的所有更长编码，不可重复计数。

简短例子

一个已分配的 k 位操作码，可排除具有该前缀的 2^(l−k) 个 l 位长编码。

408 章节补全

原理、适用条件与辨析

位移可能有符号，需要扩展。PC 究竟是当前指令地址还是已更新后的顺序后继，要看题设；基址与变址在硬件求和相似，但用途和可变部分不同。

简短例子

数组遍历常改变变址寄存器；程序重定位常调整基址。

408 章节补全

原理、适用条件与辨析

这些是风格特征，不是对所有实现的绝对保证。现代处理器可把复杂指令分解成内部操作；访存、乘除或异常可能使执行时间不同。

简短例子

典型 Load/Store ISA 中算术指令主要在寄存器间运算，访存由专门指令完成。

408 章节补全

原理、适用条件与辨析

控制信号需同时满足总线不冲突、源有效、目标写入、ALU 功能及存储器时序。MAR 送地址、MDR 传数据不能互换；具体寄存器名看题图。

简短例子

实现 R1←R1+R2 可分为 R1→Y、R2与Y运算→Z、Z→R1 等微步骤。

近期批改：Cache 组号、标记与地址拆分

原理、适用条件与辨析

按字节编址且参数为 2 的幂时：低位为块内偏移，中间为组索引，高位为标记。组数=数据容量/(块大小×路数)，不能把路数当组数。

简短例子

两块映射到同一组，还需要比较标记；组相同不代表命中。

相关真题：2022 · 第 16 题

补充知识点

原理、适用条件与辨析

两套策略分别回答不同问题。写回通常需要脏位；替换干净块无需写回。题目给出组合时必须按组合执行。

简短例子

写回且写分配：写缺失先调块，修改后置脏，替换脏块再写回。

相关真题：2024 · 第 16 题

补充知识点

原理、适用条件与辨析

按字节编址时 n 位地址可表示 2^n 个字节地址。按字编址则表示 2^n 个字，容量还需乘每字字节数。

简短例子

MAR 为 24 位而 MDR 为 32 位，不矛盾；不能用 MDR 位数直接计算地址容量。

408 章节补全

原理、适用条件与辨析

DRAM 容量密度高、常作主存，SRAM 较快常作 Cache。刷新并非 CPU 逐条执行读写指令完成；读写周期与刷新开销要区分。

简短例子

断电后普通 SRAM/DRAM 数据通常丢失，不能因 SRAM 不刷新就认为它非易失。

408 章节补全

原理、适用条件与辨析

总片数可按目标总位数/单片总位数求，但仍需按每组位宽、组数和地址线划分连线。读写控制、地址输入可共用，数据线和片选要按方案组织。

简短例子

8K×8 的芯片构成 16K×16：每组 2 片位扩展，2 组字扩展，共 4 片。

408 章节补全

原理、适用条件与辨析

并行访存受模块忙闲、周期和发起间隔限制。对步长与模块数有规律的访问，低位交叉也可能持续冲突，不能保证任意访问都满带宽。

简短例子

4 模块低位交叉时，地址 0、1、2、3 分别去模块 0、1、2、3。

408 章节补全

原理、适用条件与辨析

直接映射比较少但冲突限制强；全相联查找代价大，索引字段可无；组相联折中。每一路保存自身标记与状态；命中需有效位和标记匹配。

简短例子

两主存块映同一直接行会互相替换；组内有多个路时可同时驻留。

408 章节补全

原理、适用条件与辨析

TLB 可能包含地址空间标识以区分进程；切换时如何处理看实现。页框号与页内偏移拼出物理地址，缺页由硬件检测并转交 OS 处理。

简短例子

同一虚拟页号在两个进程中可映射到不同物理页框。

408 章节补全

原理、适用条件与辨析

突发传输常首次延迟较长，随后连续传多字，摊薄地址/访问开销。刷新、行命中/未命中等可改变 DRAM 时序，题目必须明确计时模型。

简短例子

总线有数据阶段不代表主存每个周期都能接受独立访问，仍受存储周期约束。

近期批改回顾：无转发流水线与指令相关

原理、适用条件与辨析

ALU 结果可提前转发；典型五段流水线的紧邻 load-use 仍可能停一拍。无转发题必须等结果可读，不能擅自套转发时序。

简短例子

同一周期能否先写后读寄存器文件，必须看题设。

相关真题：2024 · 第 19 题；2025 · 第 19 题

补充知识点

原理、适用条件与辨析

机器指令描述软件层操作，微指令描述一个微周期的控制操作。水平型允许较多并行控制，垂直型编码更紧凑、译码更多。

简短例子

取指微程序可由多条微指令组成，并由多种机器指令共享。

相关真题：2024 · 第 13 题

408 记忆与概念补充

原理、适用条件与辨析

比较时要同时考虑三个因子。总线时钟频率乘每拍传输次数才是传输频率，带宽再乘每次传送字节数；MT/s 与 MHz 不能无条件互换。

简短例子

同一程序若机器 A 的 CPI 降低但时钟周期变大，CPU 时间不一定缩短。

408 章节补全

原理、适用条件与辨析

间接寻址可能增加访存阶段；中断响应含保存断点及转向服务入口等操作。不要把存储周期、机器周期、指令周期都视为固定相等。

简短例子

多周期 CPU 一条访存指令可以由多个时钟周期组成。

408 章节补全

原理、适用条件与辨析

非流水同模型为 nkτ，理想加速比 nk/(k+n−1)，n 大时趋 k。锁存延迟、最长阶段、停顿和填充/排空降低实际收益。

简短例子

k=5、n=1 时理想加速比为 1，不是 5。

近期批改：中断响应周期遗漏

原理、适用条件与辨析

硬件完成哪些保存操作、软件完成哪些操作由体系结构决定。中断屏蔽与中断优先级也不同，不能只按服务程序条数估算。

简短例子

题目另给“响应需要若干周期”，若不包含在服务时间中，就要单独计入。

相关真题：2024 · 第 21 题

补充知识点

原理、适用条件与辨析

DMA 可争用总线或访存周期，并在完成/异常时中断 CPU。降低 CPU 搬运负担不等于传送过程对 CPU 没有影响。

简短例子

CPU 设置缓冲区地址、长度和方向后，DMA 按配置传送。

相关真题：2024 · 第 22 题

补充知识点

原理、适用条件与辨析

两种次序可以不同。现场保存、断点保存和开/关中断的时机必须按题设区分，不能只比较中断号大小。

简短例子

某源硬件响应优先级高，但服务时可被另一源打断，说明处理次序另有设置。

相关真题：2024 · 第 21 题

408 章节补全

原理、适用条件与辨析

查询方式检查状态，控制命令配置设备，数据寄存器承担实际传送。设备物理执行由控制器协作，CPU 不能把所有端口都当普通可缓存内存访问。

简短例子

统一编址下，普通访存指令可按规定访问 I/O 区域，但会占地址范围。

408 章节补全

原理、适用条件与辨析

各模式在 CPU 停顿、控制开销与传输速度间折中。CPU 初始化 DMA 和处理中断仍有开销；DMA 请求/总线授权不等于中断响应时机。

简短例子

周期挪用让 CPU 暂失一个或一些访存周期，而不是必然中止整个程序到整块全部传完。

408 章节补全

原理、适用条件与辨析

不同架构可能直接编码入口或有不同表结构，以题设为准。硬件识别请求、形成向量地址、保存断点与跳转是不同动作；软件继续保存通用现场。

简短例子

向量地址为 100，M[100]=200，则服务入口可为 200，不是 100。

408 章节补全

原理、适用条件与辨析

现代处理器可能主存统一而指令/数据 Cache 分开，不能只凭一级 Cache 分离就断言整个系统纯哈佛。软硬件共同决定执行行为。

简短例子

一条机器指令在存储器中也以二进制编码保存。

408 章节补全

原理、适用条件与辨析

具体工具链可合并阶段，但职责仍需区分。目标文件未必已经解析全部外部符号；装入与执行时的动态链接也可另发生。

简短例子

调用库函数的符号引用可在链接阶段与库模块对应。

408 章节补全

原理、适用条件与辨析

链式次序常赋予固定优先级且对链路故障敏感；计数器起点可影响公平；独立请求可更灵活但控制线更多。不能仅凭名称判断所有具体策略。

简短例子

固定高优先级设备不断请求可能使低优先级长期等待。

408 章节补全

原理、适用条件与辨析

峰值带宽通常按每秒有效传输次数×每次字节数。地址阶段、等待周期、仲裁和协议开销会降低实际吞吐；时钟频率与双倍/多倍传输率要分开。

简短例子

首拍发地址、后几拍等存储器时，不能把每拍都算成数据传输。

近期错题：多任务与并行

原理、适用条件与辨析

单核普通执行流同一时刻仅执行一个线程，I/O 与 CPU 仍可重叠。多核提供多个硬件执行资源；逻辑处理器和物理芯片数量也不能直接等同。

简短例子

单核轮流运行 A、B，两者都有进展但不必在同一时刻执行。

补充知识点

原理、适用条件与辨析

用户线程/内核线程的管理方式另需区分。一个进程可含多个线程，线程局部变量与共享变量不能仅靠变量名判断。

简短例子

两个线程各自栈上的 x 不一定是同一个对象；访问同一全局 x 才可能竞争。

相关真题：2024 · 第 28 题

补充知识点

原理、适用条件与辨析

运行→就绪可由时间片用尽或被抢占造成。阻塞进程缺少执行条件，不能靠给它 CPU 就解决等待。

简短例子

I/O 完成后先进入就绪队列，可能仍需等待 CPU。

补充知识点

原理、适用条件与辨析

父子都从 fork 返回处继续，返回值不同。普通内存修改不会自动修改对方的变量；共享映射是另一个机制。

简短例子

同一继承文件的偏移可能共享，但局部变量 x 的写入通常各自独立。

408 章节补全

原理、适用条件与辨析

进程切换需保存/恢复寄存器及必要管理状态，不是复制全部内存。程序为静态代码，进程为运行实例，同一程序可对应多个进程。

简短例子

多个进程可执行同一可执行文件，但有各自状态与逻辑地址空间。

408 章节补全

原理、适用条件与辨析

不同系统有不同父子终止策略，不能把级联终止作为所有系统必然行为。子进程继承与共享资源也要按规则区分。

简短例子

fork 后子进程可 exec 新程序，但典型 Unix 中其 PID 不因 exec 本身变化。

408 章节补全

原理、适用条件与辨析

用户级切换可低开销，但不是所有阻塞都等价于整个进程被阻塞，须看是否陷入内核及映射方式。多核并行需要多个可并行内核执行实体。

简短例子

多对一模型若一个线程进行阻塞系统调用，可影响同进程其他用户线程运行。

408 章节补全

原理、适用条件与辨析

相同虚拟地址可映不同物理页。普通匿名管道与命名管道在使用范围上不同，读写端关闭、空/满等待影响行为。通信通道不自动提供所有并发互斥。

简短例子

两个进程共享一页存数据，生产消费双方仍需约定有效数据与访问顺序。

近期错题：时钟中断

原理、适用条件与辨析

时钟中断是外部异步中断。时间片可能由多个时钟滴答组成；内核处理完中断后也可继续原任务。

简短例子

时间片尚未用完且没有更高优先级任务，就可能继续运行当前进程。

近期批改：动态优先级漏计 CPU 时间

原理、适用条件与辨析

不同系统的优先级编号方向不同。到达、抢占、运行、阻塞等事件可能改变状态，静态排序不能替代过程推演。

简短例子

若优先数含 CPU 使用项，运行中的进程会随 CPU 时间积累而变化。

补充知识点

原理、适用条件与辨析

等待越久，响应比越大，能缓解长期等待。绝对“不会饥饿”仍需结合有限作业或到达假设，不能对任何负载无条件保证。

简短例子

一个长作业等待期间不断到来短作业，SJF 可能一直选短作业。

补充知识点

原理、适用条件与辨析

外部中断通常异步；异常与当前指令同步。普通库函数可完全在用户态执行，也可能封装系统调用。发生前模式与处理时模式不能混淆。

简短例子

用户程序访问不存在的页时可以触发缺页异常，而缺页处理程序在内核态执行。

相关真题：2022 · 第 31 题；2024 · 第 23 题

408 章节补全

原理、适用条件与辨析

并非所有 OS 都实现这三层。调度是选择，分派/切换是实施；用户态到内核态转换可仍属于同一进程，不必发生进程切换。

简短例子

系统调用完成后返回原任务，发生模式切换但不一定换进程。

408 章节补全

原理、适用条件与辨析

有 I/O 时等待时间不能无条件用周转−CPU 服务时间，可能还需区分 I/O 等待。题设若是纯 CPU 作业模型，则常用该差值。

简短例子

任务很快显示第一条输出但仍运行很久，响应短不代表周转短。

408 章节补全

原理、适用条件与辨析

RR 片很大时可近似 FCFS，片太小切换开销大。到达、抢占、平局排序和新到任务插入位置改变结果，要明确约定。

简短例子

一个长任务前面只有一个很短任务，SJF 可能先完成短任务以降低平均等待。

408 章节补全

原理、适用条件与辨析

共享或每核就绪队列均可采用；迁移可能损失 Cache 热数据并引入协调开销。任务数相等不代表工作量相等，软/硬亲和的限制也不同。

简短例子

一个 CPU 密集任务与多个短等待任务，数量相同不代表计算负载相同。

近期批改回顾：PV 顺序与遗漏操作

原理、适用条件与辨析

如果持有互斥锁时等待 empty/full，对方可能无法进入缓冲区释放所需资源，形成死锁。每次成功申请都要有对应释放。

简短例子

缓冲区已满，生产者先持有 mutex 再等 empty；消费者无法取得 mutex 去消费。

近期错题：线程变量与执行顺序

原理、适用条件与辨析

局部变量名相同不一定共享；删掉某个线程的变量也不一定修复同步逻辑。应先明确各变量作用域、原子操作和访问顺序。

简短例子

两线程同时读到 x=0，各自写回 1，最终值可能为 1 而不是 2。

补充知识点

原理、适用条件与辨析

经典可重用资源模型中，互斥、占有且等待、不可剥夺、循环等待是死锁的必要条件。破坏其中任一可预防该模型中的死锁。

简短例子

银行家算法拒绝后不安全的请求，是避免风险，并非证明进程已经死锁。

补充知识点

原理、适用条件与辨析

选择是“存在某个可以完成的进程”，不是固定逐号顺序。申请首先检查 Request≤Need、Request≤Available，再试分配并检查安全性。

简短例子

P1 暂不能完成，但 P2 能完成并释放资源，随后 P1 可能满足需要。

408 章节补全

原理、适用条件与辨析

自旋锁等待时忙等，不能无条件说满足让权等待；阻塞型等待可让出 CPU。应区分安全性（不同时进入）与进展/公平性。

简短例子

一把永远无人释放的锁仍可互斥，却不能使等待任务正常推进。

408 章节补全

原理、适用条件与辨析

硬件保证该操作原子不自动保证锁公平或让权等待。关闭中断在单核内核特定场景可防本核打断，但不能仅靠它阻止其他核并发访问。

简短例子

两线程均读到 lock=0 再各写 1，会同时误以为获得锁。

408 章节补全

原理、适用条件与辨析

仅轮流进入可能在另一方不想进入时也阻挡自己。现代硬件/编译器可重排，真实代码还需适当内存语义；408 理论题按给定原子与顺序约定推演。

简短例子

两者同时 flag=true 时，turn 为其中一个提供让步方向。

408 章节补全

原理、适用条件与辨析

Mesa 风格条件等待应在 while 中重查条件，因为唤醒后可能被他人先改变。条件通知不等于保留一个永久许可；不同管程语义需按题设。

简短例子

消费者被唤醒但尚未拿锁前，另一个消费者可能取走唯一数据。

408 章节补全

原理、适用条件与辨析

首读者锁定写资源、末读者释放是一种常见读者优先方案；源源不断读者可能延迟写者。写者优先也可能使读者长期等待，不能只看互斥。

简短例子

读者共享数据只读，但更新 readCount 属于写共享状态，需单独同步。

408 章节补全

原理、适用条件与辨析

限制至多 n−1 人尝试是经典思路，但仍需完整释放路径；资源编号顺序消除循环等待。具体公平性另需验证。

简短例子

5 人同时拿左叉后全等右叉，即使每支叉严格互斥，也仍可能死锁。

408 章节补全

原理、适用条件与辨析

银行家基于最大需求等信息进行避免。预防可能降低利用率；解除要选牺牲者并防重复牺牲造成饥饿。四类策略目的相近但时机不同。

简短例子

统一资源申请顺序是预防；试分配后安全检查属于避免。

408 章节补全

原理、适用条件与辨析

请求边通常进程→资源，分配边资源→进程。多实例还有外部可完成进程释放资源的可能，单纯画环不能给出完整判定。

简短例子

某类型还有一空闲实例可满足等待者，环内进程仍可能继续。

补充知识点

原理、适用条件与辨析

TLB 缓存的是地址转换结果，数据 Cache 缓存的是数据。页表存在位有效时，TLB 不命中仍可直接完成内存访问。

简短例子

页在内存但其映射未进入 TLB，只发生 TLB miss，不发生 page fault。

相关真题：2022 · 第 29 题；2024 · 第 18 题

补充知识点

原理、适用条件与辨析

固定页大小便于物理分配，逻辑段长度可变。段内偏移必须检查段限，不能只加基址。

简短例子

最后一页用不满是内部碎片；空闲段间空洞是外部碎片。

补充知识点

原理、适用条件与辨析

基本 CLOCK 遇访问位 1 清零并继续，遇 0 选择。改进型还考虑修改位，其扫描规则须看题设。

简短例子

两个页面都访问过，CLOCK 可能不保留它们的精确先后次序。

补充知识点

原理、适用条件与辨析

抖动时大量时间花在调页，CPU 利用率可能下降；应考虑减少多道程序度或增加可用页框。工作集大小与窗口和局部性相关。

简短例子

进程刚切换阶段，工作集可能改变，不是永久不变的常数。

相关真题：2022 · 第 30 题

408 记忆与概念补充

原理、适用条件与辨析

先从地址宽度扣除页内偏移，再按能容纳的表项数分各级索引。题设可以让页目录大小与下级页表大小不同，不能擅自平分。

简短例子

32 位地址、4 KiB 页、4 B 页表项：页内偏移 12 位，下级索引 10 位，常见两级结构剩余目录索引 10 位。

408 章节补全

原理、适用条件与辨析

最佳适应可能留下很多小孔洞；连续变长分配主要外部碎片，固定/对齐分配可有内部浪费。伙伴只合并同级且互为伙伴的空闲块，不是任意相邻块。

简短例子

请求 18 单位，伙伴分配可能给 32 单位，剩余部分体现内部浪费。

408 章节补全

原理、适用条件与辨析

LRU 的栈性质使增加页框通常不增缺页，FIFO 不具此保证。最优基于未来信息不作一般在线实现；读序列时命中也可能更新 LRU 次序。

简短例子

FIFO 某序列用更多页框反而更多缺页，是异常，不是计算一定错。

408 章节补全

原理、适用条件与辨析

多进程共享物理内存时，分配策略与替换范围共同影响缺页和抖动。页框不足、访问局部性弱和多道度过高可能叠加；局部/全局是归属范围而非地址距离。

简短例子

全局替换可能使另一进程失去页框，影响其未来访问。

408 章节补全

原理、适用条件与辨析

共享/私有映射影响修改可见性和写回；私有映射可写时复制，不保证修改原文件。建立映射、读页、写回同步等是不同动作，不能只凭“映射”认定已物理加载全部文件。

简短例子

首次读映射区域可能触发缺页，由系统把对应文件页装入内存。

近期批改：FAT 表项下标与链接方向

原理、适用条件与辨析

FAT 集中保存链接信息。文件的逻辑块序号用于决定要走几次链，不等于 FAT 下标。不能把数据块里的内容当链接指针。

简短例子

链 100→106→108：FAT[100]=106，FAT[106]=108，FAT[108]=结束标记。

补充知识点

原理、适用条件与辨析

若编号从 1 开始需调整。位示图通常为每个磁盘块保留一位，其大小与总块数有关，不随当前空闲块数线性变化。

简短例子

每字 32 位，0 起始编号的第 2 字第 3 位对应块号 67。

相关真题：2024 · 第 26 题

补充知识点

原理、适用条件与辨析

文件描述符表、系统打开文件表、inode 与目录项各有作用。硬链接共享同一文件对象；符号链接保存路径。

简短例子

删掉一个硬链接名，另一个硬链接仍可访问同一文件。

相关真题：2024 · 第 29 题

408 记忆与概念补充

原理、适用条件与辨析

若 inode 有 d 个直接、s 个一级、t 个二级指针，最大数据容量为 [d+s(b/p)+t(b/p)²]×b；这是数据字节，不包含索引块自身占用。

简短例子

b=1024 B、p=4 B，则每索引块有 256 项，二级间接可覆盖 256² 个数据块。

408 章节补全

原理、适用条件与辨析

名字与对象分离有助硬链接。打开后用描述符定位打开对象不等于每次读都重走完整路径；缓存命中会改变实际磁盘访问次数。

简短例子

/a/b/c 的打开可能依次解析 a、b、c 的目录项，而非直接按字符串计算数据块号。

408 章节补全

原理、适用条件与辨析

FAT 是链接信息集中化的形式；多级索引的随机定位仍有索引访问开销。最大容量、目录大小和磁盘读次数须按实际结构与缓存条件计算。

简短例子

随机读链末块可能需追踪很多链接，不应直接把逻辑序号加到起始物理块号。

408 章节补全

原理、适用条件与辨析

读取目录和元数据不等于把全部数据加载。用户身份、操作类型、目录搜索权和文件权限可能共同决定访问；硬链接、打开引用和映射分别带来不同共享关系。

简短例子

路径中的某目录无搜索权限时，即使知道目标文件名，也不一定能成功打开。

408 章节补全

原理、适用条件与辨析

缓存脏块、内核缓冲、设备内部缓存的持久化保证不同。关闭文件不等于所有实现中硬件永久保存全部写入；同步语义要看规定。日志也不能替代独立备份。

简短例子

目录项已改但分配表未完全落盘，崩溃可能产生一致性问题，需恢复机制。

补充知识点

原理、适用条件与辨析

SCAN/LOOK 的差别会影响移动距离；C-SCAN/C-LOOK 还需确认回程是否计距离。机制概念与题目计费约定应分开。

简短例子

当前方向上最后请求是 80、磁盘边界是 99：LOOK 可在 80 反向，SCAN 到 99。

相关真题：2024 · 第 32 题

408 章节补全

原理、适用条件与辨析

逻辑设备到物理设备映射、权限、错误处理、缓冲可由不同层承担。单/双/循环缓冲影响并行与等待；中断服务结束时数据常先在内核缓冲，未必已经复制到用户缓冲。

简短例子

键盘驱动处理中断数据后，应用仍可能需通过系统调用取得它。

408 章节补全

原理、适用条件与辨析

平均旋转等待常为半圈，转速单位需转换。调度仍涉及访问模式和设备内部行为；不要把 HDD 的距离模型无条件用于 SSD。

简短例子

转速 7200 rpm 等于 120 圈/s，一圈约 8.33 ms，平均等待约 4.17 ms（均匀位置模型）。

408 章节补全

原理、适用条件与辨析

互斥共享指同一时刻仅允许一个使用者，不是永久独占。虚拟 CPU 靠分时，虚拟内存靠地址映射等；这些术语要结合具体机制解释。

简短例子

打印机可通过互斥或 SPOOLing 供多个进程使用，并不变成多台物理打印机。

408 章节补全

原理、适用条件与辨析

多道程序能在某任务等待 I/O 时运行其他任务。时间片越短不一定越好，切换开销会上升；硬实时截止期违反可能不可接受。

简短例子

交互终端轮流获得 CPU 是分时；工控急迫任务须在期限内完成是实时要求。

408 章节补全

原理、适用条件与辨析

微内核有助隔离和扩展，但跨服务通信/切换带来代价；宏内核可以使用模块化设计，结构风格不等于有没有模块。虚拟机监控器也不等于普通微内核。

简短例子

文件服务放用户进程不代表它不需要内核提供通信与保护机制。

408 章节补全

原理、适用条件与辨析

具体 BIOS/UEFI 流程不同；引导程序属于启动链的一环，不应混同整个 OS。内核建立中断/内存等基础后才能支持用户程序执行。

简短例子

内核从持久存储加载到 RAM，不是 RAM 自己断电保存了整个系统。

补充知识点

原理、适用条件与辨析

加大链路速率减少把比特推入链路的时间，不直接提高介质中的传播速度。还要区分排队和处理时延。

简短例子

光纤长度固定时，从 100 Mb/s 升到 1 Gb/s 不会把传播时延降为原来的十分之一。

相关真题：2024 · 第 33 题

补充知识点

原理、适用条件与辨析

一个限制码元速率与调制等级，一个限制带噪声信道的信息容量。若两者条件均给出，应同时满足；有带通等模型须按题设。

简短例子

信噪比 30 dB 对应线性比 1000，不能把 30 直接代入香农式。

相关真题：2022 · 第 34 题

补充知识点

原理、适用条件与辨析

模 2 除法使用异或，不进位、不借位。r 次生成多项式对应 r 位 CRC；余数为 0 也不能无条件证明绝无差错。

简短例子

某些错误多项式是生成多项式的倍数，可能检测不出。

补充知识点

原理、适用条件与辨析

SR 一般需要发送窗口+接收窗口≤序号空间，避免新旧帧混淆。窗口上限不是实际吞吐率，超时重传策略也不同。

简短例子

3 位序号的等大 SR 窗口最多 4，而 GBN 发送窗口最多 7。

相关真题：2024 · 第 37 题

补充知识点

原理、适用条件与辨析

广播域通常靠 VLAN 或路由器划分。CSMA/CD 属于共享半双工以太网的冲突检测机制；无线通常采用不同机制。

简短例子

两个交换机端口属于同一 VLAN，广播帧仍可被转发到另一端口。

相关真题：2024 · 第 35 题

补充知识点

原理、适用条件与辨析

隐藏站未必能听见发送端，但可能听见接收端的 CTS。SIFS 通常短于 DIFS，便于 ACK 等响应优先发送；RTS 本身仍可能碰撞。

简短例子

B 听不到 A 却听到 AP 的 CTS，可以据 NAV 延迟发送，避免干扰 A→AP。

相关真题：2024 · 第 36 题

408 章节补全

原理、适用条件与辨析

ASK 改幅度、FSK 改频率、PSK 改相位；Manchester 每位中部有跳变便于时钟提取，速率与带宽需依题设口径。不能把波特率直接当比特率。

简短例子

4 种符号可表示 2 bit，因此 1000 Baud 理想信息率为 2000 bit/s（未另计开销）。

408 章节补全

原理、适用条件与辨析

光传播仍有有限速度，链路距离产生传播时延。复用用于共享资源；全双工不是将一条流自动翻倍为两倍单向吞吐。

简短例子

对讲机常为半双工，不能双方同时讲话；全双工点对点以太网可同时发收。

408 章节补全

原理、适用条件与辨析

正交码的内积用于分离信号，映射 0/1 到 ±1 及是否归一化需按题设。不是所有随机码字都满足正交；保护带/时隙标识等开销降低有效利用率。

简短例子

普通同步 TDM 用户闲置时仍可能占固定槽，统计 TDM 可把槽给活跃用户。

408 章节补全

原理、适用条件与辨析

发送端填充、接收端解除，填充位不属于原数据。PPP 等协议还需按实际链路和帧规则区分；不能在遇四个 1 时就插位。

简短例子

原数据中的 01111110 可以通过填充避免被误认为 HDLC 标志。

408 章节补全

原理、适用条件与辨析

停止等待要区分新帧和重传，常用交替位；ACK 丢失会导致重传，接收端需去重。丢数据、丢 ACK、超时过早的时间线要分别画。

简短例子

接收端已收到帧 0，但 ACK 丢失；再次收到帧 0 不能重复交付。

408 章节补全

原理、适用条件与辨析

若目标就在入端口关联网段可过滤。表项有老化机制，搬迁后可更新；泛洪不等于路由器跨网广播，也不能无限循环而不控制二层环路。

简短例子

H1 从端口 1 发往未知 H2，交换机先学 H1→1，再泛洪寻找 H2。

408 章节补全

原理、适用条件与辨析

IP 子网与 VLAN 是不同层的组织方式，常配套但不能互相替代。端口成员、标签与路由决定可达性；同交换机上的两个 VLAN 也可隔离广播。

简短例子

H1、H2 配相同 IP 前缀但在隔离 VLAN 中，普通二层 ARP 不必可达对方。

补充知识点

原理、适用条件与辨析

目标不同网段时下一跳通常是网关。路由器每跳重封装链路层首部；通常端到端 IP 地址保持，NAT 是另一个机制。

简短例子

访问远端网站时，局域网帧的目标 MAC 通常是网关 MAC，IP 目标仍是网站地址。

相关真题：2024 · 第 35 题

补充知识点

原理、适用条件与辨析

先检查地址是否匹配，再比较前缀长度。下一跳和出接口可能单独指定，不能把目的网段地址直接当下一跳。

简短例子

10.1.2.3 同时匹配 10.0.0.0/8 与 10.1.2.0/24，选择 /24。

补充知识点

原理、适用条件与辨析

偏移相对原始 IP 数据部分，不能把首部计入偏移。MF=1 表示后面还有片，最后片 MF=0；重组通常在目的主机完成。

简短例子

片偏移 185 对应原数据的第 1480 字节处，不是第 185 字节。

补充知识点

原理、适用条件与辨析

TTL 归零时通常丢弃并可产生超时差错；不是所有数据包都允许返回差错，例如不对另一条 ICMP 差错再生成差错。IPv6 不使用同样首部校验和。

简短例子

TCP 校验覆盖 TCP 首部与数据及伪首部，而 IPv4 的校验不覆盖 IP 负载。

补充知识点

原理、适用条件与辨析

距离向量可能发生无穷计数，水平分割/毒性逆转用于缓解但不解决所有拓扑中的环路。链路状态也有传播与收敛时间。

简短例子

RIP 属于距离向量；OSPF 属于链路状态。

补充知识点

原理、适用条件与辨析

传统可用主机数规则对 /31 点到点与 /32 等特殊用途不直接适用。先看具体网段和用途，不能拿远端路由器地址作直接下一跳。

简短例子

192.168.1.60/27 属于 192.168.1.32/27，广播为 .63；网关 .62 在该子网内。

相关真题：2022 · 第 35 题；2022 · 第 36 题

补充知识点

原理、适用条件与辨析

数据平面根据流表匹配和转发，控制平面制定策略与下发规则。OpenFlow 是常见南向接口协议之一，不是所有 SDN 的唯一实现。

简短例子

控制器向交换机下发流表属于南向交互。

相关真题：2022 · 第 37 题

408 记忆与概念补充

原理、适用条件与辨析

TTL 在现代转发中主要按跳数扣减，并非主机上“到时重发”的 RTO。IP 不因重组超时自动重传原数据报；端到端可靠性由上层协议另行处理。

简短例子

路由器 TTL 归零丢包与目的主机分片迟迟不全，是不同的失效场景。

参考：RFC 1122：IP 重组与 TCP 计时机制

408 记忆与概念补充

原理、适用条件与辨析

超时不是片偏移，也不等于 RTT。不要将 IPv4 TTL 字段机械当成重组等待秒数。收到首片且满足 ICMP 发送条件时，可报告重组超时。

简短例子

到达第 1、3 片而第 2 片一直未到，等待过期后不能把不完整内容直接交给 TCP。

参考：RFC 1122：IP 重组与 TCP 计时机制

408 记忆与概念补充

原理、适用条件与辨析

路由失效时度量设为 16，停止用于正常转发，但暂保留并通告不可达。垃圾收集从失效阶段开始，不是与最初的 180 s 同时开始；厂商的保持/清除参数可能另有设置。

简短例子

无新路由等条件下，若从最近一次更新 t=0 计，t≈180 s 失效，再过 120 s 删除。

参考：RFC 2453 §3.8：RIP 定时器

408 章节补全

原理、适用条件与辨析

NAT 可能影响端到端地址与校验和；它不是路由器正常转发时必须执行的操作。端口用于区分传输端点，不能替代 IP 路由前缀。

简短例子

多个内网主机共享一个公网地址时，可用不同外部端口区分会话。

408 章节补全

原理、适用条件与辨析

IPv6 无基本首部校验和，用邻居发现等代替 IPv4 ARP 的部分职责。地址压缩 :: 一处最多用一次，不能因此失去组数信息。

简短例子

一个 IPv6 基本首部含地址与下一首部等字段，额外功能可用扩展首部。

408 章节补全

原理、适用条件与辨析

ICMP 不等于网络层可靠传输。TTL 到期、目的不可达等可报告，但有发送限制；不能对 ICMP 差错再层层生成差错。traceroute 利用逐跳 TTL 等机制及响应。

简短例子

发出 ICMP 超时并不保证原数据报自动成功重发。

408 章节补全

原理、适用条件与辨析

协议用途、交换信息和路由度量不同。BGP 的策略不等于最短地理距离；OSPF 区域组织也不是 TCP 连接窗口。RIP/OSPF 并非应用文件传输协议。

简短例子

RIP 的 16 代表不可达，不能因此认为其他协议也最大只有 15 跳。

408 章节补全

原理、适用条件与辨析

瓶颈路由队列因网络拥塞增长不等于终端 rwnd=0。资源预留、调度、整形等可影响服务；不要把不同层机制混为一个计时器。

简短例子

发送端路由器出口拥挤时，终端接收缓冲仍可能有大量空间。

408 章节补全

原理、适用条件与辨析

基本首部 20 B，带选项可更长；MTU 限制所承载的 IP 数据报大小。源/目的地址、协议号、TTL 与首部校验字段作用不同，不能把端口写成 IP 首部固有字段。

简短例子

DF=1 且需要更小 MTU 而无法直接发送时，不能照常让路由器分片。

408 路由与地址解析的冷门辨析

原理、适用条件与辨析

换网卡、主机移动等可能使旧映射失效。缓存老化、等待 ARP 回答和 TCP 重传是不同机制；交换机 MAC 表老化也不是同一个表。不要背成所有设备固定若干分钟。

简短例子

同一 IP 后来对应新网卡时，旧 MAC 映射不能永久沿用。

参考：RFC 1122：ARP 缓存验证

408 路由与地址解析的冷门辨析

原理、适用条件与辨析

相邻接口的相关参数需匹配以正常形成邻居关系。10 s/40 s 是常见广播网配置例子，不是所有网络类型的固定值；具体题目给值时按题设。

简短例子

接口 Hello 为 10 s、Dead 为 40 s 时，不能只因漏掉一次 Hello 就立即按 Dead 超时处理。

参考：RFC 2328：OSPF 邻居与协议计时

408 路由与地址解析的冷门辨析

原理、适用条件与辨析

Hold Time 按本端配置与对端 OPEN 声明取较小值；接收有效的 KEEPALIVE/UPDATE 可维护保持计时，期满会处理会话失效。协商为 0 时不启动 Hold Timer，也不定期发送 KEEPALIVE；不能硬套厂商默认值。

简短例子

即使 TCP 底层尚未给出断连错误，BGP 的保持时间也可能先超时。

参考：RFC 4271：BGP KEEPALIVE 与 Hold Timer

补充知识点

原理、适用条件与辨析

TCP 累积确认只确认连续前缀，不能因更高序号的数据到达就跨越缺口确认。序号按 32 位模空间处理。

简短例子

收到从 100 开始的 20 字节连续数据后，确认号为 120。

补充知识点

原理、适用条件与辨析

真正可新增发送的数量还要扣除已发送但未确认的数据。窗口单位、MSS 及题设拥塞算法要分清，不能只看其中一个窗口。

简短例子

rwnd=8 MSS，cwnd=4 MSS，限制通常为 4 MSS；已有 3 MSS 在途时只剩约 1 MSS 余量。

补充知识点

原理、适用条件与辨析

经典教材模型与具体 TCP 实现有差异。超时与三次重复 ACK 后的更新也不同，题目若给 Tahoe/Reno 或简化规则应按其处理。

简短例子

当前窗口含多个段时，某一个 ACK 不会使整个窗口立即翻倍。

相关真题：2022 · 第 38 题

补充知识点

原理、适用条件与辨析

TCP 是双向连接，两方向独立关闭。TIME_WAIT 有助于处理旧段和重传最后 ACK；不能仅用最后报文发送者判断所有状态。

简短例子

A 发 FIN 后，B 确认并继续发送剩余数据，之后 B 再发 FIN。

相关真题：2022 · 第 39 题；2024 · 第 38 题

补充知识点

原理、适用条件与辨析

16 位反码和出现最高位进位要回卷相加，最后按位取反。奇数字节长度需为校验补 0，补字节不算有效数据。

简短例子

算得 17 位和后，不能简单丢弃最高位而不回卷。

相关真题：2024 · 第 39 题

408 记忆与概念补充

原理、适用条件与辨析

这些计时器不是统一的固定时长。RTO 由 RTT 等估计；持续计时器不是拥塞控制；保活通常可选；TIME_WAIT 不是接收窗口探测。

简短例子

题目说“窗口恢复通知可能丢失”应联想到持续计时器，而不是保活。

参考：RFC 9293：TCP 窗口、保活与关闭

408 记忆与概念补充

原理、适用条件与辨析

RFC 模型：RTO=SRTT+max(G,4×RTTVAR)，G 是计时精度。后续更新 RTTVAR 使用更新前的 SRTT。考试给简化加权公式或常量时，按题设。

简短例子

ACK 到来时若原报文和重传报文都可能导致它，无法明确对应哪一次发送时间。

参考：RFC 6298：TCP 重传计时器

408 记忆与概念补充

原理、适用条件与辨析

经典教材模型中，两种事件对拥塞窗口的处理可以不同。RTO 超时通常指数退避；不能把 TCP Reno 的重复 ACK 处理套成超时处理。

简短例子

三个重复 ACK 已提示缺口时，不必再等待原重传计时器走完。

参考：RFC 6298：TCP 重传计时器

408 记忆与概念补充

原理、适用条件与辨析

对端可能已经空出缓冲区，但携带窗口更新的 ACK 不保证可靠送达。探测有助重新得知窗口；它不代表把 cwnd 当作 rwnd，更不等于认为对端已掉线。

简短例子

接收方窗口从 0 恢复到非 0，但通知丢失，发送方可通过探测发现恢复。

参考：RFC 9293：TCP 窗口、保活与关闭

408 记忆与概念补充

原理、适用条件与辨析

教材常以约 2 小时等数值举例；RFC 规定默认关闭，启用时默认空闲间隔不小于 2 小时。考试若另给时间和次数，按题设；不要把系统配置当永久标准。

简短例子

一个只是不发送业务数据的健康连接不必关闭；保活与应用层心跳也不是同一层机制。

参考：RFC 9293：TCP 窗口、保活与关闭

408 记忆与概念补充

原理、适用条件与辨析

等待期间既给旧报文消失留时间，也给对方重传 FIN、自己补发 ACK 留时间。FIN 往返和数据传输耗时若题目要求总时长，应另行加上。

简短例子

只问 TIME_WAIT 驻留为 2MSL；问从连接建立到 CLOSED，就不能只答 2MSL。

参考：RFC 9293：TCP 窗口、保活与关闭

408 记忆与概念补充

原理、适用条件与辨析

延迟确认可减少独立 ACK 数量或等待捎带，但不能无期限等待。若题目给延迟时间，就计入 RTT/时间线；不能认为每个数据段立即返回 ACK。

简短例子

接收端短时等下一段以合并确认，会影响观察到的确认间隔，但不改变 ACK 的累计语义。

参考：RFC 1122：IP 重组与 TCP 计时机制

408 章节补全

原理、适用条件与辨析

端点通常由地址、端口与协议关联；TCP 连接以双端组合区分。UDP 首部 8 B，TCP 基本首部 20 B，可有选项。可靠与实时适用性取决于需求，不是协议名称直接决定。

简短例子

一次发送 100 B、再发送 50 B，TCP 接收 API 可按不同批次交付，应用需自定义消息边界。

408 章节补全

原理、适用条件与辨析

第三次 ACK 可带数据，纯 ACK 不耗序号。握手交换初始序号并确认两方向通信，不保证身份认证或消息加密；中途丢失可触发重传。

简短例子

若客户端初始 x=100，SYN 被确认后的下一个数据序号通常从 101 开始。

408 章节补全

原理、适用条件与辨析

基本首部 20 B，可含选项至 60 B；确认号、窗口、校验和等职责不同。RST 不是正常半关闭的替代说法，控制标志组合需结合连接状态判定。

简短例子

首部长度值 5 对应 20 B，不是 5 B。

补充知识点

原理、适用条件与辨析

缓存可缩短流程，不能每次都按“根→顶级域→权威”完整计算。区域传送等常用 TCP，响应截断后可重试 TCP。

简短例子

本地解析器命中缓存时，不必访问根服务器。

补充知识点

原理、适用条件与辨析

HTTP 持久连接复用连接，但不等于 HTTP/1.1 普通串行请求自动并行。涉及持久连接或流水线请求时，须按题设版本与规则判断。

简短例子

FTP 控制连接常用端口 21，不能因此断言所有数据连接都固定由服务器端口 20 发起。

408 章节补全

原理、适用条件与辨析

一个名字可有多条记录，别名解析可能需继续查询。缓存减少查询次数但可能短时保留旧数据；权威回答与递归解析器缓存回答要区分。

简短例子

MX 是邮件服务器相关记录，不等于浏览器直接访问的网页服务器 A 记录。

408 章节补全

原理、适用条件与辨析

初始客户端尚无可用 IP，常通过广播发现。租约续租不同于 TCP 保活；DNS、DHCP、HTTP、邮件协议分工不同。端口是常见默认约定，服务可另配置。

简短例子

DHCP 可以同时给网关和 DNS 服务器配置，后者由 DNS 服务执行名字解析。

408 章节补全

原理、适用条件与辨析

页面可能含 HTML 和多个嵌入对象，DNS、TCP、请求/响应与对象发送时间要分开。GET、POST、HEAD 等方法不同；HTTP 200/404 是应用响应，不是 TCP 连接状态。

简短例子

一个 HTML 引用 3 张图片，不能仅因只有一页就只算一次资源请求。

408 章节补全

原理、适用条件与辨析

控制命令与文件内容分通道；不同文件或目录列表可使用单独数据连接。NAT/防火墙可影响主动模式可达，不能把端口 20 当所有模式的固定结论。

简短例子

被动模式中服务器返回可连接数据端口，客户端主动去连该端口。

408 章节补全

原理、适用条件与辨析

邮件客户端到提交服务器、服务器之间传递、收件客户端取信是不同阶段。IMAP 支持服务器端邮箱组织与同步；默认端口和加密/提交端口需按题设区别。

简短例子

附件可通过 MIME 编码随邮件内容传递，但最终传输仍依赖相应邮件协议。

408 章节补全

原理、适用条件与辨析

OSI 为七层，TCP/IP 教材可用四层/五层模型，不应因名称不同就认为协议所属层不同。典型路由器主要网络层转发，普通二层交换机主要链路层转发。

简短例子

TCP 段封装进 IP 数据报，再进链路帧，通过比特信号发送。

408 章节补全

原理、适用条件与辨析

服务由下层向上层提供，而协议在对等层之间逻辑执行；实际数据经下层传输。协议的语法、语义、时序是不同内容。

简短例子

TCP 向应用提供可靠字节流，是服务；TCP 首部与状态转换规则属于协议。

408 章节补全

原理、适用条件与辨析

电路需建连但后续传输可少逐跳存储；分组有首部、排队和丢失重排代价。比较时统一文件大小、分组大小、链路速率与存储转发约定。

简短例子

一条长报文拆成多包后可在不同链路重叠传送，而不是每跳都等待全文件。