软件设计师下午题的第四题是所有参加中级软考的同学都绕不开的算法题。每次出考场总能听到有人抱怨“算法题的代码填空又没填对”。其实这道题并没有想象中难它不要求你从零设计算法而是给出一段挖了空的C代码让你补全几个关键位置再判断算法策略、时间复杂度和空间复杂度。总共15分左右在下午总分75分里占比不小而且命题套路非常固定属于只要认真准备就能稳定拿分的一类题。这篇文章会从题型结构、策略判定、代码填空、复杂度分析、真题推演到考前训练把第四题的完整解题思路拆给你看。无论是第一次考软考的小白还是复习到第二轮的考生都可以把这篇当作一份“算法下午题行动指南”。1. 下午第四题到底考什么题型结构与命题规律1.1 题目整体面貌一段残缺代码与三个小问下午第四题在历年试卷中有几种叫法有的叫“算法设计与分析”有的叫“C语言算法题”但本质都一样。题目一般会给出一段完整的C语言程序少数时候是C程序中间挖掉4到5个空每个空用“1”“2”这种编号标注出来。在代码下方通常跟着2到4个小问。第一小问往往是“本算法采用什么设计策略”选项一般是分治法、动态规划法、贪心法、回溯法偶尔有分支限界法。第二小问是把挖掉的代码补全也就是填写那4到5个空。第三小问问时间复杂度和空间复杂度。有些年份还会加第四问比如“当输入为××时输出结果是什么”或者“如果某个条件改为××程序如何处理”。为什么这样命题因为软考是资格考试不是算法竞赛它考察的是你作为软件工程师是否具备基本的算法素养。所以它不要求你独立写出完整算法而是要求你能读懂一段经典算法的实现理解核心步骤的含义。换句话说这道题考的更多是“阅读和理解”而不是“创作”。这个定位很关键它决定了你的备考方式不是题海战术刷难题而是把经典算法的核心代码模板真正读懂、记熟。1.2 历年出题方向哪些算法频繁出现从我备考时刷过的近十年真题来看第四题虽然每年算法不同但翻来覆去就在几个经典算法里打转。分治法几乎年年考归并排序、快速排序、二分查找是常客。动态规划也特别高频0-1背包、最长公共子序列LCS、矩阵连乘、最长递增子序列这些轮流出现。贪心法同样重要活动安排、哈夫曼编码、单源最短路径Dijkstra、最小生成树Prim或Kruskal都考过。回溯法相对少一些但N皇后、图着色这类经典题也出现过。此外KMP模式匹配在部分年份也作为难题出现过。值得注意的一个趋势是题目特别喜欢考“大家一看就知道是什么算法但代码填空容易出错”的题目。比如归并排序的合并过程、动态规划填表时递推式的两个分支、贪心算法中更新最优下标的那一步——这些位置几乎是每年固定的考点。所以如果你能把“每类算法中最核心的那个递推式或赋值语句”背下来第四题的大半分数就到手了。2. 算法策略判定第一小问的辨识方法第一小问是策略判断题很像是“送分题”但实际上每年都有考生在这里栽跟头。原因不是不知道四种策略的定义而是不会从题干和代码中快速识别。2.1 从题干措辞反推算法策略先说最快的方法读题干时留意特定的行为描述。如果题干出现“每次选择当前看起来最优的解”“按结束时间排序后依次选择”“每次都从当前集合中取出最小元素”那基本就是贪心法。注意贪心的关键词是“每次”“当前”“局部最优”它没有回头路一旦选了就不再改变。如果题干出现“将问题分解为若干子问题”“子问题与原问题形式相同”“递归求解后合并结果”那基本是分治法。分治的典型行为是“先拆再合”比如归并排序先拆成两半分别排序最后归并。如果题干出现“子问题之间存在重叠”“用一个表记录已经算过的子问题结果”“自底向上填表”那就是动态规划。这三个信号里“填表”是最强的信号只要看到二维表格、dp数组、递推式基本可以锁定动态规划。如果题干出现“尝试每一种可能”“如果不满足约束则回退”“恢复现场”那是回溯法。回溯的代码里通常会有一个递归函数伴随一个标记数组或swap操作在递归返回后恢复状态。这四种策略的区分我在初期备考时也总混淆。后来我总结成一句口诀分治看合并动态规划看表格贪心看排序加局部最优回溯看递归加恢复现场。你可以把这句话记在笔记里考场上很有用。而且策略判断不是孤立的它要和后面的代码填空互相验证。我实战中习惯先不看代码只读题目描述就先把策略选项写下来再去代码里验证。如果代码框架和我的判断一致那第二问填代码时就有了信心如果不一致就要回头重新理解题目通常是题目有“求最优解”这样的字眼但我忽略了或者我把贪心和动态规划的典型特征搞混了。2.2 经典算法的“代码指纹”对照表除了从题目描述判断更可靠的判断依据其实是代码本身的“指纹”。不同算法在代码结构上有非常明显的特点即使不看题干只看代码框架也能猜个八九不离十。下面这张表是我复习时自己整理的照着背就行典型算法算法策略代码关键特征归并排序分治法递归函数加merge合并过程快速排序分治法partition分区加递归交换二分查找分治/减治while(lowhigh)与mid计算0-1背包动态规划二维dp表max(dp[i-1][j], dp[i-1][j-w[i]]v[i])最长公共子序列动态规划二维dp表相等加1不等取max矩阵连乘动态规划三重循环k遍历划分点活动安排贪心法按结束时间排序if(s[i]f[j])更新哈夫曼编码贪心法每次取最小节点合并Dijkstra/Prim贪心法每次选距离或权值最小的顶点N皇后回溯法递归加冲突判断加回溯恢复看到这张表你应该能感觉到策略判断其实是最容易的一问因为代码特征太明显了。如果你第一小问还在犹豫那说明你对经典算法的实现不够熟建议先回到代码本身把每个算法的核心结构过一遍。3. 代码填空核心得分点的拆解与训练这是第四题的大头4到5个空每个空2到3分加起来8到12分。很多考生在策略判断题和复杂度题上都能拿到分但代码填空一错错一串非常可惜。3.1 通用读题顺序与填空中思维路径我自己总结了一个“四步读题法”每次做第四题都严格按这个顺序来第一步先读题干的问题描述明确题目要算什么。是求最大价值还是求最长序列还是求最多活动数量这个问题决定了整个算法的目标也决定了你后续填的每句代码“为了什么而存在”。第二步看main函数和输出语句确认输入输出格式。这一步能帮你理解变量含义。比如题目里定义了数组s[]和f[]main里调用了一个函数再printf结果那你就知道这个函数的核心功能是什么。第三步回到被挖空的算法函数先从头到尾通读一遍不看空位只看能读懂的代码。很多考生拿到题就盯着空看结果越看越懵。正确做法是先建立整体印象这个函数参数有哪些、循环结构是什么样的、返回什么值。第四步逐个填空时问自己三个问题这个空所在的语句在做什么这个空前后的变量分别是什么含义这个函数最终要返回什么答案基本就藏在三个问题的交叉点上。这里我想特别强调一个细节填空时不要只想着“语法上填什么”而是要想“逻辑上这一句必须完成什么功能”。比如空的前面是“if (s[i] f[j])”那么这一整个if块做的决定是“当前活动能不能选”空里通常是count或者ji这种更新操作。顺着逻辑链条很难填错。3.2 案例一活动安排问题贪心法为了让思路更清楚我拿活动安排问题举一个完整例子。题目大家应该很熟有n个活动每个活动有开始时间s[i]和结束时间f[i]要选出尽可能多的互不重叠的活动。如果要使用贪心法通常先按结束时间从小到大排序然后依次判断每个活动是否和上一个已选活动冲突。核心代码模板如下int greedyActivity(int s[], int f[], int n) { int count 1; // 第一个活动必选 int j 0; // 记录上一个被选中的活动下标 for (int i 1; i n; i) { if (s[i] f[j]) { // 当前活动与上一个被选活动不冲突 count; j i; // 更新“上一个选中活动” } } return count; }如果题目把两个空分别挖在if条件和ji处那么空1要填“s[i] f[j]”因为活动不冲突的条件是当前活动的开始时间不早于上一个已选活动的结束时间。空2要填“j i”因为选中当前活动后要把“上一个选中活动”替换成当前活动。这里有个容易错的地方有的考生会把空1填成“s[i] f[j]”这个等号加不加语义就完全变了。如果允许两个活动前后紧挨着开始也就是上一个活动刚结束、下一个马上开始就必须用如果题目要求严格不重叠才是。审查题干的措辞非常关键。还有一个高频考点如果题目不是求数量而是要求输出“选择了哪几个活动”那么代码里通常还要维护一个数组selected[]此时空的答案可能变成“selected[count] i”或者记录下标的相关语句。你要根据题目给的是“求数量”还是“求方案”来判断。3.3 案例二最长公共子序列动态规划动态规划的代码填空比贪心稍微复杂一点因为要理解递推式。我用最长公共子序列LCS举例。两个字符串X和Y长度分别为m和n。dp[i][j]表示“X的前i个字符”和“Y的前j个字符”的最长公共子序列长度。递推式分两种情况如果X[i] Y[j]说明当前字符可以参与匹配长度由dp[i-1][j-1]加1得到否则只能从dp[i-1][j]和dp[i][j-1]中选较大的。对应的C代码模板如下int lcsLength(char X[], char Y[], int m, int n) { int dp[MAX][MAX]; for (int i 0; i m; i) dp[i][0] 0; for (int j 0; j n; j) dp[0][j] 0; for (int i 1; i m; i) { for (int j 1; j n; j) { if (X[i - 1] Y[j - 1]) dp[i][j] dp[i - 1][j - 1] 1; else dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } return dp[m][n]; }如果挖掉两个空一个在初始化部分一个在递推部分初始化空填“dp[i][0] 0”或“dp[0][j] 0”含义是当其中一个字符串长度为0时公共子序列长度必定为0。递推空根据分支判断。题干通常已经给出递推式你只要照搬递推式即可注意数组下标。动态规划这块最大的坑是下标基准。这里我用了X[i-1]来比较是因为数组下标从0开始如果题目变量从1开始存字符那比较条件就是X[i] Y[j]。做题时一定要先观察题目代码的起始下标不要想当然。另外软考很少要求你写出整个递推式而是把递推式拆成填空所以只要你理解了这个dp表的填表过程基本不会卡壳。建议练习时把LCS和0-1背包的填表过程亲自模拟几遍比如拿两个短字符串手动填一遍表感受一下每个格子的值是怎么来的考场上看代码就不会晕。4. 复杂度分析笔试中最容易白送的分数复杂度分析这一问通常紧跟代码填空分值3到6分。很多考生觉得复杂但其实软考第四题考查的复杂度非常基础通常只要求写出量级不要求精确的系数和常数。4.1 时间复杂度看循环更要看递推如果代码主体是循环结构时间复杂度可以大致数循环层数和每层循环规模。两层for循环遍历n乘m的表格那就是O(n*m)单层for循环遍历n个元素那就是O(n)while循环每次规模减半那就是O(log n)。如果代码主体是递归结构可以用递推式分析。比如归并排序每次把规模为n的问题拆成两个n/2的子问题再合并需要O(n)所以递推式是T(n)2T(n/2)O(n)解出来是O(n log n)。这类经典结论我建议直接记归并排序、快速排序平均、堆排序都是O(n log n)二分查找和二叉树搜索是O(log n)动态规划中背包问题O(nC)、LCS是O(mn)、矩阵连乘是O(n^3)。特别要提醒的是贪心法的复杂度容易漏算。很多贪心算法能正常运行的前提是先排序比如活动安排要先按结束时间排序哈夫曼编码要维护最小堆。如果题目没有“已排序”这个前提那么复杂度要把排序的O(n log n)加上。历年真题里这个问题出现过不止一次题干里有一句“已经按××排序”或“未排序”决定了你答案差一个log级别。4.2 空间复杂度数清楚辅助空间空间复杂度相对简单就看额外开辟了多少存储空间不包括输入数据本身占用的空间。动态规划的二维表dp[m][n]是O(m*n)一维滚动数组是O(n)。归并排序在合并时需要临时数组空间复杂度是O(n)这点很容易被忽略。快速排序虽然没有显式的辅助大数组但递归调用栈的深度平均是O(log n)最坏是O(n)。如果你在填空题里看到一个和原数组等长的临时数组那空间复杂度多半就要加一个O(n)。我复习时总结了一套速查表可以直接背算法时间复杂度空间复杂度归并排序O(n log n)O(n)快速排序平均O(n log n)最坏O(n^2)平均O(log n)最坏O(n)二分查找O(log n)O(1)0-1背包二维dpO(n*C)O(n*C)最长公共子序列O(m*n)O(m*n)活动安排已排序O(n)O(1)活动安排含排序O(n log n)O(1)DijkstraO(n^2)O(n)N皇后指数级如O(n!)O(n)考试时如果拿不准某个算法复杂度可以现场数循环或用递推式推一遍但考场上时间宝贵我更推荐把这张表背熟。这也是为什么我说复杂度是“白送”的分数——结论是固定的只要你记住了这几小问就是送分。还有一个小经验软考真题有时会把时间复杂度和空间复杂度合并在一问里并给出“时间复杂度为1空间复杂度为2”的格式。遇到这种题目按速查表填即可。唯一要注意的是如果题目问的是“最坏情况时间复杂度”要把快速排序写成O(n^2)不要写成平均情况。看清“平均”和“最坏”两个字这个细节很多人栽过。5. 真题实战演练一道0-1背包题的完整推演理论讲了那么多不如完整走一遍做题流程。下面这道模拟题命题风格贴近历年真题我按考试状态一步步拆给你看。5.1 题目与代码框架问题描述给定n件物品物品i的重量为w[i]价值为v[i]背包容量为C要求选择若干物品装入背包使得装入背包中物品的总重量不超过C且总价值最大。已知该问题可用动态规划求解dp[i][j]表示前i件物品在容量为j的背包中能获得的最大价值。递推关系为若 j w[i]则dp[i][j] dp[i-1][j]否则 dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])题目给出如下C代码其中有4个空int knapsack(int w[], int v[], int n, int C) { int dp[MAX][MAX]; for (int i 0; i n; i) dp[i][0] (1); for (int j 0; j C; j) dp[0][j] (1); for (int i 1; i n; i) { for (int j 1; j C; j) { if (j w[i]) dp[i][j] (2); else dp[i][j] (3); } } return (4); }问a本算法采用什么策略b填充上述4个空c求时间复杂度和空间复杂度。5.2 解题推演全过程拿到题先不急着填空。第一件事是确认算法策略。题目描述里出现了“dp[i][j]表示”“递推关系”“最大价值”这几乎就是把“动态规划”四个字写在脸上了。所以第一问直接答动态规划法或动态规划算法。再看代码填空。先看空1它在初始化循环里作用是当背包容量为0或物品数为0时最大价值必然是0。所以空1填“0”。空2在“j w[i]”分支意思是当前背包容量装不下第i件物品那就不选它结果等于前i-1件物品在容量j下的最优值即dp[i-1][j]。所以空2填“dp[i-1][j]”。空3在else分支此时容量足够需要在“不选”和“选”之间取最大值。不选是dp[i-1][j]选是dp[i-1][j-w[i]] v[i]合起来就是“max(dp[i-1][j], dp[i-1][j-w[i]] v[i])”。空4是函数返回值。dp表填完后前n件物品在容量C下的最大价值就是dp[n][C]所以空4填“dp[n][C]”。复杂度分析代码主体是两层for循环外层循环n次内层循环C次因此时间复杂度为O(nC)额外空间主要是二维数组dp[n1][C1]空间复杂度为O(nC)。完整流程下来4个空不到5分钟就能填完。这就是我反复强调的不要被代码吓住按“递推式—填表—返回值”的思路走动态规划题其实非常简单。这道题还可以再延伸一下比如有些年份会在代码里用一个一维数组dp[]做空间优化写法变成倒序更新for (int i 1; i n; i) for (int j C; j w[i]; j--) dp[j] max(dp[j], dp[j - w[i]] v[i]);如果看到这种倒序循环你要能反应过来它仍然是动态规划且是0-1背包的滚动数组优化空间复杂度降到了O(C)。这是近年真题里出现过的进阶问法理解原理比背代码更重要。6. 高频失分点与考前冲刺建议到了这个部分我想把考场上最常见的坑都列出来这些全是真实踩过的或者身边考生踩过的希望你能绕开。6.1 常见失分点速查第一个失分点是策略判断和代码填空互相矛盾。有的考生第一问答“动态规划”第二问代码填空却按照贪心的思路填比如在活动安排里填了一个max表达式。这种情况在阅卷时是明显丢分的。所以做完第一问之后一定要让后面的填空去验证第一问二者必须自洽。第二个失分点是数组下标基准混乱。软考的代码有时候数组从0开始有时候为了配合题目里的公式从1开始。答题时如果不看代码里已经有的语句很容易在递推式下标上多写一个减1。我的习惯是下笔之前先看循环变量的起点和已有数组访问语句例如已有代码中出现“dp[i-1][j-1]”那说明下标基本是从1开始的反向推回去填。第三个失分点是边界条件漏写。动态规划几乎必考初始化代码里经常挖掉dp[i][0]0或dp[0][j]0这种空。很多考生觉得这一句“太简单”反而在考场上脑子一空就填错。遇到初始化空牢记“容量为0或物品为0时结果一定为0”。第四个失分点是逻辑运算符的等于号。活动安排用s[i]f[j]还是s[i]f[j]0-1背包里用jw[i]还是jw[i]这些细微差别决定语义正确性。做题时必须把题干的“允许紧挨着”和“不允许紧挨着”“重量不超过”这类词圈出来。第五个失分点是复杂度漏项。贪心算法容易漏算排序的O(n log n)归并排序容易漏掉临时数组的空间O(n)这两处是复杂度小问里最经典的丢分点。提示软考下午题的填空空位阅卷时看重的是“逻辑表达式是否完整正确”。填代码填空时能写完整的赋值表达式就不要只写变量名比如要写“dp[i][j] dp[i - 1][j - 1] 1”而不是只写“1”。同时保持缩进清晰方便阅卷老师快速定位。6.2 考前一个月的训练方式如果你距离考试还有一个月第四题完全可以集中突破。我给的建议是“二十道真题加十段代码模板”。先说说真题怎么刷。把近五年真题的第四题全部找出来总共大约10到15道每道题严格按照考试时间来做不要翻书、不要看答案。做完之后对照答案重点不是看对错而是分析自己填空时的思维过程错在哪个环节。把每道题涉及的算法、填空中注意的细节、复杂度结论整理到一张表格里考前反复看。再说代码模板。第四题高频考察的代码其实就十段左右归并排序、快速排序、二分查找、0-1背包、最长公共子序列、矩阵连乘、活动安排、哈夫曼、Dijkstra、Prim。你要做到的不是“看过”而是“能默写”。我备考时是每天默写两段先看一遍核心代码合上书在草稿纸上写出来写错的地方就是你需要重点记忆的薄弱点。坚持两周考场上看到类似的代码框架会非常有亲切感。这里还建议你留意这些年考试偶尔出现的“变体”。同一算法换一个马甲比如0-1背包可能变成“资源分配”问题活动安排可能变成“会议室预订”问题LCS可能变成“基因序列比对”问题。但底层的递推式和贪心条件是不变的。做题时先剥掉问题描述的外壳找到核心模型再套用我们前面讲的模板。作为过来人我的体会是第四题是下午题里性价比最高的一道题。相比后面的Java/C程序设计大题算法题考察范围小、套路固定只要把核心代码模板吃透12分以上完全可能。考前别贪多求难把动态规划和贪心的几段核心代码按“递推式—填表—返回值”三部曲默写一遍上考场心里就有底了。最后再分享一个细节遇到策略判断题如果给的选项里有“回溯法”而你判断应该是“动态规划”可以看看代码里有没有递归加恢复现场的过程没有就放心排除。细节决定成败这道题也一样。