企业官网建设流程全解析

复试机试结束，趁着记忆还热乎，赶紧把2025年中山大学计算机考研复试机试真题整理出来，附上考场上写的解题思路和AC代码。备战的学弟学妹们可以直接拿这几道题练手，重点看我解题时的切入点，以及那些特别容易丢分的边界条件。中山的机试一直走“基础不偏、细节要命”的路线，这次四道题分别考了二叉树的递归重建、并查集与最小生成树、动态规划回溯、栈的括号匹配，覆盖了大部分高校复试机试的高频考点。

如果你正在准备这家或同类院校的机试，建议先把C++基础语法过一遍，尤其是指针、引用、STL容器这些，然后集中刷图论、DP和字符串的题。下面进入正题，每一题我都会给出完整的题目描述、输入输出样例、解题思路和能通过判题机验证的AC代码。

1. 四道题的难度阶梯与考场策略

先说整体感受，四道题并非随机排列，难度明显是递进的。

第一题二叉树重建属于“数据结构送分题”，只要递归边界写对，基本白给。第二题最小生成树考的是Kruskal算法和并查集操作，属于图论里最基础的题型，中等水平考生十几分钟就能搞定。第三题最长公共子序列（LCS）在多项式动态规划里也算经典，但难点不在计算长度，而在回溯输出任意一个具体的子序列，容易在“下标偏移”和“方向选择”上卡顿。第四题括号匹配看起来最简单，但括号种类增加到三种，且空栈和栈残留这两个坑特别隐蔽，全场翻车的人不在少数。

时间分配上，我一小时十分钟做完了前三题，剩下五十分钟全部砸在第四题和整体检查上。个人建议把前两题控制在二十分钟内，第三题和第四题各留三十分钟，最后留十分钟回去补边界数据测试。机试环境允许使用本地编译器，但判题机只认输入的最终结果，所以考场上的代码不需要写注释，可读性自己看得懂就行，优先保证运行时间。

另外说一个细节：四五道题里只有部分题目会明确提示“多组测试数据”，但中山往年风格是能测多组就测多组，所以我在写代码时统一用了while(cin >> n)格式，既适应单组也能应付多组。这个习惯建议你也保持。

2. 真题一：前序中序重建二叉树，后序一行输出

2.1 题目描述与样例

二叉树的每个节点用大写字母表示，且序列中不会出现重复字母。输入第一行是一个整数n，表示节点数量；第二行是前序遍历结果；第三行是中序遍历结果。要求输出该二叉树的后序遍历结果。

样例输入：

9 ABDGHCEIF GDHBAEICF

样例输出：

GHDBEIFCA

这道题要求是多组输入，n=9只是其中一组。最后一行结束后再读入会碰到EOF，程序正常退出。

2.2 分治重建的核心思路

前序遍历的第一个字母一定是根节点，比如样例里的A。在中序遍历中找到A的位置，左侧GDHB就是左子树的中序序列，右侧EICF是右子树的中序序列。同时，根据左子树的中序序列长度，可以切分前序序列中左子树和右子树的部分。

以样例为例：前序序列ABDGHCEIF，根A下一位B，在中序序列中B的左子树部分长度是3（GDH），右子树为空。于是左子树的前序区间是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 i=inL;i<=inR;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而不是Prim

Kruskal和Prim都能求最小生成树，但机试环境的输入是边集，Kruskal只需要把所有边按权重升序排序，然后用并查集判断两端点是否已经连通即可。代码结构清晰，容易调试。Prim更适合处理稠密图，如果输入是邻接矩阵，用Prim更方便。但这里给了m条边，且m最大不超过10000，Kruskal的复杂度是O(m log m)，完全够用。

Kruskal的核心是“贪心选最短的边，只要不构成环就加进来”，并查集在这里承担两个职责：判断在加边之前两个顶点是否已经属于同一个连通块；如果不是，则把这两个顶点合并。当选中的边数达到n-1时，最小生成树就找完了。

3.3 AC代码（C++）

#include <bits/stdc++.h> using namespace std; struct Edge { int u, v, w; }; vector<Edge> 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就一定是答案，但cnt<n-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

样例输入：

([)]

样例输出：

NO

5.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; } stack<char> 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 边界条件：空栈与多余左括号

我考场上看到不少人在([)]这种类型不匹配的样例上挂掉，但更隐蔽的是空栈和栈残留的组合场景。

比如输入)，栈空，直接ok=false，没问题。输入(，遍历结束时栈里还有元素，ok=false，没问题。但如果你在遍历过程中遇到右括号时先判断match再判断空栈，就会对空栈调用st.top()，导致运行时错误。所以“空栈判断”一定要放在match之前。

另一个细节是st.empty()检查在循环内和循环外各写了一次，两个都不能少。循环内的空栈检查解决“右括号无匹配”的情况，循环外的空栈检查解决“左括号多余”的情况。

我当时写完这道题还剩二十多分钟，回头用几组极端数据试了试程序：空字符串、单左括号、单右括号、([)]、(([]))，全部符合预期。这种“写完就用边界数据自测”的习惯，建议你也养成，能救不少分。

四道题说完了，最后再提醒一句：中山大学的机试题目本身难度并不高，但判题机对多组输入、边界数据和输出格式的要求很严格。复习时不要只盯着算法模板，多花点时间练习while(cin >> ...)、getline读取、栈的判空这些基础操，往往比死磕一道难题更有性价比。祝备考顺利，考场见真章。