复试机试结束趁着记忆还热乎赶紧把2025年中山大学计算机考研复试机试真题整理出来附上考场上写的解题思路和AC代码。备战的学弟学妹们可以直接拿这几道题练手重点看我解题时的切入点以及那些特别容易丢分的边界条件。中山的机试一直走“基础不偏、细节要命”的路线这次四道题分别考了二叉树的递归重建、并查集与最小生成树、动态规划回溯、栈的括号匹配覆盖了大部分高校复试机试的高频考点。如果你正在准备这家或同类院校的机试建议先把C基础语法过一遍尤其是指针、引用、STL容器这些然后集中刷图论、DP和字符串的题。下面进入正题每一题我都会给出完整的题目描述、输入输出样例、解题思路和能通过判题机验证的AC代码。1. 四道题的难度阶梯与考场策略先说整体感受四道题并非随机排列难度明显是递进的。第一题二叉树重建属于“数据结构送分题”只要递归边界写对基本白给。第二题最小生成树考的是Kruskal算法和并查集操作属于图论里最基础的题型中等水平考生十几分钟就能搞定。第三题最长公共子序列LCS在多项式动态规划里也算经典但难点不在计算长度而在回溯输出任意一个具体的子序列容易在“下标偏移”和“方向选择”上卡顿。第四题括号匹配看起来最简单但括号种类增加到三种且空栈和栈残留这两个坑特别隐蔽全场翻车的人不在少数。时间分配上我一小时十分钟做完了前三题剩下五十分钟全部砸在第四题和整体检查上。个人建议把前两题控制在二十分钟内第三题和第四题各留三十分钟最后留十分钟回去补边界数据测试。机试环境允许使用本地编译器但判题机只认输入的最终结果所以考场上的代码不需要写注释可读性自己看得懂就行优先保证运行时间。另外说一个细节四五道题里只有部分题目会明确提示“多组测试数据”但中山往年风格是能测多组就测多组所以我在写代码时统一用了while(cin n)格式既适应单组也能应付多组。这个习惯建议你也保持。2. 真题一前序中序重建二叉树后序一行输出2.1 题目描述与样例二叉树的每个节点用大写字母表示且序列中不会出现重复字母。输入第一行是一个整数n表示节点数量第二行是前序遍历结果第三行是中序遍历结果。要求输出该二叉树的后序遍历结果。样例输入9 ABDGHCEIF GDHBAEICF样例输出GHDBEIFCA这道题要求是多组输入n9只是其中一组。最后一行结束后再读入会碰到EOF程序正常退出。2.2 分治重建的核心思路前序遍历的第一个字母一定是根节点比如样例里的A。在中序遍历中找到A的位置左侧GDHB就是左子树的中序序列右侧EICF是右子树的中序序列。同时根据左子树的中序序列长度可以切分前序序列中左子树和右子树的部分。以样例为例前序序列ABDGHCEIF根A下一位B在中序序列中B的左子树部分长度是3GDH右子树为空。于是左子树的前序区间是BDGH中序区间是GDHB右子树的前序区间是CEIF中序区间是EICF。递归处理这两个区间最后输出根节点字母就是后序遍历的顺序。很多教程喜欢先建树再遍历。但机试时间紧张直接在递归函数里输出结果更干净省掉了建树的十几行代码也避免了指针操作带来的隐患。2.3 AC代码C#include bits/stdc.h using namespace std; string pre, in; void dfs(int preL, int preR, int inL, int inR) { if (preL preR) return; char root pre[preL]; int pos; for (int i inL; i inR; i) { if (in[i] root) { pos i; break; } } int leftLen pos - inL; dfs(preL 1, preL leftLen, inL, pos - 1); dfs(preL leftLen 1, preR, pos 1, inR); cout root; } int main() { int n; while (cin n) { cin pre in; dfs(0, n - 1, 0, n - 1); cout endl; } return 0; }代码里的核心变量是leftLen它表示左子树的节点个数决定了前序序列右半部分的起始位置。递归终点是区间为空也就是preL preR。2.4 这道题最容易翻车的地方最常见的问题有两个。第一很多同学习惯用string::find来找根在中序中的位置但递归时如果不限制查找范围可能会搜到非当前子树内部的字母。虽然题目保证字符唯一全局find通常也能找到但稳妥起见我这里用循环for(int iinL;iinR;i)限定范围避免在复杂逻辑中出错。第二后序遍历的递归顺序必须是“左、右、根”代码里cout root放在两个dfs之后。如果你写成先输出根那就变成了前序。考场上这种低级的顺序错误往往要用样例手动模拟一遍才能发现很浪费时间。第三多组输入时pre和in是string类型不需要清空因为每次循环都会用cin覆盖。不要画蛇添足写pre.clear()。3. 真题二最小生成树Kruskal的并查集功底3.1 题目描述与样例输入第一行两个整数n和m分别代表节点数和边数节点编号从1到n。接下来m行每行三个整数u、v、w表示u和v之间有一条无向边权重为w。要求输出该图的最小生成树总权重。如果图本身不连通输出-1。样例输入3 3 1 2 1 1 3 2 2 3 1样例输出2另一个样例输入4 2 1 2 1 3 4 2样例输出-1这道题同样支持多组建议用while(cin n m)处理。3.2 为什么选Kruskal而不是PrimKruskal和Prim都能求最小生成树但机试环境的输入是边集Kruskal只需要把所有边按权重升序排序然后用并查集判断两端点是否已经连通即可。代码结构清晰容易调试。Prim更适合处理稠密图如果输入是邻接矩阵用Prim更方便。但这里给了m条边且m最大不超过10000Kruskal的复杂度是O(m log m)完全够用。Kruskal的核心是“贪心选最短的边只要不构成环就加进来”并查集在这里承担两个职责判断在加边之前两个顶点是否已经属于同一个连通块如果不是则把这两个顶点合并。当选中的边数达到n-1时最小生成树就找完了。3.3 AC代码C#include bits/stdc.h using namespace std; struct Edge { int u, v, w; }; vectorEdge edges; int fa[1005]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool cmp(const Edge a, const Edge b) { return a.w b.w; } int main() { int n, m; while (cin n m) { edges.clear(); for (int i 0; i m; i) { int u, v, w; cin u v w; edges.push_back({u, v, w}); } sort(edges.begin(), edges.end(), cmp); for (int i 1; i n; i) fa[i] i; int total 0, cnt 0; for (int i 0; i m; i) { int fu find(edges[i].u); int fv find(edges[i].v); if (fu ! fv) { fa[fu] fv; total edges[i].w; cnt; if (cnt n - 1) break; } } if (cnt n - 1) cout -1 endl; else cout total endl; } return 0; }代码中find函数用了递归压缩路径虽然递归深度受并查集树高限制理论最坏情况下可能爆栈但在题目的数据范围下完全安全。如果你不放心可以改成迭代版。3.4 考场上的隐藏扣分点首先是并查集初始化。每一组新数据开始都必须重新赋值fa[i]i漏掉这一步会沿用上一次的合并结果导致后面判断全错。别笑考场上真有人在这栽了。其次是“不连通”的判断。很多人以为只要跑完循环total就一定是答案但cntn-1的情况必须输出-1。注意cnt要统计成功合并的次数而不是i循环了多少次。第三点边的结构体排序需要自定义比较函数。如果你用sort(edges.begin(), edges.end())结构体必须重载运算符否则编译报错。我习惯单独写cmp把比较逻辑和结构体定义分离逻辑更清楚。最后提醒一点最小生成树的权重总和可能超过int范围题目给的权重和边数虽然不大但保险起见可以开long long这里笔者为了和题目数据匹配用了int实际机试我建议直接long long total。4. 真题三最长公共子序列输出长度还要输出一个序列4.1 题目描述与样例输入两个字符串s和t长度均不超过1000第一行输出它们的最长公共子序列LCS的长度第二行输出任意一个满足该长度的子序列字符序列。如果长度是0第二行输出空行即可。样例输入ABCBDAB BDCABA样例输出4 BDAB注意这里输出的是子序列不是子串。子序列允许字符在原字符串中不连续但顺序必须保持。4.2 DP递推与回溯打印LCS长度的递推公式很标准用二维数组dp[i][j]表示s[0..i-1]和t[0..j-1]的LCS长度。当s[i-1]t[j-1]时dp[i][j]dp[i-1][j-1]1否则dp[i][j]max(dp[i-1][j], dp[i][j-1])。这个递推式隐含了“最后一位是否相同”的决策逻辑理解它比记住公式更重要。真正麻烦的是输出具体序列。常见错误是直接在计算长度时用path数组记录但动态规划的最优决策在回看之前并不知道所以更稳妥的方法是在dp填完后从dp[n][m]开始反向回溯如果s[i-1]t[j-1]说明这个字符一定在LCS中记下它然后同时退到i-1, j-1如果不相等比较dp[i-1][j]和dp[i][j-1]选择值更大的方向进入。如果两个方向的值相等随便选一个得到的就是另一个合法LCS。因为题目只要求输出任意一个LCS所以不存在“必须选哪个”的问题。4.3 AC代码C#include bits/stdc.h using namespace std; string s, t; int dp[1005][1005]; int main() { while (cin s t) { int n s.size(), m t.size(); memset(dp, 0, sizeof(dp)); for (int i 1; i n; i) { for (int j 1; j m; j) { if (s[i-1] t[j-1]) dp[i][j] dp[i-1][j-1] 1; else dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } cout dp[n][m] endl; string ans; int i n, j m; while (i 0 j 0) { if (s[i-1] t[j-1]) { ans.push_back(s[i-1]); i--; j--; } else if (dp[i-1][j] dp[i][j-1]) { i--; } else { j--; } } reverse(ans.begin(), ans.end()); cout ans endl; } return 0; }代码里dp数组定义在全局memset清零之后每组数据重新填充。输出空行时cout ans endl会直接换行符合要求。4.4 回溯时“相等任选”的细节在回溯时如果不相等且dp[i-1][j]和dp[i][j-1]相等代码走j--这个分支也就是向左边移动。你可能想问如果这个方向选择导致最后输出不是最优怎么办不会只要严格选择了等于dp[i][j]的方向最终回溯长度一定是dp[n][m]只是得到的字符组合不同罢了。另一个容易犯的错是回溯中遇到相等时先ans.push_back(s[i-1])再i--,j--这没问题但最后要reverse(ans.begin(), ans.end())否则得到的是LCS的逆序。我翻过几次车输出倒序序列被判错一定在结尾处理反转。如果你还想优化空间可以把dp从二维降到两个一维数组因为dp[i]只依赖dp[i-1]和dp[i]。但机试主要看正确性和速度代码直白一点不吃亏。5. 真题四括号匹配栈的经典考法5.1 题目描述与样例输入一个字符串里面只包含(,),[,],{,}这些字符。判断括号是否匹配。一个空字符串视为合法。匹配规则是左括号必须用相同类型的右括号闭合且左括号必须以正确的顺序闭合。如果合法输出YES否则输出NO。样例输入([{}])样例输出YES样例输入([)]样例输出NO5.2 栈匹配的逻辑括号匹配的经典解法是用栈维护“当前需要闭合的左括号”顺序。遍历每个字符遇到左括号(,[,{就压栈遇到右括号),],}先检查栈是否为空如果为空说明右括号没有匹配的左括号直接非法如果栈非空弹出栈顶检查它与当前右括号是否是同一种类型。遍历结束后如果栈非空说明有左括号没有被闭合也判非法。为什么用了三种括号因为不同种类的括号混在一起时“栈顶类型必须匹配当前右括号”这个约束才能体现出来。([)]这个反例就是栈顶是[却遇到了)虽然栈不为空但类型不匹配所以非法。5.3 AC代码C#include bits/stdc.h using namespace std; bool match(char l, char r) { return (l ( r )) || (l [ r ]) || (l { r }); } int main() { string s; while (getline(cin, s)) { if (s.empty()) { cout YES endl; continue; } stackchar st; bool ok true; for (char c : s) { if (c ( || c [ || c {) { st.push(c); } else { if (st.empty() || !match(st.top(), c)) { ok false; break; } st.pop(); } } if (!st.empty()) ok false; cout (ok ? YES : NO) endl; } return 0; }注意这里用了getline(cin, s)而不是cin s因为题目没有说字符串里不会有空格虽然样例里没有空格但保险起见用getline读取整行。如果题目明确说只包含括号字符用cin s也能过但考场环境里不知道输入是否包含空白字符所以这题稳妥优先。5.4 边界条件空栈与多余左括号我考场上看到不少人在([)]这种类型不匹配的样例上挂掉但更隐蔽的是空栈和栈残留的组合场景。比如输入)栈空直接okfalse没问题。输入(遍历结束时栈里还有元素okfalse没问题。但如果你在遍历过程中遇到右括号时先判断match再判断空栈就会对空栈调用st.top()导致运行时错误。所以“空栈判断”一定要放在match之前。另一个细节是st.empty()检查在循环内和循环外各写了一次两个都不能少。循环内的空栈检查解决“右括号无匹配”的情况循环外的空栈检查解决“左括号多余”的情况。我当时写完这道题还剩二十多分钟回头用几组极端数据试了试程序空字符串、单左括号、单右括号、([)]、(([]))全部符合预期。这种“写完就用边界数据自测”的习惯建议你也养成能救不少分。四道题说完了最后再提醒一句中山大学的机试题目本身难度并不高但判题机对多组输入、边界数据和输出格式的要求很严格。复习时不要只盯着算法模板多花点时间练习while(cin ...)、getline读取、栈的判空这些基础操往往比死磕一道难题更有性价比。祝备考顺利考场见真章。