一、数据结构

选择题

1.基本概念与理解：2009.1、2015.1

2.时间复杂度：2011.1、2012.1、2013.1、2014.1、2017.1、2019.1

3.链表：2016.1、2016.2、2021.1

4.栈：2009.2、2010.1、2011.2、2013.2、2017.2、2018.2、2020.2

5.队列：2010.2、2011.3、2014.3、2016.3、2021.2

6.中/后缀表达式(栈的应用)：2012.2、2014.2、2018.1

7.KMP：2015.8、2019.9

8.二叉树的基本计算：2009.5、2010.5、2011.4、2011.6、2013.4、2018.4、2020.3、2021.5

9.二叉树遍历：2009.3、2011.5、2012.3、2015.2、2017.4、2017.5

10.线索二叉树：2010.3、2013.5、2014.4

11.二叉搜索树：2011.7、2013.6、2018.6、2020.5

12.AVL树：2009.4、2010.4、2012.4、2013.3、2015.4、2019.4、2021.6

13.哈夫曼树/前缀编码：2010.6、2014.6、2015.3、2017.6、2018.5、2019.3

14.森林：2009.6、2014.5、2016.5、2019.2、2020.4、2021.4

15.图相关基本概念：2011.8、2017.3

16.图/矩阵的基本计算：2009.7、2010.7、2013.7、2016.4、2017.7、2018.3、2020.1、2021.3

17.图的遍历：2012.5、2013.8、2015.5、2016.6、2020.6

18.最小生成树：2012.8、2015.6、2020.7

19.最短路：2012.7、2016.8、2021.8

20.DAG基础：2019.6(自动机)

21.拓扑排序：2010.8、2012.6、2014.7、2016.7、2018.7、2021.7

22.关键路径：2013.9、2019.5、2020.8

23.二分查找：2010.9、2015.7、2016.9、2017.8

24.B树：2009.8、2012.9、2013.10、2014.9、2018.8、2020.10、2021.9

25.B+树：2016.10、2017.9

26.散列：2011.9、2014.8、2018.9、2019.8

27.堆：2009.9、2011.11、2015.10、2018.11、2020.9、2021.11

28.排序：2009.10、2010.10、2010.11、2011.10、2012.10、2012.11、2013.11、2014.10、2014.11、2015.9、2015.11、2016.11、2017.10、2017.11、2018.10、2019.7、2019.10、2020.11、2021.10

29.最佳归并(k叉哈夫曼树)：2019.11

大题

1.数组代码：2010.42、2011.42、2013.41、2018.41、2020.41

2.链表代码：2009.42、2012.42、2015.41、2019.41

3.二叉树代码：2014.41、2017.41

4.图代码：2021.41

5.快排思想代码：2016.43

6.队列简答：2019.42

7.二叉树基础简答：2016.42

8.哈夫曼树简答：2012.41、2020.42

9.图基础简答：2015.42(离散数学...)

10.最小生成树简答：2017.42、2018.42(套皮计网)

11.最短路简答：2009.41、2014.42(套皮计网)

12.关键路径简答：2011.41

13.查找简答：2013.42

14.散列简答：2010.41

15.排序简答：2021.42

二、计算机组成原理

选择题

一、计算机系统概述

1.冯诺依曼结构的理解：2018.12、2019.12

2.计算机系统的层次结构：2015.12、2016.12

3.性能指标：2010.12、2011.12、2012.12、2013.12、2014.12、2017.12、2019.16、2021.12

二、数据的表示和运算

1.定点数的表示与计算：2010.13、2013.14、2014.13、2015.13、2018.13、2018.16、2021.13

2.类型转换与符号扩展：2009.12、2010.14、2012.13、2016.13、2019.13

3.大小端：2016.14、2018.15、2020.14

4.结构体边界对齐：2012.15、2020.14

5.浮点数的表示与加减：2009.13、2015.14

6.IEEE754浮点数：2011.13、2012.14、2013.13、2014.14、2018.14、2020.13、2021.14

7.PSW(CF,ZF,SF,OF)：2011.17、2018.19

三、存储系统

1.各种基础RAM、ROM的基本概念：2010.16、2011.14、2012.16

2.DRAM相关计算：2014.15、2017.13、2018.17

3.SRAM与DRAM：2015.17

4.主存扩展：2009.15、2010.15、2011.15、2016.16、2021.15

5.磁盘基本概念(新大纲计算相关的全部挪到OS了)：2013.20、2019.20

6.多体并行低位交叉：2015.18

7.局部性原理：2017.14

8.Cache相关：2009.14、2009.21、2010.17、2012.17、2013.16、2014.16、2015.15、2015.16、2016.15、2020.15、2021.16

四、指令系统

1.指令格式、指令/数据寻址：2009.16、2011.16、2013.17、2014.17、2016.17、2018.18、2017.15、2017.16、2018.18、2019.15、2020.16

2.CISC和RISC：2009.17

五、中央处理器

1.寄存器等部件基础：2010.18、2019.17、2020.12、2021.17

2.指令周期：2009.11、2011.19、2016.20

3.数据通路基本概念：2021.18

4.硬布线和微程序：2009.19

5.微指令相关：2012.18、2014.18、2017.18

6.指令流水线基本概念与计算：2009.18、2011.18、2013.18、2017.19、2018.20、2020.17

7.流水线冒险：2010.19、2016.19、2019.18

8.超标量流水线：2017.17

9.多处理器：2022之后补

六、总线

1.总线、总线事务、总线定时等基本概念：2011.20、2012.21、2014.20、2015.19、2016.21、2017.20、2018.21、2021.19

2.总线相关计算：2009.20、2012.19、2014.19、2019.19、2020.19

七、输入/输出系统

1.I/O接口、I/O端口等基本概念：2014.21、2015.21、2017.21、2021.20

2.定时查询方式：2011.22

3.中断：2010.21、2011.21、2012.22、2014.22、2017.22、2018.22、2019.14、2019.21、2020.21、2021.21、2021.22

4.DMA：2017.32、2019.22、2020.22

5.中断和DMA对比：2013.22

八、新大纲已删除

1.总线标准：2010.20、2012.20、2013.19

2.显示屏刷新（新大纲外设移动合并到了OS中，但是OS中并没有磁盘外的具体外设考点，可以认为显示屏等已经删除，但是显示屏的工作原理实际上是一个很重要的常识，详细了解一下只有好处没有坏处，尽管确实可能已经不在408考点范围中了）：2010.22

3.海明码(准确来说是上一次大纲就已经删除...)：2013.15

大题

一、计算机系统概述

1.2012.43(1)：性能指标

2.2016.44(1)：简单计算

二、数据的表示和运算

1.2011.43：定点数加减

2.2012.44(1)：定点数

3.2017.43：读代码、整数类型、定点数、浮点数、IEEE754浮点数

4.2017.44(4)：IEEE754浮点数

5.2019.45(4)：数据类型

6.2020.43(4)：乘法溢出判断

7.2021.43(3)(4)：乘法溢出判断、符号扩展

三、存储系统

1.2010.44：Cache总容量、Cache映射、Cache命中率

2.2011.44：逻辑地址(OS)、Cache/TLB映射

3.2012.43(1)：Cache命中率

4.2012.43(4)：多体并行低位交叉

5.2013.43(4)：Cache命中率

6.2014.44(1)(2)：存储器编址基础

7.2014.45(2)：Cache数据容量、Cache命中率

8.2014.45(3)：TLB

9.2016.45：逻辑地址(OS)、Cache/TLB映射、Cache写策略等基础

10.2018.44：逻辑地址(OS)、Cache/TLB映射、Cache总容量

11.2020.44：Cache映射、Cache行的各位、Cache命中情况

12.2021.45：逻辑地址(OS)、Cache/TLB映射、LRU

四、指令系统

1.2010.43：指令/数据寻址、MAR、MDR、PC

2.2013.44：指令/数据寻址、PC、PSW(CF,ZF,NF)

3.2014.44(3)：指令/数据寻址

4.2014.45(1)：读代码

5.2015.43：数据通路中各种寄存器和其他部件的分析

6.2015.44(1)(2)：指令/数据寻址

7.2017.44(1)(2)(3)：CISC和RISC、指令/数据寻址、PSW(CF)

8.2019.45(1)(2)(3)(5)：读代码、常用指令基础、指令/数据寻址、PSW(OF)

9.2021.43(1)(2)(5)：MAR、MDR、通用寄存器、指令格式、

五、中央处理器

1.2009.44：控制信号

2.2012.44(2)(3)：指令流水线计算、流水线冒险

3.2014.44(4)：流水线冒险

4.2014.45(3)：异常分析

5.2015.44(3)：控制信号

6.2015.44(4)：指令周期

7.2020.43(1)(2)(3)：对各部件功能、指令周期的理解

8.2021.43(1)：ALU

六、总线

1.2013.43(1)(2)(3)：总线带宽、猝发传输

七、输入/输出系统

1.2009.43：中断、DMA

2.2012.43(2)(3)：DMA

3.2016.44(2)：中断

4.2018.43：定时查询方式、中断、DMA

三、操作系统

选择题

一、计算机系统概述

1.单道批、多道批、分时、实时：2009.23、2016.23、2018.23

2.用户态、核心态、系统调用：2010.23、2011.24、2012.23、2013.28、2014.25、2015.24、2017.24、2017.28、2019.25、2021.23、2021.32

3.中断处理：2012.24、2013.23、2013.25、2018.29、2020.18、2020.25、

4.中断与异常：2009.22、2015.22、2016.22、2020.20、

5.程序的链接与装入(原属旧大纲第三章)：2011.30

6.操作系统引导(新大纲加入,原常识题?)：2013.29

二、进程与线程

1.简单的并发计算：2012.29、2016.24

2.进程的状态与转换：2010.24、2012.30、2014.26、2015.25、2018.27、2019.24、2021.24、2021.27

3.进程的管道通信：2014.31

4.进程、子进程、线程：2011.25、2012.31、2020.29

5.多线程模型：2019.23

6.作业(进程)调度算法：2009.24、2010.26、2011.23、2013.31、2014.23、2017.23、2017.27、2018.24、2019.27、2020.26、2021.25

7.信号量基础：2010.25

8.管程：2016.32、2018.28

9.死锁基础：2009.25、2014.24、2016.25、2019.30、2021.31

10.死锁预防、死锁避免、死锁检测基本概念：2015.26、2020.32

11.安全序列和银行家算法：2011.27、2012.27、2013.32、2018.26、2020.27

12.临界区/进程同步与互斥的结果分析/实现方法：2010.27、2011.32、2016.27、2016.30、2018.25、2018.32

三、内存管理

1.内存管理、虚拟内存等基本概念：2009.26、2012.25、2014.28

2.连续分配管理(主要是动态分区分配的首次适应等四种)：2010.28、2017.25、2019.32

3.页表、段表等相关概念与计算：2009.27、2010.29、2011.28、2013.30、2014.32、2016.28、2019.28、2019.31、2021.29

4.页面置换算法：2011.29、2014.30、2015.27、2015.30、2016.26、2019.29、2020.28、2021.28

5.工作集：2016.29

四、文件管理

1.文件、目录、FCB、索引节点等基本概念与理解：2009.30、2010.31、2012.28、2014.29、2017.30、2018.31、2020.23、2021.30

2.软链接、硬链接：2009.31、2017.31

3.文件的物理结构(连续分配、链接分配、索引分配与索引节点)：2009.28、2010.30、2013.24、2013.26、2015.29、2020.24、2020.31

4.外存空闲空间管理：2014.27、2015.31、2019.26

五、I/O管理

1.I/O基础：2009.32、2012.32、2013.23

2.I/O软件层次结构(I/O子系统)：2011.26、2012.26

3.设备独立性：2020.30

4.缓冲区：2011.31、2013.27、2015.28

5.SPOOLing技术：2016.31

6.磁盘基础与计算(原属旧大纲第四章,下同)：2013.21、2015.20、2017.26、2017.29

7.磁盘调度：2009.29、2015.32、2018.30、2021.26

大题

一、计算机系统概述

1.2021.46(1)：操作系统引导(明明是新大纲...)

二、进程与线程

1.PV之简单的同步与互斥：2013.45(套皮计组数电)、2017.46、2020.45

2.PV之生产者消费者：2011.45、2014.47、2015.45

3.PV之哲学家进餐：2019.43

4.PV之吸烟者：2009.45

5.临界区互斥实现方法的分析：2021.45

6.2016.46：优先级调度的动态优先级设计

7.2017.45(3)：进程的状态与转换

三、内存管理

1.2009.46：逻辑地址、页表、TLB、驻留集、页面置换算法

2.2010.46：逻辑地址、页表、页面置换算法

3.2012.45：驻留集、局部性原理

4.2013.46：逻辑地址、二级页表

5.2015.46：逻辑地址、二级页表

6.2017.45(1)(2)：逻辑地址、二级页表

7.2018.45：逻辑地址、二级页表

8.2020.46：逻辑地址、二级页表、局部性原理

四、文件管理

1.2010.45(1)：外存空闲空间管理

2.2011.46：文件的物理结构

3.2012.46：索引分配

4.2014.46：连续分配、链接分配

5.2016.47：目录分析、链接分配、FAT

6.2018.46：索引分配

五、I/O管理

1.2010.45(2)(3)：磁盘调度、磁盘调度时间(原属旧大纲第四章,下同)

2.2019.44：磁盘基础、磁盘调度、磁盘物理地址

3.2021.46(2)(3)：磁盘格式化

四、计算机网络

选择题

一、计算机网络体系结构

1.基本概念与理解：2010.33、2020.33

2.OSI：2009.33、2013.33、2014.33、2016.33、2017.33、2019.33

3.TCP/IP：2011.33、2012.33、2018.33、2021.33

二、物理层

1.编码：2013.34、2015.34、2021.34

2.最大/实际数据传输速率、波特率(调制/码元/奈奎斯特/香农)：2009.34、2011.34、2014.35、2016.34、2017.34

3.电路交换、报文交换、分组交换(数据报与虚电路)：2010.34、2013.35、2020.34

4.接口特性：2012.34、2018.34

三、数据链路层

1.滑动窗口、停-等、GBN、SR：2009.35、2011.35、2012.36、2014.36、2015.35、2018.36、2019.35、2020.36

2.CDMA等、三种CSMA、CSMA/CD、CSMA/CA：2009.37、2011.36、2013.36、2014.37、2015.36、2018.35、2019.36、2020.37

3.以太网(802.3)与交换机基础：2009.36、2012.35、2013.38、2015.37、2016.36、2019.34

4.802.11帧三地址：2017.35

5.以太网组网实验：2014.34、2016.35

四、网络层

1.SDN：2022之后补

2.IP分组字段、IP地址、子网划分、路由聚合等基础：2010.37、2011.38、2012.39、2017.36、2017.38、2018.37、2018.38、2019.37、2021.35、2021.36

3.RIP、OSPF、BGP：2010.35、2016.37、2017.37、2021.37

4.NAT：2016.38

5.ARP：2012.38

6.ICMP：2010.36

7.IP路由器基础：2010.38、2012.37、2020.35(含SW)

8.IP组网实验、路由表等：2011.37、2015.38、2016.39

五、传输层

1.UDP：2014.39、2018.39

2.TCP：2009.38、2009.39、2010.39、2011.39、2011.40、2013.39、2014.38、2015.39、2017.39、2019.38、2019.39、2020.38、2020.39、2021.38、2021.39、2021.40

六、应用层

1.C/S与P2P：2019.40

2.DNS：2010.40、2016.40

3.FTP：2009.40、2017.40

4.SMTP与POP3：2012.40、2013.40、2015.33、2018.40

5.HTTP/1.1：2015.40、2020.40(含DNS)

6.多层基础：2014.40

七、新大纲已删除

1.HDLC：2013.37

大题

三、数据链路层

1.2010.47：CSMA/CD的时延

2.2011.47(1)(2)：MAC帧字段

3.2017.47：GBN

四、网络层

1.2009.47：IP组网实验、子网划分、路由表、路由聚合

2.2011.47(4)：IP分组字段

3.2012.47：IP分组字段(含TCP基础)

4.2013.47：IP组网实验、路由聚合、路由表、BGP

5.2014.43：路由聚合、路由表、IP基础、默认路由

6.2015.47：IP组网实验、DHCP、ARP

7.2018.47：IP地址、IP分组长度

8.2019.47：IP组网实验、NAT

9.2020.47：IP组网实验、NAT

10.2021.47：IP组网实验、NAT、ARP

五、传输层

1.2016.41：TCP

六、应用层

1.2011.47(3)：HTTP/1.1

备注

有些地方分的有点乱，比如中断相关的是分给计组还是OS，这里我并没有完全按题号所在位置进行归划，而是依照知识点本身的倾向性，比方说2017的32题明显是OS的末尾了，我依然将这道DMA归类给了计组。

大题有些多考点的，特别是计组，有时候东一头西一头，而且有时候也没有明显感觉属于什么考点，感觉是学完之后产生的理解或说学科常识，我也勉强进行细碎的划分了。当然因为一道大题多考点不易按考点规划，所以没有按数据结构那样划分，而是反过来的映射，实际上个人认为大题这样去看考点可能效果反而好一些。

有些地方可能分得过粗或者比较过细，比如TCP，分的很粗，不管是三次握手、seq/ack/mss等基础、还是拥塞控制，我全归到TCP这一个点了。应该说这种考点比较重视整体性的学习和理解，而且越分越乱，所以这样整体划分，整体拿出来练习，应该是比较好的。再比如一些细碎的点，我就直接归划到了xxx基础，因为不值得单拿。但是有些，比如DAG基础、k叉哈夫曼树，显然视作单独的题型比较好，尽管就只考过一道。总的来讲，本文中的划分方式、粗粒度和细粒度大致就是遵循这样的想法。