1. 这门课到底在考什么先看清期末的“势力范围”先说个很多人期末才反应过来的事儿《程序设计与算法基础II》不是《程序设计与算法基础I》的加长版而是一次彻底的换挡。头一学期你还在跟选择结构、循环嵌套、函数封装较劲到了II题目已经变成“给一堆点让你找最小生成树”“给两串字符串让你匹配子串”这种正儿八经的算法活。MOOC平台的期末考试尤其如此它不跟你讲情面客观题考概念辨析编程题直接上OJ判题错了就是错了没有部分分一说。我当年备考这门课的时候第一件事不是刷题而是去把MOOC的“考试大纲”和“章节测验”翻了个底朝天。这门课的期末考核范围大致固定在三大板块经典排序与查找、图论基础算法、字符串匹配与动态规划入门。热词榜上那串“冒泡排序算法c”“kmp算法”“prim算法”“匈牙利算法”其实已经把这门课的考点画出来了你盯着这些关键词去做针对性的复习比无头苍蝇式地翻整本书效率翻好几倍。另一个很重要的点MOOC期末和线下闭卷考试不一样它允许你在约定时间段内自行选择考试时间但一旦进入考试倒计时是挂在屏幕上的程序题要现场编译运行这就对熟练度提出了要求。你不是要把算法“看懂”你要把常见代码模板练到肌肉记忆看到题目描述就能条件反射出对应的数据结构。平时测验还能翻资料、查笔记期末考试选择题还能懵一懵但编程题不会就是不会这玩意儿骗不了人。所以这篇文章我打算换个讲法不按教材目录一章章带读而是按“期末最容易丢分的知识模块”来拆每个模块都讲清楚考什么、为什么考、最常见的坑是什么、考前怎么练。定位嘛就是给电子科大信软以及类似培养方案学校的朋友做一份考前冲刺的路线图。2. 排序与查找高频考点的代码细节与失分重灾区2.1 必须手写的排序算法及其适用场景热词榜上“排序算法”“堆排序算法”“归并排序算法”扎堆出现不是偶然。程序设计与算法基础II的期末编程题里排序题基本是“开门红”第一道或者第二道编程题如果不涉及排序反而会让人意外。这里说的排序不是让你调std::sort就完事儿MOOC期末的排序题常常戴着面具出场——比如“求逆序对数量”表面上是个计数题实际考查的就是归并排序的合并过程再比如“求第K大的数”你写个快速排序的partition版本去解比先全排一遍再取值要高明得多。我建议你至少能手写这四类排序冒泡排序理解元素交换的物理过程适合用来理解“稳定排序”概念考试中直接让你写完整冒泡的概率低但选择题爱考它的比较次数和交换次数。快速排序期末最常考的排序重点看partition函数的边界收缩逻辑以及递归退出条件。归并排序应用面最广因为它的合并过程能做很多“附加题”比如逆序对、链表排序。堆排序热词里单独出现了“堆排序算法”说明关注度很高。期末考它多半不是要求你写完整建堆代码而是考堆的性质、插入删除的时间复杂度、以及堆和优先队列的关系。有朋友会问“C里直接sort不香吗为什么要手写”考场上的情况往往是题目主考点不在排序本身而是排序背后的分治思想、递归结构、数据移动方式。你只有亲手实现一遍才能在变形题里看出它的原型。另外期末选择题的陷阱之一就是“以下哪种排序在最坏情况下时间复杂度为O(n²)——但平均性能最好”你要是没手写过快速排序很难真正记住这个结论背后的原因。2.2 二分查找的边界陷阱二分查找在这门课里的地位很微妙。它单独出题不难但喜欢藏在其他算法里比如查找旋转数组的最小值、在有序矩阵里搜目标数、计算浮点数开根号的近似值。热词里“二分查找算法”出现了说明搜索热度很高也就意味着大家都在这一块有困惑。二分查找最大的坑是边界条件。while (left right)还是while (left right)mid left (right - left) / 2是必须养成的习惯直接(left right) / 2在极端情况下可能整型溢出。期末复习时我建议你固定一套模板每次都用同一套边界写法别换来换去。我的固定模板是这样的int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }这套模板好记、好写而且适用于“查找确切值”的大多数场景。如果遇到“查找第一个不小于target的位置”这种题也就是lower_bound把判断条件改成nums[mid] target时收缩右边界最后返回left即可。记住一个原则你用哪套边界条件就要配套想清楚退出循环时left和right各自指向谁考场上一紧张最容易写错的就是这地方。2.3 排序算法选择题的隐藏考点除了编程题MOOC期末的选择题也喜欢在排序模块做文章。常见的隐藏考点有这么几类稳定性问题冒泡、插入、归并是稳定的选择、快排、堆排是不稳定的。考法经常是“以下哪个排序算法是稳定的”你得能说清楚为什么——本质看相同关键字元素在排序后是否保持原有相对顺序。时间复杂度的最好/最坏/平均情况快排最坏O(n²)归并和堆排都是O(n log n)插入排序在基本有序时能降到O(n)。MOOC选择题喜欢拿“输入数据已经基本有序”这个条件来问这时候插入排序反而比快排表现更好。比较次数与数据移动次数以冒泡排序比较次数恒为n(n-1)/2但数据交换次数取决于逆序度堆排序的比较次数不随数据分布改变都是建堆加调整这一点经常拿来跟快排做对比。我的建议是把四种排序的时间复杂度和稳定性整理成一张小表考前反复看几遍形成条件反射。特别是“堆排序建堆时间复杂度为什么是O(n)”这个结论选择题一旦考到很多人都栽在这里——因为直觉认为是O(n log n)实际上自底向上建堆是O(n)。3. 图论算法Prim、最短路与拓扑排序的解题节奏3.1 图论在期末试卷中的真实占比图论是程序设计与算法基础II真正区别于I的地方。从热词搜素看“prim算法”“最短路径算法”“匈牙利算法”都有很高的关联度。但说实话匈牙利算法在这门课里一般只是扩展阅读期末大规模考查的概率不大真正反复出现的是最小生成树Prim和Kruskal、单源最短路Dijkstra、Floyd、拓扑排序这三类。图论题的特征是代码模板长、边界条件多、时间复杂度分析复杂。很多同学复习的时候喜欢“看懂”图论算法觉得思路理解了就行可一道编程题丢到OJ上你会发现连图的存储都能写错。我强烈建议你动手实现至少三次图论基础代码模板第一次看着书敲第二次合上书默写第三次尝试不看模板直接根据题目要求改编。图论题在期末编程题里的出现位置一般偏后分值通常不低于20分。这和排序题是两码事——排序题你哪怕用最笨的O(n²)也可能过部分数据点如果OJ有部分分机制的话但图论题你如果没有选对算法复杂度直接超纲基本只能拿到“样例通过”甚至“样例都不通过”的结果。3.2 邻接矩阵还是邻接表选错就等着超时这是图论题里第一个决策点。平时练习用邻接矩阵方便、直观但期末OJ的数据范围往往在10⁵量级邻接矩阵的空间是n²很容易直接内存超限。所以邻接表是图论编程题的默认选择尤其是处理稀疏图的时候。// 邻接表的经典存储结构 struct Edge { int to, weight; int next; // 链式前向星写法也可以用 vectorpairint,int adj[N]; }; vectorvectorpairint, int graph(n 1); // 添加一条从 u 到 v、权重为 w 的有向边 graph[u].push_back({v, w});用vectorvectorpairint,int就够了简单直接不容易出错。链式前向星更省空间、遍历更快但记忆成本高期末这种时间紧张的场景下如果题目数据量没有大到必须用前向星就优先用vector邻接表把宝贵的脑力留在主算法逻辑上。判断场景很简单点数n ≤ 10³边数m ≤ 10³邻接矩阵完全没问题。点数n ≤ 10⁵边数m ≤ 10⁵必须邻接表。题目要求多次查询两点之间的距离邻接矩阵方便但一般考试题不会只为了查距离而让你存矩阵它考的是算法本身。3.3 Dijkstra、Prim、Floyd的区分与模板这三个算法经常被放在一起比较因为它们都有“每次挑一个最近的节点”“更新邻居”这种相似的动作。学着学着就混了。我提供一个不太严谨但特别好用的记忆方式Prim算法管的是“点集合扩张”每次从已选集合外挑一个离集合最近的点加入适合求最小生成树。Dijkstra管的是“起点到各点的最短距离”每次从未访问点里挑一个离起点最近的点加入适合求单源最短路。Floyd管的是“任意两点间的最短路径”三重循环暴力松弛适合n≤300的情况。Dijkstra的优先队列优化版是期末重点模板务必练成肌肉记忆vectorlong long dijkstra(int start, int n, vectorvectorpairint, int graph) { vectorlong long dist(n 1, LLONG_MAX); priority_queuepairlong long, int, vectorpairlong long, int, greater pq; dist[start] 0; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }注意这里有两个容易写错的地方一是if (d dist[u]) continue;这是“惰性删除”如果不加会导致重复节点反复入堆复杂度飙升二是dist的初始化有些题用的不是LLONG_MAX而是0x3f3f3f3f防的是后面做加法时溢出。Prim的模板和Dijkstra长得极像真正的区别就在于每轮更新的是“到集合的距离”还是“到起点的距离”。我当年就是因为这两个模板长得太像期末前特意把它们并排抄在一张A4纸上反复做“辨一辨”练习才彻底不再混淆。3.4 拓扑排序容易被忽略的送分题拓扑排序在期末里经常以选择题或者简单编程题的形式出现。它的考点很集中判定有向图是否有环、输出合法的拓扑序列。代码也不长就是维护入度数组加队列。vectorint topoSort(int n, vectorvectorint graph, vectorint indegree) { queueint q; vectorint result; for (int i 1; i n; i) if (indegree[i] 0) q.push(i); while (!q.empty()) { int cur q.front(); q.pop(); result.push_back(cur); for (int nxt : graph[cur]) { indegree[nxt]--; if (indegree[nxt] 0) q.push(nxt); } } if (result.size() ! n) { // 有环不存在合法拓扑序 } return result; }这里值得多提一嘴如果题目要求“输出字典序最小的拓扑序列”把队列换成优先队列小顶堆即可。这个变形在期末和平时作业中都出现过而且得分点非常明确值得记下来。图论这一块是复习投入产出比最高的部分。因为它的题型套路化严重最小生成树跑一遍模板、最短路跑一遍模板、拓扑排序跑一遍模板只要图存储写对、边界处理好基本就能拿到大部分分数。真正的分水岭不在算法的理解上而在“能不能在考场上快速写好模板并正确调试”。4. 字符串与动态规划KMP与递推模型的速成方案4.1 KMP算法理解的核心next数组的物理意义热词榜里“kmp算法”单独出现了说明这是搜索用户很关注的难点。KMP确实是这门课算法模块里抽象程度最高的一环很多人卡就卡在next数组上。我的理解方式是next数组记录的是“模式串中当前位置前的子串里最长的相等前后缀长度”。为什么要这个信息因为主串指针不回溯模式串指针在失配时跳到next[j]继续匹配。这个设计省掉了暴力匹配里大量的重复比较。期末对KMP的考查有两种形式一是选择题给个模式串算next数组二是编程题让你实现KMP匹配。如果你只是备考我建议你死记硬背一套求next数组的代码加上一个简单的使用场景。vectorint getNext(string needle) { int m needle.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 needle[i] ! needle[j]) j next[j - 1]; if (needle[i] needle[j]) j; next[i] j; } return next; } int kmpSearch(string haystack, string needle) { if (needle.empty()) return 0; vectorint next getNext(needle); for (int i 0, j 0; i haystack.size(); i) { while (j 0 haystack[i] ! needle[j]) j next[j - 1]; if (haystack[i] needle[j]) j; if (j needle.size()) return i - (int)needle.size() 1; } return -1; }这段代码里的while (j 0 needle[i] ! needle[j]) j next[j - 1];是最容易写错的一行。很多教材用的是next[j]跳到k的写法很容易把手写下标搞混。我自己用的是上述“减一型”next数组它在代码层面更少出现歧义也更好背——考前我建议你就认准这一套不要临时换流派。4.2 动态规划的递推模型识别动态规划在这门课里的地位是“压轴”。期末程序题最后一道题大概率是DP而且经常伪装成“数塔问题”“最长公共子序列”“01背包”这些经典模型。热词里虽然没有直接写“动态规划”但“数据结构与算法”“算法”这些大词背后DP都是不可回避的核心内容。我的经验是考前不要试图穷尽所有DP类型先把最常考的几类线性模型和背包模型吃透。复习时按以下顺序过一遍判断步骤题目是在求最值吗是求最大、最小、最长、最短吗如果不是可能不是DP。问题是否能划分成若干阶段每个阶段的状态能否只由前一个阶段推导出来能的话尝试定义dp[i]或者dp[i][j]。初始状态是什么边界条件是什么转移方程怎么写LCS是最典型的入门DPint longestCommonSubsequence(string a, string b) { int n a.size(), m b.size(); vectorvectorint dp(n 1, vectorint(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { if (a[i - 1] b[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[n][m]; }这里需要提醒一个低级但常见的错误a[i - 1]和b[j - 1]的下标偏移。DP数组从1开始编号是为了方便表达“前i个字符”这个含义字符串本身从0开始所以要偏移一位。考试时一旦混淆轻则答案差一位重则数组越界。4.3 贪心和DP的辨析别在最简单的地方丢分期末选择题里几乎必有一道“下列哪项适合用贪心算法解决”或者“这个题为什么不能用贪心”。有的同学DP学得不深但特别喜欢拿到题就拍脑袋“每一步取最优吧”这就是典型把贪心当成万金油。一个简单可靠的判断原则贪心要求局部最优能推出全局最优而DP允许你保留所有可能的状态并逐步递推。经典的“换零钱”“最大子段和”“活动安排”适合贪心但“01背包”“编辑距离”“最长上升子序列”就必须用DP。为什么最长上升子序列不能用贪心因为当前这一步的选择会影响后续的选择局部贪心会丢掉一些“暂时看起来不是最优”但后续可能翻盘的状态。我在考前的自查办法是每复习完一个DP模型就翻到之前的PPT再找一个长得像但使用了贪心的题目把两个题放在一起对比亲手在纸上写出“为什么一个用贪心一个用DP”的理由。这样辨析过一次之后选择题基本不会再丢分。5. 期末复习的时间规划与MOOC平台实操策略5.1 考前倒计时三周的分段复习方案复习方法上我教训最深的一点是“不要平均用力”。程序设计与算法基础II的知识点权重并不均匀热词搜索已经告诉你了排序、图论、DP、KMP这几个模块明显是搜索密集区也就是大家公认的难点和痛点。期末前我建议把时间切成三段第一周打地基。把排序、二分、栈、队列、链表这些I代内容快速过一遍重点练习写模板代码。这一周的目标不是学会新东西而是把旧知识回到“随手能写”的状态。第二周攻坚。主攻图论和DP每天至少写完2道图论题和2道DP题。不贪多但每一题都要做到“先自己思考再看题解最后合上书自己重写一遍”三遍法。图论模板和DP模板在这个阶段必须完成自动化。第三周冲刺。主攻MOOC平台上的往年样题和章节测验错题。这周起不再学习新知识点而是反复做套题模拟训练手速和节奏。KMP、Prim、Dijkstra的代码模板每天默写一遍默写到全对为止。这样的节奏下来到考前最后一天你不会慌因为你知道自己每个模块的时间投入和水平上限。5.2 MOOC客观题的抢分策略概念辨析是关键MOOC期末的客观题(选择、判断)占分比一般不小而且往往并非直接背诵教材原话而是考概念辨析。这意味着你在复习时就要留意教材里“对比”“区别”“优缺点”这类表述。比如“广度优先搜索使用什么数据结构深度优先搜索使用什么数据结构”——队列和栈这是一个经典送分题。“快速排序在有序情况下复杂度是多少为什么”——O(n²)因为每次partition选到极值递归树退化成单链。“哈希表冲突解决方式有哪些”——拉链法和开放定址法。客观题抢分的关键在于把每个算法的“代价模型”想清楚而不是停留在“会用”。一个很有效的复习动作是每复习一个算法就在一张卡片上写下它的时间复杂度最好、最坏、平均、空间复杂度、稳定性、适用场景、同类算法对比。考前拿着卡片过脑子比翻书一遍有效得多。5.3 编程题的时间分配与答题顺序MOOC期末的编程题通常有3到5道难度递增。前1-2题一般是送分题比如简单排序、字符串处理中间题开始上算法图论、DP最后一题往往是综合压轴。我的答题顺序策略是先把所有题都读一遍估个难度。用5分钟浏览题目描述标注每道题的数据范围和核心考点。从最简单的题开始做确保前两题每道都“一次通过样例”别在送分题上磨蹭但也不要掉以轻心不检查。再攻中等题一般对应最短路径、拓扑排序、二分答案这些模块代码模板熟的话15到20分钟搞定。最后剩多少时间就给压轴题能做多少做多少哪怕只能写出暴力解也要把暴力解的代码交上去因为OJ如果有部分分机制暴力求解也能拿分。这里想强调一点“样例通过”不代表“完全正确”。很多同学提交后显示“答案错误”就慌了但更高频的情况是“段错误/越界”和“超时”。段错误往往是数组开小了或者vector下标越界超时则是算法复杂度不够优秀需要优化数据结构或改用更优算法。提交前多看一眼自己的数组大小和循环变量是否在边界内能省下不少无谓的罚时。6. 实战中容易忽略的细节环境、调试与提交6.1 本地运行和在线OJ的差异期末考试用的是MOOC内嵌的在线评测不是本地IDE。这两者的体验差异非常显著。第一输入输出严格格式化。本地调试时你可以在cout里随意加调试信息但提交代码里必须删干净在线OJ比较的是你的标准输出和答案文件多一个空格、少一个换行都会判错。建议每道题提交前最后检查一次“所有cout是否都是题目要求的输出内容”。我建议平时练习时就养成一个习惯调试信息走cerr不干扰标准输出。第二数据规模可能比样例提示的高。期末编程题给的样例往往是常规数据但测试点里藏着大数据。你用O(n²)能跑过样例不等于能跑过额外的大数据测试点。提交前自己尝试估算一下如果n10⁵你的时间复杂度是多少会不会超时这个意识要从平时练习就开始培养。第三头文件缺失和命名冲突。#include bits/stdc.h在MOOC环境通常可以正常使用但不保证所有平台都支持。如果遇到编译错误提示某个函数找不到优先检查头文件是否齐全如果遇到奇怪的重名错误检查是不是自定义变量名比如next、prev和库函数重名这类问题很容易让人白白浪费时间。6.2 程序填空题的做题技巧MOOC期末还有一种必考题型程序填空题。它跟热词里的“python的顺序结构程序设计题”“头歌python程序设计答案”那种训练平台题型类似但本质都是在考“你理解代码的执行逻辑吗”。程序填空题的抢分要点是先通读全代码别一上来就空着想填什么。读懂变量命名的规律看清缩进结构然后根据空缺位置前后文推断。填的时候注意C的语法边界比如函数调用末尾有没有分号、条件表达式是否需要括号包裹、指针访问用的是.还是-。还有一个适用于几乎所有填空题的技巧从结果反推。如果空位后面是对结果的输出你可以根据输出格式和样例反推变量名或表达式。哪怕你对这段逻辑理解不深也能靠上下文拼出正确答案。我自己考前的习惯是在MOOC平台把每一章节的测验题重新做两遍因为你可能会在期末发现某些填空题就是从章节测验改的。6.3 考场上代码调试的优先级考场上不像平时你没办法一行行打日志慢慢看。我的调试优先级是第一确认数组大小定义一个长度为n的数组循环却从1到n会发生越界很多时候“段错误”就是这么来的。第二确认数据类型图论、DP里经常涉及很大的累加值用int会溢出需要用long long的地方别吝啬。第三确认初始化和边界条件dp[0][0]是多少dist[1]初始化了没优先队列是不是空的这些零碎的小点往往就是致命细节。我记得有一次练习Dijkstra样例怎么跑都对一提交就超时排查了半天发现是“没有加if (d dist[u]) continue;”导致节点反复入堆。这让我在后来的所有图论代码里都会先检查这一行。这种问题自己提前踩过一遍比在考场上交学费要划算得多。7. 一些考前值得反复默写的代码清单7.1 一周默写计划表我把考前一周的默写计划分享出来按天拆分单次耗时大概40到60分钟。不要觉得浪费时间默写代码这个动作的本质是把脑子里的“看懂”转化为手上的“会写”前者和后者之间的差距就是期末编程题的分数差距。天数默写内容默写要求第1天快速排序 归并排序含partition和merge函数独立完成第2天二分查找普通 lower_bound变体一次写完边界条件不能出错第3天Dijkstra优先队列版 Prim堆优化版两个模板并排默写注意对比区别第4天拓扑排序 并查集并查集要写路径压缩和按秩合并第5天KMP求next数组 匹配半小时内两段代码都完成且无手误第6天LCS 01背包DP数组初始化、转移方程、答案位置要写对第7天综合最长上升子序列 二分答案复习本周所有默写查漏补缺7.2 默写的正确姿势默写不是抄写。你要做到“不看参考代码从空白开始写出完整可运行的代码”。写完之后再做三件事一是在本地编译运行一遍确认通过编译二是用题目样例测一遍确认输出正确三是把代码和参考模板对比找到自己写走样或模糊的地方。有人说“我理解了就是写起来慢”这恰恰说明平时的输入形式太单一。期末编程题考的是输出能力不是输入能力。哪怕你全部听得懂、看得懂手写不出来考场上照样抓瞎。默写这个过程治的就是这个病。说到这儿想起我当初考前那个礼拜每天中午固定一小时拿一张A4纸一支笔把Dijkstra、KMP、DP模板轮着默写一开始要写二十多分钟还带错到第三天基本十分钟内写完且无差错。这种手感带进考场之后图论题对我来说就是“题读完了模板往上套调试两下提交通过”的流程心里一点不慌。希望这份经验对你有用。