我还在读本科的时候期末复习最怕的不是背概念而是那种看起来每个字都懂、合上书却一道题都算不出来的感觉。后来我做了一件事把所有课程里需要动手计算、需要推演的题目单独抽出来按课程和题型整理成一份《计科-软工13-计算实例「整理」》。这份资料名字挂的是13级但它的整理思路和题型框架对所有计科、软工专业的在校生都通用。这篇内容不是把当年的标准答案重新贴一遍而是聊聊我当年是怎么把这些计算实例系统整理出来的以及整理过程中踩过的坑和摸索出的方法。如果你正在准备期末考试、考研专业课或者只是觉得“听懂了但不会做题”下面这套整理思路可以直接参考。它会告诉你哪些计算题值得整理、用什么模板管理题目、每章高频实例怎么拆解以及整理完之后怎么让这份资料真正帮你提分。1. 为什么计科和软工的课本里永远绕不开“计算实例”1.1 不是所有课程都靠背计算题才是区分度所在计算机科学与技术、软件工程这两个专业课程体系里其实藏着一条很清晰的分界线一类课以概念和机制为主比如组成原理里的寄存器作用、软件工程里的过程模型这些内容靠理解和记忆就能应付另一类课则几乎每章都有一道标志性的计算题数据结构里的哈希表平均查找长度、操作系统里的页面置换缺页率、计算机网络里的子网划分、数据库里的范式判断和模式分解、编译原理里的FIRST与FOLLOW集合全都在这个范畴里。这类题的共同特点是不需要你大段默写文字但必须在考场上快速、准确地完成推演。也恰恰是这类题把“听懂了”和“考得好”彻底分开。上课听懂原理只是第一步真到考试时你会发现自己要么漏掉一个冲突处理步骤要么把一个判断条件用反。我当年第一次做页面置换题LRU和FIFO的逻辑都懂但一画内存变化图就乱最后只能对着答案反推哪里错。后来想明白了不是我不懂概念而是缺少把概念落到纸面上的训练这个训练就是大量过计算实例。1.2 “整理”不是抄题而是构建解题模型很多人整理习题方式就是把教材例题原封不动抄一遍抄完合上本子脑子里留下的东西还是原来的那些。这种整理几乎没有价值因为抄写没有调用任何“理解”层面的思考。我后来把整理的定义改成了“把每一道题变成解题模型的一个样本”。什么意思呢比如你整理十道哈希表题目不应该只收获十个孤立答案而应该从中提炼出一组固定动作先确认散列函数是什么再确认冲突处理方法是线性探测还是链地址法然后按顺序构造散列表最后套用平均查找长度公式。这组动作就是这一题型的解题模型。整理的价值不在于拥有一个厚厚的习题集而在于你被迫从大量题目中看出它们的共性并且用自己的话把步骤重写了一遍。重写的过程里所有“以为自己会但一写就卡壳”的地方都会暴露出来这才是真正的收获。2. 计算实例的梳理框架按课程主线把题目归类2.1 数据结构与算法以“复杂度”和“查找/排序”为两条主线数据结构是我当年整理计算实例的第一站也是题型最多的一门课。如果只凭感觉乱收题很容易变成流水账。我后来定了一个框架按两条主线走一条叫“复杂度计算”一条叫“查找与排序”。复杂度计算重点关注两类一类是循环嵌套的复杂度推导另一类是递归算法的时间复杂度例如用展开法或主定理分析递归方程。这类题看似简单实际上非常容易在“忽略常数项”或“误把整体规模当子问题规模”上翻车。查找与排序则是大题重灾区。查找部分要整理折半查找的判定树与ASL、二叉排序树的构造与ASL、哈希表的构造与成功和不成功ASL排序部分要整理直接插入、希尔、冒泡、快速、堆排序、归并排序的趟数、比较次数、移动次数和稳定性。图算法里能出计算题的主要是Prim、Kruskal最小生成树Dijkstra、Floyd最短路径以及拓扑排序的序列生成。整理的时候不要只写结果每一步选边的依据、每一轮dist数组的更新都要留痕我自己复习时发现这些过程性记录比答案本身有用得多。2.2 操作系统围绕“调度-内存-文件”三维度展开操作系统的计算题非常集中整理时可以按“处理机调度、内存管理、磁盘调度”三个维度搭框架。处理机调度里FCFS、SJF、时间片轮转是必考计算周转时间和带权周转时间时特别要注意新任务到达时刻与当前任务完成时刻的先后顺序稍不留神就会把一个任务多算一个等待时间。内存管理主要整理页面置换算法、有效访问时间计算、页表与地址转换。页面置换题要亲手画内存变化表OPT、FIFO、LRU、Clock各画一遍你会发现FIFO和LRU在某些访问序列下缺页次数完全相同这时候就该把序列特征记到易错点里。磁盘调度则要比较先来先服务、最短寻道优先、电梯算法在给定磁道序列下的寻道长度这类题计算量小但非常考验细心程度。银行家算法和信号量PV操作也建议整理特别是银行家算法必须把“找安全序列”的每一步写在纸上不能只凭眼睛判断。2.3 计算机网络与数据库优先整理“会考流程”的实例计算机网络和数据库有一个共同特点计算题的类型没有前两门那么杂但每一类都要求你对流程非常熟。计网我重点整理了两块——子网划分与TCP拥塞控制。子网划分题一旦把“块大小、网络号、广播地址、可用地址范围”这条链路走顺所有题都大同小异TCP拥塞控制则要会画拥塞窗口随时间的变化图区分慢启动、拥塞避免、快重传和快恢复四个阶段题目中给出的门限值变化要严格按流程使用。数据库整理的主线很明确关系代数表达式求值、候选码求解、范式判断与模式分解、事务并发调度的冲突可串行化判断。其中范式判断和分解题我强烈建议在草稿纸上把函数依赖链画出来A→B、B→C这种传递依赖用箭头串起来看比直接对着属性列表肉眼看要清晰得多。事务调度部分要理解冲突操作的定义再按“交换非冲突操作能否得到串行调度”的思路判断整理时把判断过程完整写下来不要只标一个“是”或“否”。2.4 编译原理与软件工程容易被忽视但绝不能省略编译原理和软件工程的计算题在考试里占的比例不如前几门大但一旦考到没整理过的人基本只能蒙。编译原理里从NFA到DFA的子集构造法、FIRST与FOLLOW集合计算、LL(1)预测分析表构造、LR(0)与SLR(1)分析表构造这些都是标准计算题。它们的共同特点是步骤性强但规则多很容易在某个边界条件上出错比如求FOLLOW集合时忘记“产生式右边后面跟着非终结符且该非终结符可推空”的情况。软件工程听着像是偏文科的课但它也有能出计算题的角落代码行数和功能点估算、关键路径法CPM中的最早开始时间与最晚开始时间计算、McCabe圈复杂度的三种等价计算方式。整理这类题时我会特意把“为什么是这个公式”标注在旁边因为这些公式不像数据结构里的算法那样直观不写清楚推导逻辑复习时很容易记混。3. 用一张统一的模板管理所有习题字段设计与标注规范3.1 为什么需要统一模板而不是每门课各弄一套格式我最早整理计算实例时每门课各用各的格式数据结构写在笔记本上操作系统记在Word里计网直接在PDF上画。问题在题量超过一百道之后彻底暴露了——想找一道曾经错过的哈希表题得先回忆它记在哪本本子、哪个章节效率低到让人崩溃。后来我统一了所有题目的模板每个实例固定包含七个字段编号、来源、题型标签、题干、我的解答、易错点、关联知识点。编号用来在索引表里定位来源标明是教材例题、历年真题还是期末模拟题方便复习时判断重要程度题干部分写精简版即可不必完整抄题我的解答必须用自己理解后的语言重写哪怕比标准答案啰嗦也没关系易错点专门记录我第一次做错的原因和这道题常见的坑关联知识点用来把散落的题目串成网络比如一道哈希表ASL题可以顺手关联到散列函数设计和冲突处理方法。这套模板看起来平淡无奇但坚持用一年之后你会发现自己对每道题的记忆都加深了很多因为每写一次“易错点”就是一次主动反思。3.2 我实际使用的标签体系模板解决的是“每道题长什么样”标签体系解决的是“这些题怎么被检索”。我给每个实例打四类标签课程标签、题型标签、难度标签、状态标签。课程标签按名称写如数据结构、操作系统题型标签按题型写如页面置换、子网划分、范式分解难度标签分基础和进阶两级进阶里再单列一类“真题错题”状态标签则持续更新区分“已掌握”“经常错”“尚未完成”。这里我有一条坚持不变的规则一道题如果这次做还是错就在题目前面加一个明显的警示符如果连续两次做对才把状态从“经常错”改成“已掌握”。这个机制能防止自我欺骗因为很多人会把“看懂了答案”误当成“自己做对了”状态标签逼你诚实面对自己。3.3 目录与索引的管理技巧整理出来的资料如果没有索引放到后期就是一堆散页和没整理没什么区别。我的做法是在整套资料最前面放一个总索引表行是课程列是题型格子里面填题目编号。比如数据结构那一行哈希表列下就填“8-1、8-2、8-3”排序列下就填“5-1、5-2”。考前复习先看索引一眼就能扫出哪类题练得多、哪类题还空着薄弱点一目了然。纸质和电子怎么选看个人习惯电子版便于全文检索和长期更新纸质版便于手写推演尤其适合编译原理和数据结构这种需要大量画图演算的科目。我自己的方案是主用电子版归档复习前把重点题打印出来在纸上重新推演一举两得。4. 五个高频计算实例的解题思路拆解4.1 哈希表的平均查找长度别被“探测次数”绕晕哈希表ASL题目在数据结构考试里的出现频率极高而且出题套路比较固定。我拿一个经典例子说清楚计算逻辑散列表表长13散列函数H(key)key mod 13采用线性探测法处理冲突关键字序列为19,14,23,01,68,20,84,27,55,11,10,79。构造过程我从头走一遍。19%136直接放入地址614%131放入地址123%1310放入地址1001%131地址1被占探测地址2为空放入地址2。到这一步前四个关键字就体现出一个关键规则线性探测用的比较次数是“哈希地址本身这一次”加上“往后空转的次数”。68%133放入地址320%137放入地址784%136地址6被19占探测地址7被20占继续探测地址8为空所以84比较了3次才放进去。后续的关键字同样按这个规则推进。27和55分别要比较4次和3次因为它们的哈希地址落在已经被占用的连续区域里79最惨哈希地址1到8全被占一路探测到地址9才落位比较了8次。把所有关键字成功插入时的比较次数加起来11121134313829再除以关键字个数12得到ASL成功为29/12约等于2.42。很多同学算到这里就停了但如果题目问ASL不成功则要对每个哈希地址0到12从该位置开始一路探测到第一个空位置记录每个地址需要的比较次数求和后除以表长13而不是除以关键字个数。这两个公式的分母完全不同是最常见的失分点。4.2 页面置换算法的缺页率亲手画一张“内存变化图”页面置换题的核心能力是画内存变化图。我先给出一个训练用例页面走向为7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1分配3个内存块用LRU算法。我的建议是不要直接在脑子里模拟而要按下面这个表格一步一步写访问步访问页面内存状态从最久未使用到最近使用是否缺页177缺页207 0缺页317 0 1缺页420 1 2缺页501 2 0命中632 0 3缺页前几步有两个很典型的细节。第4步访问2时内存块是7、0、1其中7是最久未被使用的所以淘汰7内存变成0、1、2第5步又访问00命中但要更新它的“最近使用”身份内存顺序立即变为1、2、0。这一步如果你不在表格里更新顺序第6步就很容易判断错淘汰对象。整个访问序列完整走完缺页次数是12总共访问21次缺页率12/21约等于57.1%。同样一个序列如果换成FIFO算法缺页次数会不同这就是两种算法的本质区别——LRU依据的是“最近使用时间”FIFO依据的是“进入内存时间”。整理这类题时我会要求自己在旁边补一段话用一两句话解释这次为什么淘汰那个页面防止下次凭感觉。4.3 CIDR子网划分先把“块大小”刻在脑子里子网划分题不是数学难题错的几乎都是思路问题。以192.168.1.0/24为例需要划分出5个子网其中最大子网至少容纳30台主机。很多人的第一反应是“5个子网那就借3位主机位可以得到8个子网”这个方向是对的但为什么要借3位、块大小怎么算很多人讲不清楚。正确步骤是这样先根据主机需求确定块大小。每个子网可用的主机地址数是块大小减2因为网络号和广播地址不能分配给主机。最大子网需要30台主机那么块大小至少是32因为32减2等于30。块大小必须是2的幂32正好是2的5次方所以主机位保留5位掩码从/24变成/27借了3位子网位。3位子网位能产生8个子网块满足5个子网的需求还多出3个块做扩展。块大小32意味着每个子网从块首开始到块尾结束。具体划分如下192.168.1.0/27可用地址192.168.1.1到192.168.1.30广播地址192.168.1.31192.168.1.32/27可用地址192.168.1.33到192.168.1.62广播地址192.168.1.63192.168.1.64/27可用地址192.168.1.65到192.168.1.94广播地址192.168.1.95192.168.1.96/27可用地址192.168.1.97到192.168.1.126广播地址192.168.1.127192.168.1.128/27可用地址192.168.1.129到192.168.1.158广播地址192.168.1.159剩下三个块留作备用。这个题的精髓在于先确定块大小再反推掩码。如果你一上来先算子网个数很容易忽略主机容量约束这也是考试题目里最爱埋的陷阱。4.4 关系模式的范式判断与分解从部分依赖和传递依赖入手数据库范式题看起来很绕其实判断逻辑非常固定。我常用一个典型例子关系模式R(A,B,C,D,E)函数依赖集F{AB→C, C→D, D→E}要求判断最高范式并分解到3NF。第一步求候选码。A的闭包只有AB的闭包只有B而AB的闭包可以通过AB→C得到CC→D得到DD→E得到E最终AB的闭包是{A,B,C,D,E}所以候选码是AB非主属性是C、D、E。第二步判断2NF。2NF要求所有非主属性完全函数依赖于候选码。C完全依赖AB因为A单独推不出CB单独也推不出CD和E虽然经过了依赖链但AB确实能决定它们且没有任何候选码的真子集能决定它们所以满足2NF。第三步判断3NF。3NF要求非主属性不传递依赖于候选码。这里AB→C且C→DD就是通过C传递依赖于AB的所以不满足3NF。因此这个模式最高是2NF。如果需要分解到3NF按函数依赖集拆分即可R1(A,B,C)保持AB→CR2(C,D)保持C→DR3(D,E)保持D→E。因为R1包含候选码AB同时所有依赖都有对应的关系模式承接这个分解既保持了函数依赖也满足无损连接。整理这类题时我会把判断过程拆成三步写到模板里求候选码、按2NF定义查部分依赖、按3NF定义查传递依赖。顺序不能乱乱一步整个判断就全错了。4.5 FIRST与FOLLOW集合LL(1)文法的看家本领编译原理里的FIRST/FOLLOW计算题是公认步骤多但套路固定的题型。我整理时用过一个非常经典的文法S→ABA→aA|εB→b|ε。FIRST集合相对好算。A能推导出a开头的串也能推导出空串所以FIRST(A){a,ε}。B能推导出b开头的串也能推空所以FIRST(B){b,ε}。S是AB那么FIRST(S)要先把FIRST(A)中的a放进来再把FIRST(B)中的b放进来因为A和B都能推空所以S也能推导出空串最终FIRST(S){a,b,ε}。FOLLOW集合才是真正的失分重灾区。FOLLOW(S)必然是结束符$。FOLLOW(A)要看A在产生式右部出现的位置这里A出现在S→AB中A后面跟着B。B的FIRST集合里有b所以b要加入FOLLOW(A)同时B能推导出ε这时A后面实际上可以是整个S后面能跟的东西所以FOLLOW(S)也要加入FOLLOW(A)。于是FOLLOW(A){b,$}。这个易错点我在整理时用红笔标了三遍只要A后面那个非终结符能推空就一定要并上FOLLOW(S)。FOLLOW(B)则直接等于FOLLOW(S)因为B在产生式右部末尾所以FOLLOW(B){$}。算完这些就可以判断是否是LL(1)文法。对A来说A→aA的SELECT集是FIRST(aA){a}A→ε的SELECT集是FOLLOW(A){b,$}两者交集为空对B来说B→b的SELECT集是{b}B→ε的SELECT集是FOLLOW(B){$}交集也为空。S只有一个产生式不需要比较。因此这个文法是LL(1)文法。这类题的整理价值不在于最终那个“是”字而在于把每个集合的推导过程完整保留下来考前重算一遍就能把这几分稳稳拿住。5. 整理过程中的踩坑记录与复习阶段的用法5.1 我踩过的坑抄题而不是解题、迷信标准答案、难度标记失真第一批整理的文件说实话效果很差因为我犯了一个新手通病抄题。看到教材答案就觉得自己会了于是题目摘抄得工工整整答案也誊得干干净净但合上本子换一道数字稍微变一下的题照样不会。后来我强迫自己执行一条规则整理时先把答案遮住自己在草稿纸上推一遍推完再对照答案改。那一遍自己写的步骤才是整理资料里真正值钱的部分。第二个坑是迷信标准答案。教材和习题集偶尔也会有笔误尤其是操作系统调度表和网络计算这类过程繁复的题往往中间某个值印错就会导致最终结果对不上。遇到这种情况我的建议是别急着怀疑自己重新验算一遍确实对不上就标注“此处与教材不一致以推演结果为准”不要硬着头皮把错误答案写进整理文档。第三个坑是难度标记失真。一开始我给很多题都标了“重点”结果整本资料全是重点等于没有重点。后来我只分三档基础题、进阶题、真题错题。基础题负责覆盖知识点进阶题负责提升计算熟练度真题错题则是考前冲刺只看这一类就够了。这样分层之后复习效率明显提高。5.2 整理之后怎么安排复习才能让文档真正发挥作用整理不是终点用它复习才是终点。我的复习安排分为三轮。第一轮在考试前较早就开始只翻总索引表按课程扫盲看到一道题能说出大致步骤就算过关这一轮的目的是找回记忆第二轮按题型集中突破只重做状态为“经常错”的题已经掌握的不再浪费时间第三轮在考前两三天只看每道题的“易错点”字段和页边记号这时候整套资料过一遍只需要很短时间但每道题的关键坑都还在脑子里。这样算下来整理一次可以支撑三轮复习比考前临时翻书靠谱得多。5.3 一点建议整理方法比整理成果更值得传递下去我后来把自己这套模板和标签规则发给过不少学弟学妹大家反馈说最有用的不是那些具体题目而是那个“课程—题型—编号”的框架。框架立住了任何人都能往里填新题这份资料就变成了活的东西。《计科-软工13-计算实例「整理」》能流传下来靠的也是这样一套骨架。如果你决定做一份自己的计算实例整理建议从一开始就按这个思路搭目录、统一字段、标记状态并且把每次更新的日期记在索引表里等积累到几百道题回头看你会感激自己当初这份“笨功夫”。整理这件事最值钱的从来不是文档本身而是整理过程中被迫亲手重算的每一道题。那些算过的哈希表、画过的内存变化图、写过的子网划分表会在考场上变成你下笔时的底气。希望这篇东西能帮你少走一点弯路把那些该算的、不该错的都扎扎实实算明白。
