怎么看这一部分
页面里有四种标记,含义固定。
用比喻和白话先把“这是在解决什么问题”说清楚,再看定义。
典型计算或手推过程,答案在虚线下方,建议先自己做一遍。
考试最容易丢分的地方,右侧栏会自动汇总前三条。
不在考试大纲内:读懂原理即可,不用背公式、不用练题。
行内标记:大纲内仅做理解
每讲第 00 节都有完整的大纲对照表,可点击跳到对应小节。
三科十讲
与原章节一一对应;原章节保留了交互模拟器和更多图示,可从每讲页脚跳过去。
建议顺序
数据结构四讲环环相扣,先连续学完;操作系统和计网可以交替推进。
跨科联系:堆(DS·5)↔ 堆排序(DS·8)↔ 优先队列;B+ 树(DS·7)↔ 文件索引(OS·4);Dijkstra(DS·6)↔ OSPF(CN·4);内存管理(OS·3)↔ 组成原理的 Cache / TLB / 虚拟存储器。
“仅做理解”一览
以下内容不在大纲条目内,复习时间紧时可以只看懂、不练题。
| 讲 | 仅做理解的内容 |
|---|---|
| 内存管理 | 程序的链接与装入方式;覆盖与交换;伙伴系统 / Slab;反置页表;请求分段;页面缓冲算法、LFU |
| 文件管理 | 散列文件、记录成组与分解;单级 / 两级目录;文件系统层次结构模型 |
| I/O 管理 | 通道控制方式与通道控制表;异步 I/O、I/O 多路复用;扇区交替编号 / 错位命名;RAID |
| 树与森林 | 三叉链表;后序线索树找后继的分类讨论;并查集 O(α(n)) 复杂度 |
| 图 | 有向无环图描述表达式(真题出现过,建议会做);Bellman-Ford、SPFA |
| 查找 | 插值查找、斐波那契查找;红黑树的删除调整 |
| 排序 | 计数排序、桶排序 |
| 网络层 | VPN;IPv4→IPv6 过渡(双栈、隧道);IGMP 与组播路由协议 |
| 传输层 | SACK;糊涂窗口综合征与 Nagle 算法;CUBIC、BBR、QUIC |
| 应用层 | P2P 文件分发时间公式;IMAP 与网页邮箱;HTTPS / TLS、HTTP/2、HTTP/3、CDN |