保研复试机考速通笔记

面向哈尔滨工业大学（深圳）计算机相关专业推免 / 预推免复试机考。适合已经学过专业课、但距离考试只剩几天，希望通过高频知识点和往年题快速恢复状态的同学。

2026年9月2日更新于 2026年9月4日Leo Zhu

一、先说结论：不要把它当成一套简单的 408

哈工深计算机推免机考历年的具体题量、科目分布都会变化，因此某一年的通知只能作为参考。

从本文所附的 2020 年两场、2021 年一场试卷来看，比较稳定的特征是：

题量较大，以选择题、判断题等客观题为主；
覆盖面很广，但大量题目考查基础概念、经典模型和语言细节；
数据结构与算法、操作系统、计算机网络是三场都大量出现的主干；
数据库同样稳定高频，而且关系理论、SQL、事务、设计与恢复都有涉及；
C 语言题量未必最大，但程序阅读、指针和字符串题很适合拉开正确率；
离散数学场次波动较大，却会连续考逻辑、关系、图论与代数系统；
部分年份会明显体现出“408 化”的趋势；
哈工自己的课程体系比较重要，尤其是数据库、离散数学；
往年题、课程题、MOOC 题具有很高的复习价值。

因此，几天内突击时，最不推荐的方法是：

按照教材目录，从第一章重新开始学习六七门课。

更有效的思路是：

往年题反推重点 → 高频知识点快速恢复 → 大量客观题巩固 → 错题查漏补缺。

二、从三份真题反推复习优先级

下面的排序只针对本文使用的三份样本，不把它冒充成未来考试的固定命题比例。跨学科题按主要考点归类后，可以得到一个很清楚的复习方向：

三份 PDF 是带作答痕迹的试卷导出，不是官方标准答案。本文只用题干统计知识点；页面上的勾选项和填空内容不作为结论依据。

优先级	模块	三份试卷反复出现的内容
S	数据结构与算法	树与森林、B / B+ 树、堆、排序、图、栈与队列、查找与复杂度
S	计算机网络	GBN / SR / 停等、TCP、CSMA、子网与路由、协议分层、交换
S	操作系统	分页与分段、页面置换、文件与磁盘、死锁、信号量、I/O
A	数据库系统	函数依赖与范式、关系代数、完整性、SQL 权限、E-R、恢复
A	离散数学	命题与量词、关系与偏序、图论、群与模运算；场次间波动较大
A	C 语言	指针、数组与字符串、`static`、联合体、运算符、递归与程序阅读
B	计算机组成原理	Cache、流水线、补码、寻址、RISC、I/O；题量较少但计算性强

三份试卷共同暴露出的命题习惯

不是只问定义。 很多题给出地址序列、帧序列、函数依赖或程序片段，要求现场计算。
同一母题会换参数重考。 例如 GBN 重传、LRU、候选键、B 树高度、堆调整、TCP 序号与窗口在不同场次重复出现。
系统课程比重不能让位给纯 C 突击。 C 需要练程序阅读，但网络、操作系统和数据结构的覆盖面更大。
哈工课程题风明显。 文件系统、关系数据库、离散数学中的偏序和代数系统，比只刷 408 更细。

最短时间分配建议

如果只剩两天，可以按“ $40\%$ 主干计算题、 $35\%$ 数据库与离散、 $25\%$ C 与计组”分配：

主干计算题：链路利用率与滑动窗口、页面置换、磁盘调度、树 / 堆 / 排序；
数据库与离散：闭包、候选键、范式、关系代数、量词、偏序、群；
C 与计组：手推程序、字符串 / 指针、Cache 地址划分、流水线与补码。

复习每个知识点时，至少做到“能解释概念、能算一题、能识别一个陷阱”，不要只背一句结论。

C 语言

数组与指针

声明 int a[10]; 后，a 在大多数表达式中会转换为指向首元素的指针 &a[0]。下标运算本质上是指针运算：

a[i] \equiv *(a+i) \equiv i[a]

最后一种写法虽然合法，但可读性很差，只适合用来识别考题陷阱。

`a` 和 `&a`

对 int a[5];，a 与 &a 的地址数值通常相同，类型和步长却不同：

表达式	调整后的类型	加一跨过的空间
`a`	`int *`	一个 `int`
`&a`	`int (*)[5]`	整个 `int[5]`

若 sizeof(int)=4，则地址增量分别为 $4$ 字节和 $5\times4=20$ 字节。

指针数组与数组指针

int *p[10];：[] 先结合，p 是含有 $10$ 个 int * 元素的指针数组。
int (*p)[10];：括号让 *p 先结合，p 是指向 int[10] 的数组指针。

读复杂声明时，从变量名出发，按运算符优先级向外读。

数组作为函数参数

函数形参中的 void f(int a[]) 会调整为 void f(int *a)。C 语言仍然是值传递，复制的是首元素地址，不是整个数组；因此在函数内部对形参使用 sizeof(a)，得到的是指针大小，而不是原数组大小。

`sizeof` 与 `strlen`

对 char s[] = "HIT";，内存内容为 H I T \0，因此：

\operatorname{strlen}(s)=3,\qquad \operatorname{sizeof}(s)=4

若声明改为 char s[100] = "HIT";，则：

\operatorname{strlen}(s)=3,\qquad \operatorname{sizeof}(s)=100

strlen 统计首个 \0 之前的字符数；sizeof 计算对象本身占用的字节数。字符串字面量 "abc" 还包含结尾的 \0，所以 sizeof("abc") == 4。

字符数组与字符串字面量

char s[] = "abc"; 创建可修改的字符数组，s[0] = 'A'; 合法。
const char *s = "abc"; 指向字符串字面量，不应修改其内容。

旧代码中常见 char *s = "abc";，但执行 s[0] = 'A'; 属于未定义行为。

`const` 指针

声明	含义	可以做什么
`const int *p`	不能通过 `p` 修改所指对象	可以让 `p` 指向别处
`int * const p = &x`	`p` 本身不能改变指向	可以执行 `*p = 10`
`const int * const p = &x`	指向和所指内容都受限	二者都不能通过 `p` 修改

速记：const 在 * 左侧，限制所指内容；在 * 右侧，限制指针本身。

`++`、`--` 与表达式

i++ 先产生旧值，再完成自增副作用；++i 先自增，再产生新值。不要机械计算 printf("%d %d", i++, ++i);：同一完整表达式中对 i 的多次无序修改可能导致未定义行为，题目声称它“一定输出某值”时应高度警惕。

短路求值

逻辑与、逻辑或从左到右求值，并满足：

0\mathbin{\&\&}f()=0,\qquad 1\mathbin{||}f()=1

两式中的 f() 都不会执行。例如 int x = 0; 后判断 x && ++x，右侧被短路，最终仍有 $x=0$ 。

`static` 与 `extern`

局部静态变量的作用域仍在函数内，但生命周期贯穿整个程序，且只初始化一次：

void f(void) {
    static int x = 0;
    printf("%d ", ++x);
}

连续调用三次输出 1 2 3。文件作用域的 static int x; 让名字只在当前翻译单元内可见；extern int x; 通常声明 x 的定义位于其他位置。

动态内存

函数	作用	高频陷阱
`malloc(n)`	分配 $n$ 字节	内容未初始化
`calloc(k, n)`	为 $k$ 个、每个 $n$ 字节的对象分配空间	分配区按字节置零
`realloc(p, n)`	调整内存块大小	可能移动地址；失败时原块仍有效
`free(p)`	释放内存	不会自动令 `p = NULL`

常见分配写法是 int *p = malloc(100 * sizeof *p);。释放后若指针仍会继续存在，可写：

free(p);
p = NULL;

结构体与联合体

结构体的各成员拥有各自的存储空间；联合体的成员共享同一块空间：

struct Student {
    int id;
    char name[20];
    double score;
};

union Data {
    int a;
    double b;
};

结构体大小通常不小于成员大小之和，联合体大小通常不小于最大成员大小；两者都可能因对齐要求产生额外填充。

宏定义

宏是文本替换。若写 #define SQUARE(x) x*x，则 SQUARE(1 + 2) 展开为 1 + 2 * 1 + 2，结果为 $5$ 而不是 $9$ 。较安全的写法是：

#define SQUARE(x) ((x) * (x))

即使加了括号，也要警惕 SQUARE(i++) 令实参求值两次。

运算符、条件表达式与 `switch`

真题中的 C 题经常不是问语法定义，而是让你手推一行表达式。建议按下面的顺序处理：

先加括号，确认 []、函数调用、单目运算、算术、关系、位运算、逻辑运算和条件运算的结合范围；
区分位运算 & | ^ 与逻辑运算 && ||；
再判断是否短路、是否有副作用、是否存在未定义行为。

条件运算符 ?: 从右向左结合。例如 w < x ? w : y < z ? y : z 等价于：

w < x ? w : (y < z ? y : z)

switch 中若某个 case 后没有 break，会继续执行后续分支，直到遇到 break 或离开 switch。这类题不要只看匹配到哪个 case，还要沿着控制流继续向下走。

字符串函数与手写扫描

三份试卷多次要求判断字符串比较、复制和长度程序：

strcmp(s1, s2) < 0 表示 s1 按字典序小于 s2，不是长度更短；
strcpy(dst, src) 会连同结尾的 \0 一起复制，目标数组必须有足够空间；
while (*p++); 结束时，p 已越过 \0，因此 p - s 通常等于 strlen(s) + 1；
char *p[10] 是指针数组，p[i] 才是某个字符串的首地址。

输入格式与程序阅读

scanf 的格式字符串必须和实际输入匹配。格式中出现普通字符时，输入中也必须出现相同字符：

scanf("x=%d,y=%f", &x, &y);

对应的输入形如 x=10,y=66.6，仅输入 10 66.6 不匹配。

手推递归或静态变量程序时，建议画调用表，记录“实参、局部变量、静态变量、返回值”四列。static 不会因函数返回而恢复初值，第二次顶层调用会继承第一次调用后的状态。

C 语言考前检查表

看到的关键词	立即联想到
数组、`&a`	数组到指针的转换、数组指针、步长
字符串	结尾的 `\0`、字面量不可修改
`sizeof`、`strlen`	对象大小与字符串长度的区别
`const`	它修饰的是内容还是指针
`++`、`--`	求值顺序、副作用、未定义行为
`?:`、`switch`	结合方向、分支贯穿与 `break`
`strcmp`、`strcpy`	字典序、空间大小与结尾 `\0`
`scanf`	格式串中的普通字符也要匹配
`&&`、`\|\|`	短路求值
`static`	生命周期、作用域与链接属性
`malloc`、`free`	未初始化、泄漏、悬空指针
`struct`、`union`	内存对齐与存储共享
宏	文本替换、括号、重复求值

数据库系统

三级模式与数据独立性

数据库的三级模式是外模式、模式和内模式，两级映像承担数据独立性：

变化	为保持独立性需要调整
内模式改变，不希望影响模式	模式 / 内模式映像，即物理数据独立性
模式改变，不希望影响外模式和应用	外模式 / 模式映像，即逻辑数据独立性

看到“逻辑数据独立性”时，不要误选内模式相关映像。

键与函数依赖

超键（Super Key）：能够唯一确定一个元组的属性集合。
候选键（Candidate Key）：不含多余属性的最小超键。若 $K$ 是候选键，则 $K^+=R$ ，且任意真子集 $K'\subset K$ 都满足 $K'^+\ne R$ 。
主键（Primary Key）：从候选键中选出的一个标识键。
外键（Foreign Key）：引用另一关系的候选键；它用于维护参照完整性，不要求在当前关系中唯一。

属性闭包

设函数依赖集为：

F=\{A\to B,\ B\to C,\ CD\to E\}

计算 $A^+$ 时，从 $A^+=\{A\}$ 出发，依次应用 $A\to B$ 与 $B\to C$ ：

\{A\}\Rightarrow\{A,B\}\Rightarrow\{A,B,C\}

由于缺少 $D$ ，无法使用 $CD\to E$ ，所以最终 $A^+=\{A,B,C\}$ 。

属性闭包主要用于：

判断候选键；
判断函数依赖是否可推出；
求最小覆盖；
判断范式。

最小函数依赖集

求最小依赖集通常按三步进行：

右部单属性化：将 $A\to BC$ 拆成 $A\to B$ 与 $A\to C$ 。
删除左部冗余属性：对 $AB\to C$ ，分别检查 $C\in A^+$ 或 $C\in B^+$ 是否能由当前依赖集推出。
删除冗余依赖：暂时移除 $X\to Y$ ，若仍有 $Y\subseteq X^+$ ，该依赖可以删除。

范式

范式	核心要求	主要消除的问题
1NF	属性值具有原子性	重复组、非原子值
2NF	在 1NF 上，非主属性完全依赖于每个候选键	对复合候选键的部分依赖
3NF	对每个 $X\to A$ ， $X$ 是超键或 $A$ 是主属性	非主属性对候选键的传递依赖
BCNF	对每个非平凡依赖 $X\to Y$ ， $X$ 都是超键	决定因素不是超键的依赖

例如：

\text{StudentID}\to\text{Dept},\qquad \text{Dept}\to\text{DeptPhone}

由传递律得到 $\text{StudentID}\to\text{DeptPhone}$ ，这就是典型的传递依赖。范式强弱可粗记为：

\mathrm{BCNF}\Rightarrow\mathrm{3NF}\Rightarrow\mathrm{2NF}\Rightarrow\mathrm{1NF}

真题常把定义包装成候选键判断。推荐顺序是：先求候选键，再标出主属性，最后逐条检查函数依赖。仅知道“候选键都是决定因素”还不够；BCNF 要求的是每个非平凡函数依赖的左部都是超键。

若考到多值依赖，记住 $X\twoheadrightarrow Y$ 描述的是给定 $X$ 后， $Y$ 与其余属性可以独立组合。4NF 要求每个非平凡多值依赖的决定因素都是超键。

完整性约束

约束	约束对象	典型例子
实体完整性	主键	主键非空且唯一
参照完整性	外键	外键为空，或引用被参照关系中的有效键值
用户定义完整性	具体业务列	成绩必须在 $0$ 到 $100$ 之间

列级、表级是按约束写在 SQL 定义中的位置分类；实体、参照、用户定义则是按约束语义分类，不要混成一组。

关系代数与连接

关系代数的基本对象是关系，核心运算优先记下面五个：

符号	含义	对结果的主要影响
$\sigma_F(R)$	选择	筛行
$\pi_A(R)$	投影	选列并按关系语义去重
$R\times S$	笛卡尔积	拼接所有元组组合
$R-S$	差	保留只在 $R$ 中的元组
$R\bowtie S$	连接	按条件组合两个关系

SQL FROM R, S WHERE R.C = S.C 可先理解为 $R\times S$ ，再做选择；SELECT A, B, D 最后对应投影。

自然连接会比较所有同名属性，并只保留一份同名列； $\theta$ 连接按指定条件连接。因此只有一个公共属性时，自然连接通常比保留两份连接列的等值连接少一个属性。

SQL 逻辑执行顺序

建议记为：

\texttt{FROM}\to\texttt{WHERE}\to\texttt{GROUP BY}\to\texttt{HAVING} \to\texttt{SELECT}\to\texttt{DISTINCT}\to\texttt{ORDER BY}\to\texttt{LIMIT}

很多 SQL 选择题都可以通过这条顺序判断。

SQL 语言类别与权限

类别	典型语句	用途
DDL	`CREATE`、`ALTER`、`DROP`	定义数据库对象
DML	`SELECT`、`INSERT`、`UPDATE`、`DELETE`	查询和操作数据
DCL	`GRANT`、`REVOKE`	授予和收回权限

收回用户 ZHAO 对表 STUD 中列 XH 的修改权，可识别为：

REVOKE UPDATE(XH) ON STUD FROM ZHAO;

题目若写 PUBLIC，表示所有用户，不是某个指定用户。

NULL

判断空值要写 WHERE score IS NULL，不能写 WHERE score = NULL。SQL 使用三值逻辑：

\{\mathrm{TRUE},\ \mathrm{FALSE},\ \mathrm{UNKNOWN}\}

比较 NULL = NULL 的结果是 UNKNOWN，而 WHERE 只保留结果为 TRUE 的行。

`COUNT`

COUNT(*) 统计行数；COUNT(column) 只统计该列非 NULL 的行。若一组共有 $n$ 行，其中该列有 $k$ 个空值，则：

\operatorname{COUNT}(*)=n,\qquad \operatorname{COUNT}(column)=n-k

`WHERE` 与 `HAVING`

WHERE 在分组前过滤行，HAVING 在分组后过滤组。

例如：

SELECT dept, COUNT(*)
FROM student
WHERE age >= 18
GROUP BY dept
HAVING COUNT(*) > 10;

执行逻辑是“筛选 $age\ge18$ 的行 $\to$ 按 dept 分组 $\to$ 保留人数大于 $10$ 的组”。

`EXISTS`

EXISTS (subquery) 只判断子查询是否至少返回一行，不关心返回列的具体值：

\operatorname{EXISTS}(Q)= \begin{cases} \mathrm{TRUE}, & |Q|>0\\ \mathrm{FALSE}, & |Q|=0 \end{cases}

特别注意子查询是否：

与外层查询相关；
完全独立。

如果一个独立子查询返回非空，那么 EXISTS 对外层每一行都可能成立。

视图

视图本质上是：

由查询定义出来的虚表。

简单的单表选择、投影视图通常比较容易更新。

如果包含：

GROUP BY；
聚合函数；
DISTINCT；
复杂连接；

通常不能直接更新。

视图消解是把针对视图的查询转换为针对基本表的查询过程；它不是把查询直接改写成对物理数据文件的访问。

E-R 模型与数据库设计

E-R 方法的三个基本要素是实体、属性和联系。局部 E-R 图合并时常见命名冲突、属性冲突和结构冲突，“语法冲突”通常不是这一组标准分类。

数据库逻辑设计会影响表结构与查询方式，物理设计会影响文件组织、索引和访问路径。大关系拆分可能减少某些连接内的冗余，却会增加查询时的连接开销，不能笼统地说“拆得越细性能越好”。

ACID

特性	含义
Atomicity	原子性，全做或全不做
Consistency	一致性，从一个合法状态转移到另一个合法状态
Isolation	隔离性，并发事务互相隔离
Durability	持久性，提交后的结果能够保存

并发异常

异常	现象	速记
脏读（Dirty Read）	读到另一事务尚未提交的数据	未提交
不可重复读（Non-repeatable Read）	同一事务两次读取同一行，值不同	同一行变
幻读（Phantom Read）	同一条件查询两次，返回的行集合不同	行集合变

冲突可串行化

对调度建立优先图：若事务 $T_i$ 的某个冲突操作先于 $T_j$ ，就加入边 $T_i\to T_j$ 。判断条件是：

\text{conflict-serializable}\iff G_P\text{ is acyclic}

图的任一拓扑序就是一个与原调度冲突等价的串行顺序。

两阶段锁 2PL

两阶段锁分为“增长阶段：只能加锁”和“收缩阶段：只能解锁”。一旦释放了任何锁，就不能再申请新锁。2PL 能保证冲突可串行化，但不能保证没有死锁。

Undo / Redo

快速记忆：

\mathrm{STEAL}\Rightarrow\mathrm{UNDO},\qquad \mathrm{NO-FORCE}\Rightarrow\mathrm{REDO}

STEAL：

允许未提交事务修改的数据页提前写回磁盘。

所以发生回滚时需要：

UNDO。

NO-FORCE：

提交时不要求所有修改页立刻写盘。

所以系统恢复时可能需要：

REDO。

索引

B+ Tree

适合：

等值查询；
范围查询；
顺序访问。

优点：

高扇出；
树高度低；
磁盘 I/O 少；
叶节点有序。

Hash

哈希索引适合 WHERE id = 123 这样的等值查询，但通常不适合 WHERE id BETWEEN 100 AND 200 这样的范围查询。

离散数学

命题逻辑

最重要的等价式是：

p\to q\equiv\neg p\lor q

蕴含式只在 $p=\mathrm{T}$ 且 $q=\mathrm{F}$ 时为假。

双条件

p\leftrightarrow q\equiv(p\to q)\land(q\to p)

德摩根律

\neg(p\land q)\equiv\neg p\lor\neg q,\qquad \neg(p\lor q)\equiv\neg p\land\neg q

逆、否、逆否

名称	形式
原命题	$p\to q$
逆命题	$q\to p$
否命题	$\neg p\to\neg q$
逆否命题	$\neg q\to\neg p$

必须记住： $p\to q\equiv\neg q\to\neg p$ ；逆命题与否命题也彼此等价，但它们通常不等价于原命题。

量词否定

\neg\forall x\,P(x)\equiv\exists x\,\neg P(x),\qquad \neg\exists x\,P(x)\equiv\forall x\,\neg P(x)

口诀：否定向内推进， $\forall$ 与 $\exists$ 交换，谓词同时取否定。

前束范式与变量换名

前束范式要求所有量词集中在公式最前面。移动量词前，先把不同量词约束的同名变量改名，避免变量捕获。例如：

(\exists x\,F(x,y))\land(\forall x\,G(x)) \equiv \exists z\forall x\,(F(z,y)\land G(x))

不能在不检查自由变量的情况下，机械地把两个量词都移到最前面。

集合

若 $|A|=n$ ，则幂集大小为：

|\mathcal P(A)|=2^n

两个与三个集合的容斥原理分别为：

|A\cup B|=|A|+|B|-|A\cap B|

|A\cup B\cup C| =|A|+|B|+|C| -|A\cap B|-|A\cap C|-|B\cap C| +|A\cap B\cap C|

二元关系

设 $R$ 是集合 $A$ 上的关系：

性质	定义
自反	$\forall a\in A,\ aRa$
对称	$\forall a,b\in A,\ aRb\Rightarrow bRa$
反对称	$\forall a,b\in A,\ aRb\land bRa\Rightarrow a=b$
传递	$\forall a,b,c\in A,\ aRb\land bRc\Rightarrow aRc$

反对称并不是“不对称”：反对称允许 $aRa$ ，只是不允许两个不同元素同时满足 $aRb$ 与 $bRa$ 。

等价关系与偏序

\begin{aligned} \text{equivalence relation}&=\text{reflexive}+\text{symmetric}+\text{transitive},\\ \text{partial order}&=\text{reflexive}+\text{antisymmetric}+\text{transitive}. \end{aligned}

典型偏序包括 $\le$ 、 $\subseteq$ 与整除关系。等价关系将集合划分为互不相交的等价类；偏序中的元素则不一定两两可比。

哈斯图中的四类元素

对偏序集的子集 $B$ ：

最大元、最小元必须属于 $B$ ，若存在则唯一；
极大元、极小元也属于 $B$ ，但可能有多个；
上界、下界在整个偏序集内寻找，不一定属于 $B$ ；
最小上界、最大下界是所有上界 / 下界中的最小 / 最大者，若存在则唯一。

“最大元”一定同时是极大元和最小上界；反过来，“最小上界”不一定属于 $B$ ，所以不一定是最大元。

映射

单射： $f(x_1)=f(x_2)\Rightarrow x_1=x_2$ ，不同输入不会映射到相同输出。
满射： $\forall y\in Y,\exists x\in X$ 使 $f(x)=y$ ，陪域中的每个元素都有原像。
双射：既单射又满射，因此存在逆函数。

若 $|X|=m$ 、 $|Y|=n$ ，则从 $X$ 到 $Y$ 的函数总数为：

n^m

图论

握手定理：

\sum_{v\in V}\deg(v)=2|E|

因此：

奇数度顶点的数量一定是偶数。

三份试卷还出现了割点 / 割边、点覆盖与独立集、对偶图、图着色和森林。建议补记：

森林有 $n$ 个顶点、 $e$ 条边时，连通分量数为 $n-e$ ；
无孤立点图中，极小点覆盖的补集是极大独立集；
有割边不一定有割点，例如只有两个顶点的一条边；
简单图的点色数满足 $\chi(G)\le \Delta(G)+1$ ，并非总有 $\chi(G)\le\Delta(G)$ 。

树

有 $n$ 个顶点的树满足 $|E|=n-1$ 。以下命题彼此等价：

连通且无环；
有 $n-1$ 条边且连通；
有 $n-1$ 条边且无环；
任意两点之间恰有一条简单路径。

平面图

连通平面图满足 Euler 公式：

|V|-|E|+|F|=2

例如 $|V|=12$ 、 $|E|=14$ ，则 $|F|=2-|V|+|E|=4$ 。

两个必须记住的经典非平面图是 $K_5$ 与 $K_{3,3}$ 。

连通平面图的对偶图满足“原图的面对应对偶图的顶点，原图的边对应对偶图的边”，因此：

|V(G^*)|=|F(G)|,\qquad |E(G^*)|=|E(G)|

Euler 与 Hamilton

Euler

关注：

边。

无向连通图存在 Euler 回路：所有顶点度数均为偶数。

存在 Euler 路但不存在 Euler 回路：恰有两个奇数度顶点，路径从其中一个奇度顶点出发，在另一个结束。

Hamilton

关注：

顶点。

不要把 Euler 的度数条件直接套到 Hamilton 上。

代数系统与群

短期复习只抓基本定义。

\begin{aligned} \text{semigroup}&=\text{closure}+\text{associativity},\\ \text{monoid}&=\text{semigroup}+\text{identity},\\ \text{group}&=\text{monoid}+\text{inverse},\\ \text{Abelian group}&=\text{group}+\text{commutativity}. \end{aligned}

必须记：

循环群一定是交换群。

但是：

交换群不一定是循环群。

元素的阶与模逆元

若 $a$ 是 $n$ 阶循环群的生成元，则：

\operatorname{ord}(a^k)=\frac{n}{\gcd(n,k)}

因此在 $10$ 阶循环群中， $a^3$ 仍是 $10$ 阶元素，因为 $\gcd(10,3)=1$ 。

整数 $k$ 在模 $q$ 下存在乘法逆元，当且仅当：

\gcd(k,q)=1

例如 $125\equiv5\pmod8$ ，且 $5\times5\equiv1\pmod8$ ，所以逆元存在。

数据结构与算法

高频复杂度

操作	复杂度
数组随机访问	$O(1)$
链表随机访问	$O(n)$
栈 Push / Pop	$O(1)$
队列入队 / 出队	$O(1)$
二分查找	$O(\log n)$
哈希平均查询	$O(1)$
平衡 BST 查询	$O(\log n)$
堆插入	$O(\log n)$
删除堆顶	$O(\log n)$
自底向上建堆	$O(n)$

特别注意：

自底向上 Build Heap 是 $O(n)$ ，不是 $O(n\log n)$ 。

栈与队列

栈遵循 LIFO，队列遵循 FIFO。DFS 使用栈或递归，BFS 使用队列。

真题还会给定入栈序列，判断某个出栈序列是否合法。手算时维护“下一个待入栈元素”和“当前栈顶”：想输出的元素若不在栈顶，就持续入栈；若已经被压在别的元素下面，则该序列不可能。

表达式求值通常需要操作数栈和运算符栈。中缀转后缀时，右括号只负责弹出到左括号，本身不进入结果；a*(b+c)/d 的后缀式是 abc+*d/。

循环队列

设数组容量为 $M$ ，采用“牺牲一个存储单元”的经典实现，则队空、队满和队长依次满足：

\begin{aligned} front&=rear,\\ (rear+1)\bmod M&=front,\\ L&=(rear-front+M)\bmod M. \end{aligned}

二叉树

根节点为第 $1$ 层时，第 $i$ 层最多有 $2^{i-1}$ 个节点；高度为 $h$ 的二叉树最多有：

1+2+\cdots+2^{h-1}=2^h-1

任意非空二叉树中，若 $n_0$ 是叶节点数， $n_2$ 是度为 $2$ 的节点数，则：

n_0=n_2+1

若一棵完全二叉树共有 $2n-1$ 个节点，则叶节点数为 $n$ 。完全二叉树按数组编号时，节点 $i$ 的左右孩子为 $2i$ 、 $2i+1$ ，父节点为 $\lfloor i/2\rfloor$ 。

二叉树遍历

遍历	访问顺序
前序	根 $\to$ 左 $\to$ 右
中序	左 $\to$ 根 $\to$ 右
后序	左 $\to$ 右 $\to$ 根
层序	按层 BFS

节点值互异时，“前序 $+$ 中序”或“后序 $+$ 中序”可以唯一确定一棵二叉树；“前序 $+$ 后序”通常不能。

树、森林与二叉树转换

左孩子右兄弟表示法中，普通树节点的第一个孩子变成二叉树的左孩子，右侧兄弟变成二叉树的右孩子。常见对应关系是：

树 / 森林的先根遍历对应二叉树的先序遍历；
树的后根遍历对应二叉树的中序遍历；
森林的后根遍历对应二叉树的中序遍历。

对普通树转换后的二叉树，原树中最后一个孩子没有右兄弟。若原树有 $n$ 个节点、 $L$ 个叶节点，则转换后二叉树中无右孩子的节点数为 $n-L+1$ 。

BST

二叉搜索树满足“左子树键值 $<$ 根键值 $<$ 右子树键值”（默认键值互异），因此中序遍历得到升序序列。

查询复杂度取决于树高 $h$ ，即 $O(h)$ ；较平衡时为 $O(\log n)$ ，退化成链时为 $O(n)$ 。

AVL

任意节点的平衡因子满足：

|h_{left}-h_{right}|\le 1

失衡类型	调整方式
LL	右旋
RR	左旋
LR	先对左孩子左旋，再对失衡节点右旋
RL	先对右孩子右旋，再对失衡节点左旋

B 树与 B+ 树

这组真题多次直接考阶数、高度、关键字上下界，必须单独复习。对 $m$ 阶 B 树：

每个节点至多有 $m$ 棵子树、至多有 $m-1$ 个关键字；
除根和叶层外的内部节点至少有 $\lceil m/2\rceil$ 棵子树；
非叶根至少有 $2$ 棵子树；
所有失败节点位于同一层。

不要把“所有节点至少有 $\lceil m/2\rceil$ 棵子树”当成正确描述，因为根节点是例外。

B+ 树与 B 树的区分：B+ 树的内部节点只作索引，数据记录集中在叶节点，叶节点按键值顺序链接，因此范围查询更自然。

堆

最大堆：

父节点 ≥ 子节点。

最小堆：

父节点 ≤ 子节点。

但是：

堆不是整体有序。

最大堆只能保证：

根节点一定最大。

Huffman

构造规则：

每次选择权值最小的两个节点合并。

目标：

最小化带权路径长度 WPL。

Huffman 编码是：

前缀编码。

若一棵严格 Huffman 树共有 $N$ 个节点，则叶节点数为 $(N+1)/2$ ，可得到同样数量的码字。计算编码总位数时，使用：

\mathrm{WPL}=\sum_i w_i l_i

其中 $w_i$ 是频率或权重， $l_i$ 是对应码长。

哈希、KMP 与折半查找

链地址法处理冲突时，先算 $H(key)$ ，再统计落到同一桶中的记录数。字符串模式匹配中，经典 KMP 的预处理和匹配总时间复杂度为 $O(m+n)$ 。

含 $n$ 个元素的有序表，其折半查找判定树高度按“根为第 1 层”计为：

\left\lceil\log_2(n+1)\right\rceil

图的存储

存储方式	空间复杂度	更适合
邻接矩阵	$O( \lvert V \rvert ^2)$	稠密图、频繁判断两点是否相邻
邻接表	$O( \lvert V \rvert + \lvert E \rvert )$	稀疏图、遍历某点的邻边

BFS 与 DFS

使用邻接表时，BFS 与 DFS 的时间复杂度都是 $O(|V|+|E|)$ ；使用邻接矩阵时是 $O(|V|^2)$ 。

BFS 可以求：

无权图的最短路径。

最小生成树

含 $|V|$ 个顶点的连通图，其最小生成树含 $|V|-1$ 条边。MST 最小化的是总边权，不保证任意两点间的路径都是原图最短路径。

Prim

特点：

从已经形成的树不断向外扩张。

通常更适合稠密图。

Kruskal

步骤是：将边按权值升序排列，依次选择不会形成环的边，直到选满 $|V|-1$ 条。

经典数据结构：

并查集。

通常更适合稀疏图。

最短路径

Dijkstra

单源最短路。

必须记住：

不能正确处理负权边。

Floyd

Floyd 用动态规划求所有点对最短路，时间复杂度为 $O(|V|^3)$ ，允许负权边，但不能有负权环。

拓扑排序

只有 DAG 才存在拓扑排序。

如果：

图中仍有节点未输出，但找不到入度为 0 的节点，

说明：

存在环。

排序稳定性

排序	平均	最坏	稳定
冒泡	$O(n^2)$	$O(n^2)$	✓
插入	$O(n^2)$	$O(n^2)$	✓
选择	$O(n^2)$	$O(n^2)$	✗
快排	$O(n\log n)$	$O(n^2)$	✗
归并	$O(n\log n)$	$O(n\log n)$	✓
堆排	$O(n\log n)$	$O(n\log n)$	✗
希尔	与步长相关	—	✗

口诀：“快选堆希不稳定”，即快速、选择、堆、希尔排序不稳定；冒泡、插入、归并稳定。

从中间结果识别排序

冒泡排序每趟会把当前最大或最小元素固定到一端；
选择排序每趟直接选出一个极值放到最终位置；
插入排序的已处理前缀始终有序；
快速排序一趟结束后，基准元素到达最终位置，左侧不大于它、右侧不小于它；
归并排序会出现长度为 $1,2,4,\ldots$ 的局部有序段；
堆排序先建堆，再不断把堆顶与未排序区末尾交换。

若键值范围很小且已知，例如大量成绩都在 $0$ 到 $150$ 之间，桶 / 计数思想可达到 $O(n+k)$ ；按输入顺序写入每个桶还能保持稳定。这比机械地在快排和归并之间选择更符合题意。

算法设计

动态规划

两个核心性质是最优子结构与重叠子问题。状态转移可抽象为：

dp[s]=\operatorname{opt}_{a\in A(s)}\{dp[T(s,a)]+w(s,a)\}

经典问题：

0-1 背包；
最长公共子序列；
矩阵链乘。

贪心

核心：

每一步选择当前最优。

但是：

局部最优并不天然保证全局最优。

经典贪心：

Huffman；
Prim；
Kruskal。

操作系统

进程与线程

可以先用一句话记：“进程是资源分配单位，线程是 CPU 调度的基本单位。”

同一进程内通常共享	每个线程独立拥有
代码、全局数据、堆	程序计数器 PC
地址空间、打开文件	寄存器、栈

高频判断：

同一进程中的线程共享栈。

错误。

进程状态

经典三状态为运行、就绪、阻塞，常见转换如下：

状态转换	原因
运行 $\to$ 就绪	时间片耗尽或被抢占
运行 $\to$ 阻塞	等待 I/O 或事件
阻塞 $\to$ 就绪	等待的事件完成
就绪 $\to$ 运行	获得 CPU

阻塞态不能直接变为运行态，必须先进入就绪队列。

调度算法

FCFS

先来先服务。

问题：

护航效应。

SJF

短作业优先。

优点：

平均等待时间较低。

问题：

长作业可能饥饿。

Round Robin

时间片轮转。

时间片太大：

接近 FCFS。

时间片太小：

上下文切换开销增加。

Priority

可能产生：

饥饿。

经典解决方法：

Aging。

信号量

互斥访问的基本结构是 P(mutex) $\to$ 临界区 $\to$ V(mutex)。若只保护一个临界区，初值为 $1$ ；若表示 $n$ 个同类资源，计数信号量初值为 $n$ 。

P / V 操作本身必须是原子操作。若信号量当前值为正，它通常表示可用资源数；若采用允许负值的定义，负值的绝对值表示等待进程数。

把高级语句拆成 load、修改、store 后，要考虑指令交错。例如两个进程分别执行 x++ 和 x--，结果不一定回到原值，因为一次写回可能覆盖另一次更新。

死锁

四个必要条件是：互斥、请求并保持、不可剥夺、循环等待。

破坏其中任意一个：

可以从根本上预防死锁。

银行家算法

属于：

死锁避免。

核心：

保证系统保持在安全状态。

特别注意：

不安全状态 ≠ 已经发生死锁。

不安全只是说明：

存在进入死锁的风险。

银行家算法的核心关系是：

\mathrm{Need}[i,j]=\mathrm{Max}[i,j]-\mathrm{Allocation}[i,j]

资源分配图化简则用于判断当前状态：能不断消去可完成进程，最终全部消去表示可完全简化。

I/O、SPOOLing 与中断

CPU 干预从多到少可粗略比较为：程序查询 I/O、中断驱动 I/O、DMA、通道 I/O。DMA 适合成块数据传输，通道可执行更独立的 I/O 程序。

关中断通常只屏蔽可屏蔽硬件中断，不意味着所有异常、软件中断和不可屏蔽中断都失效。

SPOOLing 用磁盘上的输入井 / 输出井和内存缓冲区模拟脱机 I/O，把独占设备改造成可由多个作业共享的虚拟设备，主要目标是提高 I/O 设备利用率。

分页

逻辑地址由“页号 $+$ 页内偏移”组成。若页面大小为 $2^k$ 字节，则页内偏移占 $k$ 位：

4\ \mathrm{KiB}=2^{12}\ \mathrm{B}\Rightarrow12\ \mathrm{bits},\qquad 8\ \mathrm{KiB}=2^{13}\ \mathrm{B}\Rightarrow13\ \mathrm{bits}

若逻辑地址共 $m$ 位，页号位数就是 $m-k$ 。

多级页表

先算每页能容纳多少页表项：

E=\frac{\text{page size}}{\text{PTE size}}

若 $E=2^e$ ，每一级页表索引最多覆盖 $e$ 位页号。虚拟地址共 $v$ 位、页内偏移 $k$ 位时，页号有 $v-k$ 位，所需级数至少为：

\left\lceil\frac{v-k}{e}\right\rceil

例如页面 $4\,\mathrm{KiB}$ 、页表项 $8\,\mathrm B$ ，一页可放 $512=2^9$ 项； $48$ 位虚拟地址的页号有 $36$ 位，因此需要 $4$ 级页表。

TLB

TLB：

页表项的高速缓存。

TLB 命中意味着：

不需要再次访问内存中的页表来获得页框号。

Page Fault

发生条件：

当前访问的页面不在物理内存中。

典型处理流程是：选择空闲页框或牺牲页 $\to$ 必要时写回脏页 $\to$ 从磁盘读入目标页 $\to$ 更新页表与 TLB $\to$ 重新执行引发缺页的指令。

页面置换

OPT

选择：

未来最长时间不会访问的页面。

理论最优，但实际无法预测未来。

FIFO

选择：

最早进入内存的页面。

可能产生：

Belady 异常。

即：

增加页框数反而增加缺页次数。

LRU

选择：

最近最久没有访问的页面。

LRU 不产生 Belady 异常。

分页与分段

方式	划分依据	大小	主要碎片
分页	物理存储管理	固定	内部碎片
分段	程序的逻辑单位	可变	外部碎片

分段地址转换先检查段号是否越界、段是否在内存、访问权限是否允许、段内偏移是否超过段长。只有全部通过，才计算：

\text{physical address}=\text{segment base}+\text{offset}

段页式系统在不考虑 TLB 和 Cache 时，通常要访问段表、页表，最后再访问目标数据，至少三次内存访问。

动态分区与磁盘调度

动态分区中的最佳适配会选择“能满足请求的最小空闲分区”，每次分配和释放后都要重新画空闲区，不能只比较总空闲量。

SCAN 又称电梯算法：磁头沿当前方向服务途中遇到的请求，到达该方向端点后再反向。题目若明确磁盘编号范围，移动距离通常要把走到端点的距离计入；若题目采用 LOOK，则只走到该方向最远请求处。先分清 SCAN 与 LOOK 再求和。

文件系统

文件分配方式	随机访问	扩展	主要问题
连续分配	快	困难	外部碎片、需预知长度
链接分配	慢	容易	指针开销、可靠性
索引分配	支持	容易	索引块开销

多级索引题先算一个间接索引块能存多少地址，再逐级乘容量。多级目录的核心作用是解决命名冲突并支持分组管理，不是为了节省文件数据空间。

位示图一位对应一个盘块。若分区容量为 $C$ 、盘块大小为 $B$ ，位数为 $C/B$ ，位示图占用的盘块数还需再除以 $8B$ 并向上取整。

计算机网络

五层模型

层	典型内容
应用层	HTTP、DNS、SMTP
传输层	TCP、UDP
网络层	IP、ICMP
数据链路层	Ethernet
物理层	Bit

网络设备

设备	主要工作层次	转发依据
Hub	物理层	比特信号，不识别地址
Switch	数据链路层	MAC 地址
Router	网络层	IP 地址

以太网交换机本质上是多端口网桥。每个交换机端口构成独立冲突域，但默认仍属于同一个广播域；路由器才隔离广播域。共享式 $10\,\mathrm{Mbps}$ 以太网由站点竞争带宽，交换式以太网的每个全双工端口可以独享端口速率。

停等、GBN 与 SR

三份试卷都出现了链路层可靠传输，是本组真题最值得优先练的计算题之一。

协议	接收窗口	确认与重传
停等	$1$	发一帧，等确认后再发
GBN	通常为 $1$	累计确认；超时后从最早未确认帧起重传
SR	可大于 $1$	分别确认；只重传丢失或超时帧

采用 $k$ 位序号时，常用窗口约束是：

W_{GBN}\le 2^k-1,\qquad W_{SR}\le 2^{k-1}

停等协议忽略确认帧发送时间时，利用率为：

U=\frac{T_t}{T_t+2T_p}=\frac{L/R}{L/R+2T_p}

滑动窗口协议可近似为 $U=\min(1, W T_t/(T_t+2T_p))$ 。若确认帧也很长，分母还要加确认帧发送时间。

介质访问控制

CSMA/CD 用于经典共享式有线以太网，边发送边检测冲突；
CSMA/CA 用于 IEEE 802.11，无线节点难以边发边检测，使用退避、确认，并可用 RTS / CTS 预约信道；
CDMA、TDMA、FDMA 通过码、时间或频率划分资源，本身不是竞争型 CSMA。

CSMA/CD 要求发送方在最坏往返传播时间内仍未发完最小帧，才能检测碰撞：

L_{min}\ge 2T_pR

最小帧长减半而速率不变时，允许的最大站间距离也应减半。

ARP

ARP 完成本地网络中的 $\mathrm{IPv4}\to\mathrm{MAC}$ 地址映射，不要记反。

IPv4 与 IPv6

IPv4 地址长度为 $32$ bit，IPv6 地址长度为 $128$ bit。

CIDR

IPv4 前缀为 $/p$ 时，主机位数 $h=32-p$ ，地址块大小为：

N=2^h=2^{32-p}

例如 192.168.1.0/24 有 $h=8$ 个主机位，共 $2^8=256$ 个地址。传统普通子网扣除网络地址和广播地址后，可分配主机地址数为 $2^8-2=254$ 。

建议直接背：

前缀	地址数
`/24`	256
`/25`	128
`/26`	64
`/27`	32
`/28`	16
`/29`	8
`/30`	4

路由转发使用最长前缀匹配：将目的地址分别与表项掩码按位与，匹配项中前缀最长者优先；若都不匹配才走默认路由。

IPv4 分片通常发生在沿途 MTU 更小的路由器上，目的主机负责重组。除最后一片外，每片数据长度通常是 $8$ 字节的整数倍，因为片偏移以 $8$ 字节为单位。

TCP 与 UDP

特性	TCP	UDP
连接	面向连接	无连接
可靠性	提供可靠、有序传输	尽力而为，不保证可靠
数据边界	字节流，无消息边界	面向报文，保留消息边界
控制机制	流量控制、拥塞控制	协议本身不提供
首部与开销	较大	较小

判断：

UDP 一定比 TCP 快。

这种绝对化表述通常不成立。

TCP 三次握手

典型过程为：客户端发送 SYN $\to$ 服务端回复 SYN + ACK $\to$ 客户端发送 ACK。三次握手使双方确认彼此的发送与接收能力，并同步初始序列号。

序号与确认号

TCP 序号按字节编号。收到序号为 $S$ 、有效载荷为 $L$ 字节的连续报文段后，期望确认号为：

ACK=S+L

SYN 和 FIN 各自也消耗一个序号。发送报文段时，本端序号取自己的发送序列，确认号则针对对方的数据，二者不要混算。

TCP 四次挥手

典型报文顺序为 FIN $\to$ ACK $\to$ FIN $\to$ ACK。

原因：

TCP 是全双工协议，两个方向需要分别关闭。

TIME_WAIT

主动关闭方通常进入 TIME_WAIT，持续时间为 $2\times\mathrm{MSL}$ 。

主要作用：

最后一个 ACK 丢失时还能重新发送；
等待旧连接报文从网络中消失。

流量控制与拥塞控制

不要混。

流量控制

目标：

防止发送方速度超过接收方处理能力。

主要关注接收窗口 rwnd。

拥塞控制

目标：

防止网络本身过载。

经典机制包括慢启动、拥塞避免、快速重传和快速恢复。实际发送窗口受二者共同限制，可粗略记为：

\text{send window}=\min(\mathrm{rwnd},\mathrm{cwnd})

经典题设中发生超时后，cwnd 通常回到 $1\,\mathrm{MSS}$ ，慢启动门限设为原窗口的一半；先指数增长到门限，再线性增长。每轮都要与接收窗口 rwnd 取最小值，实际发送窗口不可能超过接收方公布的窗口。

交换与时延

一条报文经过 $h$ 段等速链路、每段采用存储转发，忽略传播和处理时延时，报文交换总发送时间约为：

T_{msg}=h\frac{L}{R}

若分成 $N$ 个等长分组，流水发送，总时间约为：

T_{pkt}=(N+h-1)\frac{L/N}{R}

虚电路在连接建立阶段选择路径，后续分组沿既定虚电路转发；数据报网络则通常对每个分组独立进行路由选择。

DNS

DNS 主要用于：

域名和其他资源记录的解析。

普通查询通常使用 UDP 端口 $53$ ，但区域传送、响应过大或回退等情况可能使用 TCP。

但某些情况会使用 TCP。

所以：

“DNS 永远使用 UDP。”

错误。

HTTP / HTTPS

HTTP 是无状态的应用层协议；HTTPS 是运行在 TLS 之上的 HTTP，即 $\mathrm{HTTPS}=\mathrm{HTTP}+\mathrm{TLS}$ 。

路由协议

协议	类型 / 思想	使用范围
RIP	距离向量，Bellman–Ford 思想	自治系统内部
OSPF	链路状态，Dijkstra 算法	自治系统内部
BGP	路径向量	自治系统之间

计算机组成原理

如果时间非常有限，这部分优先级低于前面几门，但不要完全不看。

补码

$n$ 位有符号补码的表示范围是：

-2^{n-1}\le x\le 2^{n-1}-1

例如 $8$ 位补码的范围是 $[-128,127]$ 。

Cache

典型地址可划分为 Tag | Index | Offset。若 Cache 块大小为 $2^b$ B，则块内偏移占 $b$ 位；若共有 $2^s$ 组，则组索引占 $s$ 位，其余高位作为标记 Tag。

映射方式包括直接映射、全相联与组相联。

直接映射或组相联中，先由主存地址算块号：

\text{block number}=\left\lfloor\frac{\text{address}}{\text{block size}}\right\rfloor, \qquad \text{set}=\text{block number}\bmod\text{set count}

计算 Cache 行需要的总位数时，不能只算数据区，还要加入 Tag、有效位；若采用回写策略，通常还需要脏位。若题目给的是“Cache 数据区大小”，先用它除以块大小得到行数。

局部性

时间局部性：

最近访问的数据，很可能很快再次访问。

空间局部性：

访问某个地址后，其附近地址很可能很快被访问。

存储层次

速度大致满足：

\mathrm{Register}>\mathrm{Cache}>\mathrm{Memory}>\mathrm{SSD/Disk}

容量通常相反。

流水线

流水线的主要目标：

提高指令吞吐率。

并不意味着：

单条指令本身的延迟一定降低。

三种主要冒险是结构冒险、数据冒险、控制冒险，最常见的数据相关是 RAW（Read After Write）。理想情况下， $k$ 级流水线执行 $n$ 条指令需要约 $k+n-1$ 个时钟周期，而非流水方式约需 $kn$ 个周期。

流水线时钟周期至少等于最慢功能段的延迟。若各段为 $90,80,70,60\,\mathrm{ns}$ ，忽略段间寄存器开销，周期至少为 $90\,\mathrm{ns}$ 。

寻址与 RISC

相对寻址的目标地址通常为“取完当前指令后的 PC + 符号扩展位移”。若指令长 $2$ 字节、起始地址为 3000H、位移为 06H，取指后 PC 为 3002H，目标为 3008H。

RISC 通常具有指令种类少、格式较规整、寻址方式少、通用寄存器多、便于流水的特点，并常采用硬布线控制；“RISC 普遍采用微程序控制器”通常是错误项。

DMA

DMA 允许：

外设与内存之间直接进行较大规模的数据传输。

作用：

减少 CPU 对每一个数据字传输的参与。