说个可能会劝退不少人的事实软考中级软件设计师的下午题里第四题和第五、六题是大多数考生的分水岭。数据流图和数据库设计背熟套路就能拿分UML题拼的是读图细心而第四题算法题考场上经常能听到翻卷子叹气的声音。不是题目本身有多难而是很多人压根没搞懂它到底想考什么。先明确一点第四题不是让你从零设计算法它是一道C语言代码阅读与填空大题。试卷会给你一段写好的核心代码通常有少量留空再配两个问题问题1让你判断算法策略、填时间复杂度问题2让你补全几行关键代码。说白了它考的是“你认不认识这段代码是什么套路、关键逻辑能不能看懂”而不是“你能不能写出一个算法”。今天这篇就把第四题的复习思路、识别算法的方法、代码填空的套路、以及考场上的踩分顺序一次性说清楚。目标很简单让你下次模考拿到第四题第一遍读题就知道大概填什么而不是从头空到尾。1. 第四题到底在考什么别把算法题当成算法题上午的选择题里算法考的是概念和性质排序复杂度、查找方式、图遍历顺序你背清楚就能拿分。下午的第四题完全不一样它考的是“基于某个算法策略的实现级理解”。整道题15分常见构成是问题1给两到三个空算法策略、时间复杂度大概4到5分问题2给四到六个代码空大概10到11分。有些年份会在问题1里多问一句“该算法能否获得全局最优解”“为什么采用贪心而不是动态规划”这类说理题分值不大但很能拉开差距。这道题在下午卷里的顺序是固定的第1题数据流图、第2题数据库设计、第3题UML建模、第4题算法、第5题C设计模式、第6题Java设计模式5和6任选其一。第四题卡在中间战略地位很微妙你要是在这题上耗太久后面的设计模式代码题很容易时间不够但你要是直接瞎蒙15分搭进去上午题做得再好也悬。从历年真题的出题风格来看第四题考察的算法策略非常集中动态规划出现的频率最高贪心法紧随其后分治法偶尔来一次回溯法隔几年露个面。至于你看网上很多人提到的KMP、Prim、Dijkstra、冒泡排序这些词放心它们几乎不会以裸算法的形式出现在第四题里。第四题的核心不是某个具体算法本身而是“分治、贪心、动态规划、回溯”这四大设计策略的代码形态。掌握了这个定位复习方向就清晰了。还有一个很多人忽略的点第四题使用的语言一定是C语言不会用C或Java。C的cin、cout、vector基本不出现Java更是完全不沾边。你得习惯C的写法数组就是int a[]函数参数里带指针和取地址符结构体定义得老老实实写。这块儿对平时写Java和Python的人来说最痛苦不是算法不会是C语言语法看着别扭。2. 先学会在第一遍读题时认出算法策略算法策略的识别是整道题的基石。你问题1填不出算法策略问题2的代码填空基本也是连蒙带猜。反过来一旦你认出这是动态规划代码里哪里该填状态转移、哪里该填边界条件心里会非常有数。我建议你用下面这套特征去认比死记“动态规划的定义是啥”管用得多。2.1 动态规划看到二维数组和双重循环先别慌动态规划类题目在第四题里最好认。代码里几乎必然出现一个二维数组名字一般是dp、c、f、cost这类然后主体是一个两层for循环循环体里藏着一个if-else结构核心就在这个if-else里。这是标准的“状态表填充”结构。举个例子历年真题考过的最长公共子序列LCS就是典型代表。它的核心代码长这样for (i 1; i m; i) { for (j 1; j n; j) { if (X[i-1] Y[j-1]) c[i][j] c[i-1][j-1] 1; else c[i][j] max(c[i-1][j], c[i][j-1]); } }你看到循环里有一个max或者min的调用或者有一个从上一行/上一列推导过来的赋值公式基本可以锁定动态规划。另外动态规划的代码通常不短但结构非常规整循环边界都是1到m、1到n这种因为要留着c[0][j]和c[i][0]做边界。识别动态规划还有一个辅助信号题目文字里会出现“最优解”“最大/最小价值”“最长的子序列”这类字眼配合二维表结构。2.2 贪心法一重循环加排序代码简短得像在写作文贪心法的代码形态跟动态规划是反着的。动态规划是“长、规整、双循环”贪心往往是“短、直接、一重循环”。很多贪心题还会在代码开头调用一个排序函数或者用结构体数组存数据然后按某个关键字排好序再进入主逻辑。比如活动安排问题的骨架sort(act, act n, cmp); // 按结束时间从小到大排序 count 1; lastEnd act[0].end; for (i 1; i n; i) { if (act[i].start lastEnd) { count; lastEnd act[i].end; } }识别贪心的关键信号有几个先排序再处理、只有一个计数器或累加器、循环体里的逻辑非常简单一个if就完事、不涉及二维数组状态表。真题里如果有“每次选择当前看起来最优的”“尽可能多的活动”“每步都做局部最优选择”这种描述那绝对是贪心。2.3 分治法递归调用自己两次中间夹着一个合并逻辑分治法在第四题里出现的形态非常固定一个递归函数在函数体中间某个位置对左右两半分别调用一次然后再写几行代码把两边结果合并起来。最容易认的信号就是函数体内有两次对自身的递归调用参数通常是low和mid、left和right这种对半分的形式。void solve(int a[], int low, int high) { if (low high) { // 递归出口 return; } int mid (low high) / 2; solve(a, low, mid); solve(a, mid 1, high); // 合并左右两半的结果 }分治的题目代码空位非常容易出在三个位置递归出口的条件、mid的计算、以及合并那段逻辑。归并排序、求最大值最小值、最近点对这类都会套这个模板。你一旦看到递归和二分下标就往分治法上靠。2.4 回溯法递归套循环前后各有一个“恢复现场”回溯法一旦出现就是全场辨识度最高的。它一定有一个递归函数函数体里是一个for循环循环里做三件事设置状态、递归调用、撤销状态。那个“撤销状态”的代码最显眼通常是把一个标记数组重新置0或者把某个变量减回去。void backtrack(int t) { if (t n) { record(); return; } for (i 1; i n; i) { if (!used[i]) { used[i] 1; x[t] i; backtrack(t 1); used[i] 0; // 这就是恢复现场 } } }N皇后、全排列、图的m着色是回溯法最常考的载体。你可以把“带标记数组的递归循环”当成回溯法的指纹看到这个指纹直接锁定。我把四种策略的识别对照表放在这里考前建议反复看几遍算法策略代码特征典型载体最容易出现的填空位置动态规划二维状态数组 双重循环 if-else状态转移最长公共子序列、0-1背包状态转移方程、边界初始化贪心法一重循环 排序 简单计数器活动安排、部分背包、哈夫曼排序参数、贪心选择条件分治法递归函数 左右两半递归调用 合并逻辑归并排序、最大最小值递归出口、mid计算、合并逻辑回溯法递归 for循环 标记数组 恢复现场N皇后、全排列、图着色剪枝条件、恢复现场语句提示时间复杂度的填空也能从策略反推。动态规划通常是O(n²)贪心通常是O(nlogn)排序O(n)主循环分治常见的是O(nlogn)回溯最坏是指数级O(2^n)或O(n!)。记不住精确复杂度没关系先记住这个粗粒度范围再结合代码里的循环层数去修正。3. 代码填空的通用套路把C代码当“逻辑填空”来做识别完算法策略接下来要面对4到6个代码空。很多考生的问题在于明明看懂了题目说的是什么但就是不知道空里该填什么。这里我有一套自己考场验证过的做题顺序分享给你。第一步先通读全代码不要一上来就盯空。别人给了你一百多行C代码你直接填空等于盲人摸象。先把函数名、参数、全局变量扫一遍尤其是注释真题代码里经常有“/* 求最大连续子序列和 */”这种提示性注释白给的信息不要浪费。第二步把代码里所有已经写好的语句当成“参考答案”。这一点是很多人不知道的。第四题的代码填空答案风格高度统一如果代码里大括号的换行风格是KR你填空时就不要另起一行写花括号如果代码里用的是数组下标i从1开始你填空时也乖乖从1开始。阅卷看的是逻辑等价不是逐字符匹配但你的代码风格贴近原代码在心理上就能少一些不确定性。第三步把每个空按“位置类型”去猜功能。根据我对历年真题的拆解第四题的填空位置基本逃不出下面五类递归出口的边界条件这种空最常见前面是if开头后面是一个return语句。你看参数是low和high就填low high看是n就填n 0或n 1。循环边界条件常见的是i n、i n、i m、j n这种。判断依据是数组下标从0开始还是从1开始以及循环里有没有访问a[i1]这种越界风险。状态转移或核心计算公式动态规划里的c[i][j] ... 、贪心里的交换判断、分治里的合并比较这类空分值最高也是最需要结合上下文的。我的建议是先把等号左边是什么变量看清楚再看等号右边有哪些变量是可用的结合题目文字描述去凑公式。参数传递C语言里函数调用涉及指针和取地址。题目里如果出现了函数声明中带int *max调用处填空就大概率是max。赋值语句或标记操作回溯法里的used[i] 0以及很多算法里的return count、lastEnd act[i].end都属于这种。第四步等价变形不要慌。阅卷老师在判代码填空时看的是逻辑正确性不是和你背的答案一字不差。比如活动安排里那个贪心选择条件你写if (act[i].start lastEnd)可以写if (act[i].start act[pre].end)也可以只要逻辑对就能拿分。这跟上午题那种必须选A还是B的感觉完全不同你在填的时候可以大胆写自己觉得合理的等价写法。这里我展开说一个常见误区很多人以为代码填空必须填得跟标准答案一模一样的变量名。其实不是。真题里有个经典场景动态规划的循环变量用i和j你填空时写成p和q只要前后一致、循环逻辑正确分数照样拿。真正要命的反而是那些“运行结果对不上”的错位答案比如数组下标错了一位或者把条件判断写反了。所以填完以后一定要在脑子里虚拟跑一遍把前几行数据代进去看看结果合不合理。第五步检查边界。这是很多代码填空题的隐藏坑。代码填空不是让你把主体逻辑写完就完事边界往往决定了空的答案。动态规划要检查c[0][j]和c[i][0]有没有初始化贪心要检查排序后第一个元素是否正确处理回溯要检查递归出口后有没有漏掉记录结果。考场时间紧这一步至少留出两分钟值得。4. 踩分顺序与时间管理第四题的15分怎么拿最划算在下午题里第四题不是“最难的题”而是“最应该控制时间的题”。它不像数据流图那样背熟模板就能拿满分也不像前两题那么按部就班。很多人栽在第四题上不是因为不会做而是因为死磕导致后面设计模式没时间写。这里说说我的时间策略。下午题一共150分钟六道题选做五道每道题平均30分钟。我的建议是第四题最多给25分钟最好控制在22分钟左右。如果25分钟过去了两三个空还写不出来果断先跳到第五题设计模式把设计模式的代码题搞定再回头补。设计模式题考的其实是UML类图和代码填空的融合版只要把工厂、单例、观察者这些常见模式的C或Java版本背清楚拿分比第四题更容易。做题顺序上我更推荐“先做1、2、3再做4最后做5/6”的常规路线但如果你对C语言特别熟把第四题提前到第二位也行。重点是不要在第四题上恋战。你写完数据流图和数据库设计脑子比较清醒这个时候做第四题状态最好后面设计模式代码题需要的记忆量大放到最后反而提神。这个顺序我是实际考过验证过的体感不错。踩分的优先级非常明确第一优先级问题1的算法策略和时空复杂度。这几乎是整张下午卷里最好拿的几分之一。你就算完全读不懂代码光靠我上面说的那些特征去猜命中率都很高。见到双重循环加二维数组就写“动态规划法”见到递归两半就写“分治法”见到排序加单循环就写“贪心法”见到递归套循环加标记数组就写“回溯法”。时间复杂度的空也一起填上这个分不能丢。第二优先级问题2里那些“一眼就能填”的空。递归出口、循环边界、简单赋值这三类空的分值加起来往往有四五分而且真的不难。你只要把代码从头到尾看一遍很多空是能凭上下文补出来的压根不需要理解整个算法。第三优先级状态转移、贪心选择条件这类核心逻辑空。这些空需要你真正理解算法分值也重属于拉开差距的部分。能填出来当然好填不出来就按我前面说的“把能看懂的填了”猜也有三分之一的概率蒙对方向。第四优先级问题1里的说理题“该算法能否得到全局最优解”。这类题其实也好答贪心一般答“不能保证全局最优但可以得到可行解或问题在该策略下的最优解”动态规划和分治一般答“可以保证全局最优”回溯法暴力搜索也能保证。你只要算法策略认对了这类送分题别留空。我见过不少考生在第四题上花40分钟就为了抠出最后一个填空的4分结果第五题设计模式15分只拿了一半。这账怎么算都不划算。下午题45分就及格第四题拿个8到10分完全不影响证书但从第10分压到14分付出的代价可能比从0分考到10分还大。5. 常考算法模板速背四个策略各留一个“肌肉记忆”第四题的代码填空说白了就是让你在别人搭好的框架里补关键几笔。那你不妨提前把每个策略的“骨架”背下来上了考场直接在脑海里做匹配。这里我把四个最常出现的模板整理一遍每个都配“背诵要诀”和“容易出空的位置”你可以直接拿去用。5.1 动态规划模板最长公共子序列int LCS(char X[], char Y[], int m, int n) { int c[m1][n1]; for (i 1; i m; i) c[i][0] 0; for (j 1; j n; j) c[0][j] 0; for (i 1; i m; i) for (j 1; j n; j) if (X[i-1] Y[j-1]) c[i][j] c[i-1][j-1] 1; else c[i][j] max(c[i-1][j], c[i][j-1]); return c[m][n]; }出空位置边界初始化那两行、if的等值判断、状态转移公式。背的时候重点记住“下标从1开始存判断时用i-1和j-1”这个细节这是最容易填错也最容易出题的地方。真题考过几次动态规划几乎都是这类带二维状态表的变体比如0-1背包、矩阵连乘本质换汤不换药。5.2 贪心模板活动安排int greedy(Activity act[], int n) { sort(act, act n, cmp); int count 1; int lastEnd act[0].end; for (i 1; i n; i) { if (act[i].start lastEnd) { count; lastEnd act[i].end; } } return count; }出空位置排序函数cmp的返回值、贪心选择的if条件、lastEnd的更新。贪心的代码形态很灵活但核心永远是“在当前状态下选一个最优的然后更新状态”。你只要认准那个if条件填空基本就能拿下一半。5.3 分治模板求最大/最小值void solve(int a[], int low, int high, int *max, int *min) { if (low high) { *max a[low]; *min a[low]; return; } if (high - low 1) { // 两个元素直接比大小 } int mid (low high) / 2; int max1, min1, max2, min2; solve(a, low, mid, max1, min1); solve(a, mid 1, high, max2, min2); *max (max1 max2) ? max1 : max2; *min (min1 min2) ? min1 : min2; }出空位置递归出口条件、两次递归调用、合并部分的比较赋值。分治法考的就是“分”和“合”两个字代码里递归那段基本不会给你挖太多坑合并那几行才是重点。5.4 回溯模板全排列void backtrack(int t) { if (t n) { recordSolution(); return; } for (i 1; i n; i) { if (!used[i]) { x[t] i; used[i] 1; backtrack(t 1); used[i] 0; } } }出空位置递归出口的t n判断、used[i] 1的标记、backtrack(t1)的递归参数、恢复现场那行used[i] 0。回溯法的代码填空特别喜欢把“恢复现场”那一行挖掉因为这是回溯法区别于普通递归的关键。你只要记得“递归前标记、递归后恢复”这句口诀这个空就拿下了。这四套模板不用死记硬背你要做的是每天动手在草稿纸上各写一遍坚持一周肌肉记忆自然形成。到考场上看到题目代码你的脑子里会自动把这些模板和试卷代码做比对哪儿缺了、哪儿被改了一眼就能看出来。6. 常见问题与避坑实录考场上最容易丢分的几个点整理一下我在刷真题、带人复习过程中反复遇到的坑基本都是真实考场里的失分点。6.1 数组下标从0还是从1开始这是第四题最大的暗坑。动态规划题特别喜欢让c[i][0]和c[0][j]做边界循环从1开始而分治和贪心的代码里数组经常从0开始循环边界就写成i n而不是i n。填循环边界前一定先确认题目代码里有没有预留第0行第0列有没有a[0]和a[n-1]的使用痕迹。填错一位整道题的逻辑全乱。6.2 “时间复杂度”别只看代码循环层数还要看递归。很多考生看到两层循环就写O(n²)但代码前面如果递归调用了自己两次复杂度其实是对数或线性对数的。贪心题如果先排序复杂度里至少要带上O(nlogn)不能只写循环的O(n)。实在不会算按我当时的方法写“最坏情况不超过O(n²)”这种保守答案也能捞到半分。6.3 问题1让填“算法策略”时写完整名称。别写“DP”“贪心”“动态”这种缩写阅卷老师不想猜。标准写法是“动态规划法”“贪心法”“分治法”“回溯法”这四个词一定要背准确字不能写错。就这4分每年都有考生因为写成“动态规则”被扣掉太冤了。6.4 代码填空如果实在不会也要尽量填别留空。阅卷是按空给分的你填了且逻辑沾边有概率得分留空则铁定没分。我的建议是实在不会的空先填一个跟变量名最搭的表达式。空左边是“x[t] ”你就填i或某个循环变量空右边是个比较符号你就试着填两个数组元素之间的比较。这不是教你瞎蒙而是告诉你第四题的空白处永远有上下文线索利用上下文去猜猜中概率不低。6.5 别把C语言的语法细节搞混。软考下午题用的C是经典的老式C89风格代码里经常出现int *max这样的指针形参变量声明放在函数开头。你填空的时候别写C的引用运算符也别在for循环里用C99风格的int i 0初始化除非原代码就是这么写的。尽量模仿原代码风格这是最稳妥的。6.6 注意递归结束条件的“等号”。递归出口是low high还是low high这两种写法逻辑上有时等价但阅卷时更认可和原代码对称的写法。我看很多复习资料里会把递归出口写得很“严谨”比如low high真到考场上反而容易跟答案的low high差半拍。你就记住出题人出空的时候通常挖的是那个跟递归参数直接相关的简单判断别想复杂了。6.7 审题别漏掉题目文字描述。第四题大段代码前面通常有两到三行文字介绍问题背景、输入输出格式。很多人直接跳过文字去看代码这是大忌。背景文字里会有“求……的个数”“每个物品的重量”“要求时间复杂度不超过O(n²)”这些关键信息它们直接决定了算法策略的答案。尤其是“要求时间复杂度”这句话几乎是暗示你选哪种策略的信号灯。7. 复试冲刺阶段的第四题复习法如果你的复习时间只剩两到三周第四题的投入产出比其实非常高因为你只需要做透一件事刷近八年的真题第四题每道题做三遍。第一遍摸底。找一套最近的真题第四题严格按照“25分钟”的时间限制做一遍做完对答案看看自己卡在哪个环节。是认不出策略还是看不出代码结构还是C语言语法不熟这一步决定了你后面复习的重点。第二遍拆解。把做过的每道题按“算法策略代码结构填空位置答案句式”四个维度整理出来。你会惊讶地发现真题的第四题重复率非常高动态规划的代码框架翻来覆去就那么几个样子贪心的题目甚至连变量名都很相似。整理完一遍你已经对出题人的套路了然于胸。第三遍默写。合上答案把每道题的核心代码从头到尾手写一遍。不是抄是默写。默写完再和原代码对比看哪儿漏了、哪儿写反了。这个过程最痛苦但提升也最明显。我当年考软考前两周每天晚饭后默写一遍最长公共子序列和活动安排到考场上看到第四题代码简直像看到老熟人。还有一个小技巧就是把每道真题的问题1那道“算法策略时间复杂度”挖出来做个表格只填年份不填答案每天扫一遍逼自己看到年份就说出策略和复杂度。这4分基本就是白送的你要确保逢题必对。至于教材官方教程和历年真题解析就足够了不需要额外买一堆“算法大全”。第四题不是考你算法广度它考的是你对四种策略的代码实现理解。把有限的题做精比做一百道泛泛的练习题有用得多。我个人在备考时的体感是第四题真的是下午题里“稳定性”最高的一道题。数据流图和数据库设计你偶尔还会碰到没见过的变体UML题有时候会纠结关系和箭头的画法但第四题只要吃透四种策略的代码模板每次看到都是同一个味道。它就像考试大纲给你划好范围后出题人认认真真在范围内出题不做任何超纲的“炫技”。所以耐心把这四种模板吃透这套题就是你的稳定分数来源。