408近年大题真题总结（后续整理入笔记）

前言

本文并不是多么细致地讲解大题，而是告诉你大题都考什么，让你心理有个底，因为我自己就是刚开始只学东西，一点大题都不看。

题型分析

综合18-23年的真题，一套卷从前到后基本只会考这些题型

1. 纯算法设计（难）
2. 算法+其他知识的综合设计，或者分析
3. 硬件系统分析（难）
4. 内存+cache
5. 虚拟内存
6. PV操作（难）
7. 文件系统
8. IO性能计算
9. 计网综合

算法设计题

题型
暴力解法

如果不追求高分（135以上），算法题可以考虑暴力解法，对于计算机科班的同学来说，只要熟悉基本数据结构的操作方法，就一定可以写出来这道题，拿到7分以上的分。

建议：

1. 一般会分为三部分
   • 首先是写算法思路。尽量分点，细节作答，比如邻接矩阵，你不要想当然认为考官知道度怎么求，你要告诉他你是用遍历一行非零元素个数的方式求度。
   • 其次是代码。和平时写代码一样，可以声明辅助函数，除了不能导库。另外注意三思而后行，辅助变量别漏了，注释写好
   • 最后可能会分析复杂度
2. 纵观6年真题，这道题想拿分还是很容易的，不用担心颗粒无收
   • 如果想拿高分，以科班的水平，只需要将基本的那些算法代码都背一遍就好，尤其是数组，链表，二叉树的详细操作，万变不离其宗。
   • 后面第二道的算法分析题，更侧重算法广度，不要求实现，但是要求对全书的大大小小算法的特性和执行过程都有了解
   • 想拿高分，最后还是要回归到基本算法的夯实，足矣
3. 这道题分数波动大，放在最后一个去做，如果有时间就多想，分数还可以更高，没时间就直接暴力解。

我这里简单记录一下我的思路，都是直接对着王道书标答写的：

1. 23年
   • 很简单，遍历节点，对每个节点求入度出度，并做判断
2. 22年
   • 考察数组储存的树的中序遍历
   • 判断一棵树是否为二叉搜索树（排序树），要用到递归的思想，直观来看就是L<N<R，但是你不能直接用最大值最小值来判断
   • 转换思路，二叉搜索树的中序遍历是有序的，从中序遍历的视角来看，就是当前节点大于前面子序列的最大值，而这个子序列就是左子树，我们只需要顺着中序遍历序列检查每一个节点是否都满足这种特性即可，不用管右边
   • 因此代码按照中序递归写法，LNR，其中，L和R都是递归，而N的判断中，只会和左子树最大值（val）比较，不用记录右子树最大值
3. 21年
   • 这道题看着吓人，最后发现还是邻接矩阵的度计算，和23年本质一样
4. 20年
   • 这道题牛逼，需要自己画个图，分析一下三元组距离的决定因素
   • 之后用类似于归并排序的结构写程序，每次迭代要移动的下标为数轴上最靠左的那个数的下标
   • 数据复杂度同一趟归并排序
5. 重点：19年
   • 考察链表操作，很细腻，需要链表较强的功底，明天仔细研究一下
6. 18年
   • 最小的正整数，要考虑已有的最长连续正整数串，其下一个数就是我们要的数。比如1234678，从1开始的连续的串是1234，因此5就是目标数
   • 已知这个串从1开始，那么其最大也就是n，因此直接用空间换时间，把符合范围的数都放到对应的位置
   • 最后从头开始扫一遍，要么断在中间，要么停在结尾，即目标数的位序

系统分析题

这类题难度比较高，是计组的精华所在

这道题拿满分不容易，拿大头是没问题的，但是他考的知识很多很杂，有的硬件知识如果你遗漏了，那就真是不会做，好在这些都是边边角角

1. 21年真题，侧重指令结构分析
   • 1，2，考察基本指标计算
   • 3，难度所在，带符号整数减法，以及带符号整数乘法（除法），其中乘法是最难的，致命问题是符号位怎么搞？这道题取巧了，因为恰好乘8可以用算数移位做，如果让你直接算怎么办呢？
2. 22年真题，这道题侧重CPU内部数据通路
   • 1，难点所在，现场分析标志位生成和原理，死记硬背是没用的
   • 2,3,5考察数据通路和CPU设计原理
   • 4，控制信号序列，注意写法要标准
3. 23年真题，这道题侧重指令系统
   • 1,2考察寻址方式
   • 3考察数组元素的地址计算，注意edx×4，那个4是数据元素大小，不要当成一行的元素个数，这两个很容易混淆
   • 4考察缺页中断？
   • 关于大端和小端，一般来说都是小端，你找到一个kB长的数，看看顺序就可以验证

内存+cache题

cache，会根据cache的组织结构，问你地址怎么分割

然后会考察读取过程中，cache命中，缺页中断，以及置换算法，这需要对文件系统熟悉

虚拟内存

PV操作

作为科班人，我最怕的还是这道题，做不出来就颗粒无收，而当初学读者写者问题的时候，背后的逻辑一直困扰着我。

1. 19年
   • 以哲学家问题为模板，增加了一类资源，且要有防死锁措施
   • 碗看起来是增加了限制，但是碗资源非常简单，反而不会有啥限制，能够为我所用，利用碗来限制哲学家同时进餐的上限，很妙
   • 因为碗既充当了资源，要P，也充当了防死锁机制，因此放在最外面卡着
2. 20年
   • 经典PV思想，先V后P进行同步
   • 注意点1：信号量设法，用$S_{AB}$这种设法最直观
   • 注意点2：因为进程太多，所以要简化进程写法，①使用CoBegin/CoEnd同时启动所有进程。②其中的每一条进程都用Begin/End包住，不区分名字，只需要用“操作A”，“操作B”来区分
3. 21年
   • 考察PV操作的实现原理以及相关底层知识
   • 1，互斥原理，答案浅薄，就是因为多进程共享，才要互斥，并没有具体告诉你共享不互斥会出现什么情况（脏读之类），不过点到为止，小分别计较，先浅后深最好
   • 2，这个没学过，你要自己模拟一下，防止死循环
   • 3，用户无法用特权指令
4. 22年
   • 同20年，写法略有不同，20年没有告诉你几个进程，你可以让每一个操作对应一个进程，然后用简化方法写进程
   • 22年告诉你有俩进程，并且规定了任务的归属，那就将PV穿插在每个进程的任务之间即可。同一个进程，先后顺序已经OK了，所以你只需要注意进程之间的制约即可，图可以进一步简化
5. 23年
   • 考察了swap指令：互斥的硬件实现，大胆猜测一下，明年要么深入考一下硬件，要么就换到理发师，之类的其他没考过的PV问题了

后续怎么复习呢，硬件这块得回忆一下，其次就是经典PV问题

文件系统

1. 22年
   • 这道题知识性强，不难，靠我笔记里的那点内容纯拿捏
   • 需要明确的是，虽然他用索引节点，但是题目给的那张表里面，既然有磁盘块号，那就代表图中的这几个文件都只占用一个磁盘块
   • 1，2考了文件的组织
   • 3考察文件读取流程，其实也是考文件系统整体的组织，考的是利用索引节点优化FCB后的读取流程
   • 4考察多级索引的计算
2. 21年
   • 同样是知识性，考察磁盘结构，从物理格式化，到分区，到逻辑格式化（文件系统建立），以及其引导过程，这些都是基础知识
3. 19年
   • 2，考察磁盘寻道，在这个磁盘结构中，需要移动磁头的情况就是切换柱面。因此分别求出4个簇号对应的柱面，然后走一下SSTF算法即可。
   • 3，考察磁盘逻辑地址和物理地址的转换，这个磁盘采用的是柱面，磁道，扇区的三级结构。给了簇，我自己是先乘2变成磁盘块号的，然后就是依次计算柱面，磁道，扇区即可，总之就是从粗到细地计算
4. 18年，和22年大同小异
   • 1，考察多级索引的计算，上限
   • 2，很显然文件数量的上限，既受到空间的限制，也受到索引节点空间的限制，二者取交集即可
   • 3，多级索引的读取过程，如果有多级索引，就要多读几次，数量取决于你的索引级数k，次数=1+k次

总之，文件系统这一道题不难，只需要把基础知识记住即可，没有费脑子的地方。

IO系统

1. 23年
   • 1，2，考察进程进行一次IO的全过程，参考笔记里的那个IO流程图，需要注意的是，中断服务进行到快结束的时候，其实进程就已经就绪了，只是还要等一个善后，开中断+返回
   • 3，驱动程序是用来操作硬件的，因此硬件级别的IO（读缓冲区）就是驱动操作的。需要区分步骤4并不是驱动程序，他只是拉起中断程序，在中断程序执行的过程中，才会调用驱动程序，而步骤4只是中断程序的一个入口
2. 22年
   • 文件和IO联系比较紧密，第1问有两种格式，推荐使用柱面，磁头（不是磁道），扇区三元组，每个地址字段内部要分配够位数
   • 2，访问时间=寻道+旋转+划过扇区
   • 3，终于到了IO性能计算了，考察DMA，一块大小对应一个磁盘块，访存次数=缓冲区传送的次数。这道题还问了优先级，之所以DMA优先级更高，是因为磁盘读写需要即使将数据移出缓冲区，否则就会覆盖丢失

这个考点其实一般是在选择题里，所以大题不用怎么注意，把基本过程熟悉了就好了，本来是选择题小考点，你大题出来就是送分

计网综合（重点）

这一部分一定要拿到，每年的常驻嘉宾

复习建议

总的来说，其实比较硬核的题只有两道吧，一是系统分析，二是内存+cache分析，其他的都是比较小的知识性的点，即使是算法题，我也仍然觉得其想拿分也不难，只是高分难罢了，因此仍然归属于知识性内容。

1. 做过的题都翻一遍
2. 笔记都看一遍，注重算法细节的回忆
3. 重点关注算法题，代码细节要熟稔于心
4. PV操作部分，互斥的软硬件方式都看一下，然后基本PV分析思路了解一下
5. 重点关注内存部分，会出分析题

就这么简单粗暴，不用花里胡哨的