2025年哈工大计算机复试机试刚落下帷幕考研群里已经陆续有人贴出回忆版题目。我把出现频率高、代表性强的几道题整理成了这篇带完整解法的文章从出题意图、推导思路到可以直接跑的AC代码都拆开讲。如果你正在准备哈工大或者同类学校的复试机试这篇文章完全可以当作考前模板库用。机试这东西说穿了考的不是智商而是你在绝对紧张的状态下能不能把最基础的算法稳定地写出来、调通、提交通过。1. 先别急着刷题把哈工大机试这件事看透了1.1 机试在复试中的定位它考的是“稳定输出”而不是“炫技”很多人准备机试有一个误区以为要学一堆竞赛级别的奇技淫巧什么网络流、后缀自动机、平衡树拼命往深处钻。实际上哈工大机试的难度定位非常明确考察基本的编程实现能力和算法基础不追求偏难怪。从历年题目看核心范围基本锁死在模拟、链表、栈与队列、二叉树、简单图论、线性DP、并查集、字符串处理这些主题上。机试在复试总分中的占比不低具体比例每年以复试细则为准但有一点是确定的机试不过关笔试面试发挥得再好也白搭。我见过不少初试高分选手算法原理说起来头头是道一上OJ就卡在编译错误和边界条件上最后遗憾落榜。这个环节刷掉的人不是不会算法而是写不完整、调不出来、时间分配崩溃。所以准备机试的核心策略就是要把高频题型练到肌肉记忆做到看到题直接浮现模板而不是现场推演。1.2 考试环境与评测规则这些信息比刷题本身更重要哈工大机试通常使用黑盒评测也就是ACM模式程序从标准输入读数据往标准输出写结果评测机拿到你的输出和标准答案比对。这意味着三个很现实的约束第一你必须习惯自己处理输入输出格式任何多余的空格、换行、提示语都是错。第二多组输入是很常见的设定代码要考虑EOF结束、每组数据之间是否需要清空状态。第三C是全场最稳妥的选择STL容器和算法库能极大减少手写数据结构的时间和出错概率。虽然部分年份允许Java或Python但考场时间有限C配合bits/stdc.h这道万能头文件基本能覆盖绝大多数情况。我建议备考时直接上洛谷、牛客这种标准OJ练习不要只在IDE里写完看一眼输出就完事必须强迫自己提交、看评测结果因为WA和RE的反馈体验在考场上是一模一样的。2. 2025年考生回忆版真题拆解六道题从题意到AC每一道题我都按照“题意还原、考察意图、思路推导、AC代码、注意事项”五个层次来讲。题目描述来自考后回忆细节可能有出入但考察点是完全真实的。2.1 双向链表的区间翻转最容易被“指针绕晕”的模拟题题意还原给定一个长度为n的双向链表每个节点的值为1到n要求翻转从位置l到位置r这一段节点然后按链表顺序输出所有节点的值。考察意图这道题看着简单实际是在考两个东西第一你熟不熟悉双向链表的前驱和后继关系第二你的边界处理能力。如果真去用new Node()一个个动态建节点再翻转指针大概率会写乱。机试里最好的做法是用数组模拟链表用一个pre[]数组存前驱下标nxt[]数组存后继下标这样调试起来一目了然也不用担心内存泄漏。思路推导核心是三步走。第一步找到区间左端点的前驱L和区间右端点的后继R把整个区间从链表上摘下来第二步遍历区间内每个节点把它的前驱指针和后继指针交换实现区间内部反向第三步把翻转后的子链表重新接回L和R中间。这里有一个关键设计在链表的头和尾分别加一个哨兵节点0和n1。加了哨兵l等于1和r等于n的情况就不用特判了L和R永远都有有效值。#include bits/stdc.h using namespace std; const int MAXN 100005; int pre[MAXN], nxt[MAXN]; int n, l, r; int main() { while (scanf(%d%d%d, n, l, r) ! EOF) { // 0 为头哨兵n1 为尾哨兵所有节点初始化为正常双向链表 for (int i 1; i n; i) { pre[i] i - 1; nxt[i] i 1; } pre[1] 0; nxt[n] n 1; int L l - 1; // 区间左侧的前驱 int R r 1; // 区间右侧的后继 // 第一步把区间 [l, r] 从原链表中断开 int subHead l; int subTail r; nxt[L] R; pre[R] L; // 第二步翻转区间内部的 pre 和 nxt 指针 int cur subHead; while (cur ! R) { int originalNext nxt[cur]; // 必须先把原后继存下来 swap(pre[cur], nxt[cur]); cur originalNext; } // 第三步重新接回翻转后区间的头变成 subTail尾变成 subHead nxt[L] subTail; pre[subTail] L; nxt[subHead] R; pre[R] subHead; // 从头哨兵开始输出 for (int i nxt[0]; i ! n 1; i nxt[i]) { if (i ! nxt[0]) printf( ); printf(%d, i); } printf(\n); } return 0; }注意事项翻转内部指针时最容易犯的错误就是遍历方向搞混。因为你在循环里交换了指针如果仍用cur nxt[cur]去移动一旦走到当前节点nxt[cur]已经变成原来的前驱就会往回走造成死循环或重复翻转。解决方案就是在交换之前先把原后继暂存下来我代码里的originalNext变量就是干这个的。另外本题如果要求输出节点的值而不是编号只需要把i换成val[i]即可思路完全一样。2.2 二叉树的重建与层序遍历一旦掌握就是白给题题意还原给出某二叉树的前序遍历序列和中序遍历序列节点值互不相同要求输出该二叉树的层序遍历序列。考察意图二叉树遍历是数据结构课的必修内容机试里出现毫不意外。这道题真正考的是递归划分的思维前序遍历第一个节点一定是根拿着根去中序序列里定位左边是左子树、右边是右子树然后递归处理。思路推导先用哈希表把中序序列每个值对应的下标存下来这样每次找根的位置就是O(1)时间整体复杂度O(n)。递归建树的过程就是不断缩小前序和中序的区间左子树的长度由中序列中根的位置决定这步理解了整道题畅通无阻。建完树以后用标准BFS输出即可。#include bits/stdc.h using namespace std; struct Node { int val; Node *left, *right; Node(int v) : val(v), left(nullptr), right(nullptr) {} }; vectorint pre, in; unordered_mapint, int pos; Node* build(int preL, int preR, int inL, int inR) { if (preL preR) return nullptr; int rootVal pre[preL]; Node* root new Node(rootVal); int idx pos[rootVal]; int leftLen idx - inL; root-left build(preL 1, preL leftLen, inL, idx - 1); root-right build(preL leftLen 1, preR, idx 1, inR); return root; } int main() { int n; while (cin n) { pre.resize(n); in.resize(n); pos.clear(); for (int i 0; i n; i) cin pre[i]; for (int i 0; i n; i) { cin in[i]; pos[in[i]] i; } Node* root build(0, n - 1, 0, n - 1); queueNode* q; q.push(root); bool first true; while (!q.empty()) { Node* curNode q.front(); q.pop(); if (!first) cout ; first false; cout curNode-val; if (curNode-left) q.push(curNode-left); if (curNode-right) q.push(curNode-right); } cout endl; } return 0; }注意事项这道题有个细节多组输入时unordered_map一定记得clear()否则残留数据会直接导致下标定位错误。层序遍历输出的节点间空格格式也要严格按题目要求很多同学WA不是算法错而是输出格式多了一个行尾空格。如果题目要求输出后序遍历只需要在递归返回前打印根节点的值其他部分完全不变这类变形建议考前都练一遍。2.3 带路径输出的最短路Dijkstra模板别只背一半题意还原给定n个点m条带权无向边求从节点1到节点n的最短路径长度并输出一条最短路径经过的节点序列。考察意图最短路是机试图论题的重头戏但大部分同学背模板只背到dist[]数组忽略了路径记录。这道题就是要考察你能否在标准的堆优化Dijkstra里顺手维护前驱节点。思路推导堆优化Dijkstra用优先队列维护当前距离最小的点核心松弛条件是若dist[u] w dist[v]则更新dist[v]并记录pre[v] u。路径输出用一个小技巧从终点n不断沿着pre[]回溯到起点再翻转vector得到正向路径。这里优先队列里存的是{距离, 节点编号}并且用greater实现小顶堆。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 10005; struct Edge { int to, w; }; vectorEdge graph[MAXN]; int dist[MAXN], pre[MAXN]; int n, m; void dijkstra(int s) { memset(dist, INF, sizeof(dist)); memset(pre, -1, sizeof(pre)); dist[s] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期节点直接跳过 for (auto e : graph[u]) { int v e.to; if (dist[v] dist[u] e.w) { dist[v] dist[u] e.w; pre[v] u; pq.push({dist[v], v}); } } } } int main() { while (cin n m) { for (int i 1; i n; i) graph[i].clear(); for (int i 0; i m; i) { int u, v, w; cin u v w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } dijkstra(1); if (dist[n] INF) { cout No path endl; continue; } vectorint path; for (int cur n; cur ! -1; cur pre[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); cout dist[n] endl; for (int i 0; i path.size(); i) { if (i) cout ; cout path[i]; } cout endl; } return 0; }注意事项这道题有两个容易翻车的点。第一if (d ! dist[u]) continue;这行必须有它的作用是跳过已经被更新过的旧记录没有它复杂度会退化但注意这里用!而不是因为在非负权图中堆顶记录要么等于最新最短路要么是过期值用反而可能错过有效更新。第二路径回溯前pre数组要先全部初始化为-1否则如果目标节点不可达回溯循环会越界。另外如果题目要求字典序最小的路径可以在相等距离时比较pre的字典序或者对邻接表按节点编号排序后用严格小于更新。2.4 最长递增子序列两种复杂度都要烂熟于心题意还原给定一个长度为n的整数序列求最长严格递增子序列的长度。考察意图线性DP是机试最爱考的DP类型而LIS是其中最经典的载体。这道题下限可以O(n^2)暴力DP上限可以O(nlogn)贪心二分很多考生只记得nlogn的lower_bound写法却推导不出原理一换条件就懵。思路推导O(nlogn)的核心思路是维护一个数组d[]d[len]表示长度为len的递增子序列的最小末尾值。遍历原序列时用二分找到第一个大于等于a[i]的位置pos把a[i]放到那里去如果pos大于当前len说明这个数接上了更长的子序列len加一。严格递增用lower_bound如果题目改成了非递减就用upper_bound这个区别值得你标记在笔记旁边。#include bits/stdc.h using namespace std; const int MAXN 100005; int a[MAXN], d[MAXN]; int main() { int n; while (cin n) { for (int i 1; i n; i) cin a[i]; int len 0; for (int i 1; i n; i) { int pos lower_bound(d 1, d len 1, a[i]) - d; d[pos] a[i]; if (pos len) len pos; } cout len endl; } return 0; }注意事项这套O(nlogn)模板虽然简短但只适用于求长度。如果题目要求输出具体的最长递增子序列d[]数组本身并不是最终序列必须额外用pre[]数组记录每个数在DP过程中的前驱下标然后从最后一个数回溯。我备考时踩过这个坑现场临时加路径输出把自己绕晕了最后AC代码还是回到O(n^2)带路径版本。另外注意如果用while (cin n)处理多组输入d[]数组不需要清空因为每次会用len重新限定范围但a[]数组要重新读入。2.5 中缀表达式求值考场上的“纸老虎”题意还原给定一个由数字、、-、*、/和括号组成的中缀表达式计算其值除法为整除。考察意图表达式求值几乎是每年机试的常驻题型。它不涉及高深算法但极其考验代码的细致程度运算符优先级、括号匹配、数字的连续读取任何一处疏忽都会WA。思路推导双栈法是标准解法一个栈存操作数一个栈存运算符。遍历字符串时遇到数字就完整读取一串数字入栈遇到左括号直接压栈遇到右括号就一直计算栈顶直到遇到左括号遇到运算符先处理掉栈顶所有优先级不低于当前运算符的运算符再压栈。遍历结束后把栈里剩余的运算全部执行完操作数栈顶就是答案。#include bits/stdc.h using namespace std; int applyOp(int a, int b, char op) { if (op ) return a b; if (op -) return a - b; if (op *) return a * b; return a / b; } int main() { string s; while (getline(cin, s)) { stackint nums; stackchar ops; int priority[256] {}; priority[] priority[-] 1; priority[*] priority[/] 2; for (int i 0; i (int)s.size(); i) { if (s[i] ) continue; if (isdigit(s[i])) { int num 0; while (i (int)s.size() isdigit(s[i])) { num num * 10 (s[i] - 0); i; } i--; nums.push(num); continue; } if (s[i] () { ops.push(s[i]); continue; } if (s[i] )) { while (!ops.empty() ops.top() ! () { int b nums.top(); nums.pop(); int a nums.top(); nums.pop(); char op ops.top(); ops.pop(); nums.push(applyOp(a, b, op)); } ops.pop(); // 弹出左括号 continue; } // 处理运算符包括负数开头的特殊情况 if (s[i] - (i 0 || s[i - 1] ()) { nums.push(0); } while (!ops.empty() priority[ops.top()] priority[s[i]]) { int b nums.top(); nums.pop(); int a nums.top(); nums.pop(); char op ops.top(); ops.pop(); nums.push(applyOp(a, b, op)); } ops.push(s[i]); } while (!ops.empty()) { int b nums.top(); nums.pop(); int a nums.top(); nums.pop(); char op ops.top(); ops.pop(); nums.push(applyOp(a, b, op)); } cout nums.top() endl; } return 0; }注意事项表达式求值有一个大家都不太在意的坑负号。比如表达式-35遍历到-的时候操作数栈是空的按常规写法会再把栈顶两个数弹出来计算直接就崩了。我的解决方案是在-号前面补一个数字0把它当成0 - 3 5处理。判断条件是当前字符是-并且它位于表达式开头或者前面紧跟着左括号。同样地2*(-3)这种带括号的负号也要用这个办法处理。另外空格的处理、多位数读取、除0问题题目一般不会给但保险起见可以用整除都要在交卷前过一遍。2.6 带权并查集近几年越来越爱考的一类题意还原有n个元素初始各自为集合。m条操作第一种是查询x与y的关系能确定则输出关系不能确定则输出未知第二种是给定x、y以及它们之间的差值w表示y比x大w进行合并。考察意图普通并查集大家都背过但带权并查集是很多人的盲区。哈工大近年明显加大了对这类题的考察力度因为它既考并查集结构又考数学推导能力难度区分度很好。思路推导核心是维护两个数组fa[x]表示x的父亲val[x]表示x到fa[x]的权值或者说“差值”。find函数做路径压缩时递归找到根节点后要把val[x]累加上val[fa[x]]这样压缩后val[x]就直接表示x到根节点的差值。合并时如果x的根是rxy的根是ry需要把ry挂到rx下面并计算val[ry]使得val[y] - val[x] w成立。推导结果就是val[ry] w val[x] - val[y]。#include bits/stdc.h using namespace std; const int MAXN 100005; int fa[MAXN], val[MAXN]; // val[x] 表示 x 到 fa[x] 的差值即 x - fa[x] int find(int x) { if (fa[x] x) return x; int root find(fa[x]); val[x] val[fa[x]]; // 路径压缩时累加差值 return fa[x] root; } int main() { int n, m; while (cin n m) { for (int i 1; i n; i) { fa[i] i; val[i] 0; } while (m--) { int type, x, y; cin type x y; if (type 1) { // 查询 int rx find(x), ry find(y); if (rx ! ry) { cout Unknown endl; } else { cout val[y] - val[x] endl; // y - x 的差值 } } else { // 合并输入 w 表示 y - x w int w; cin w; int rx find(x), ry find(y); if (rx ! ry) { fa[ry] rx; val[ry] w val[x] - val[y]; } } } } return 0; }注意事项合并公式val[ry] w val[x] - val[y]推导的时候很多人懵我给你拆解一下。路径压缩后val[x]是x到rx的差值val[y]是y到ry的差值。我们想让ry以rx为父也就是要满足val[y] val[ry] - val[x] w整理一下就是val[ry] w val[x] - val[y]。这个推导要当作模板的一部分背下来考场上现场推太费时间。另外find路径压缩必须用递归写法否则更新val[x]的时机不对如果你对爆栈有顾虑可以改循环写法但难度翻倍不建议考场尝试。3. 考场实战从读题到AC的完整工作流3.1 三分钟读题法先看数据范围再想算法机试和平时刷题最大的区别就是时间压力一道题不可能留出半小时慢慢推。我自己的习惯是拿到题先不急着读故事背景直接扫三样东西n和m的取值范围、输入输出格式、有没有特殊修饰词。数据范围决定算法这是最朴素也最有效的判断依据n小于1000O(n^2)随便写n到1e5必须上O(nlogn)n到1e9基本是数学公式题。输出格式里有“字典序”“不超过”“严格”这类词都是出题人埋的坑必须圈出来。读题三分钟以内必须做出判断并开始写代码切忌反复怀疑自己是不是漏了什么条件。机试题目不会像竞赛题那样藏着弯弯绕绕的深意大部分是直来直去的宁可写完后反复对样例也不要迟迟不动手。3.2 先搭框架输入、输出、主流程按固定顺序写很多新手一上来就写核心算法写到一半发现输入漏读了一个变量又回去改代码结构一团糟。我的习惯是任何题目都先写三段框架先是while(scanf(...) ! EOF)的读入循环把题目要求的输入格式全部读一遍并处理好再是核心逻辑函数的空壳参数和数据容器都定义好最后是输出部分把格式串先写好再用占位符跑通流程。框架通了再往核心函数里填细节。这样做的最大好处是心理上的看到程序能完整跑完输入输出哪怕答案是错的心态也是稳的调试时能从“全盘崩坏”缩小到“某一步逻辑错”。另一个好处是如果题目变成多组输入你的框架天然支持不用二次改造。3.3 样例过了不等于AC五步自查清单提交之前花两分钟过一遍自查清单能救回不少无谓的WA。我自己的清单有五项全部压在记忆里第一边界值。l等于1或r等于n、n等于1、树为空、路径不存在这些最容易炸。第二多组数据之间的残留。全局数组、容器、计数器在下一组数据开始前必须清空vector要resizemap要clear。第三输出格式。行尾有没有多余空格每行末尾有没有换行多组输出之间有没有空行全部核对一遍。第四类型与范围。INF是否是0x3f3f3f3f乘法是否会溢出int要不要开long long。第五题眼复读。再念一遍题确认自己有没有漏掉“严格”“非递减”“从1开始编号”这种修饰。4. 高频踩坑记录与排查技巧实录4.1 运行时错误对照速查表机试评测结果就那么几种每种背后都对应一个常见的代码错误。我整理一张速查表遇到报错直接对着排查能节省大量时间。评测结果常见原因排查方向Compile Error变量名写错、少头文件、语法错误看编译信息重点检查函数签名和类型匹配Runtime Error数组越界、除以零、栈溢出、空指针检查循环边界、动态内存释放、递归深度Time Limit Exceeded算法复杂度过高、死循环、输入输出太慢确认数据范围与算法是否匹配关同步流Wrong Answer边界条件没处理、输出格式错、读入错位用极端样例自测重新读题Presentation Error输出多余空格/换行与标准答案格式不符逐字符对比输出格式尤其是行尾空格4.2 我踩过的三个典型坑第一个坑是全局数组残留。有次练习多组输入的Dijkstra题第一组数据跑得好好的第二组开始路径错乱查了半天发现是graph[]没清空上一组图的边全残留了下来。从那以后我养成了习惯所有全局容器在while循环开头统一clear()并且和输入操作写在一起防止漏掉。第二个坑是路径输出忘了reverse。第一次写Dijkstra带路径时回溯完顺直接输出路径数组结果是倒序的。检查了二十分钟才反应过来。其实这个错误特别好防路径回溯必然是先得到终点再得到起点要么原地reverse要么用递归从起点开始打印二选一写熟练就行。第三个坑是表达式求值里的负数。第一次自己写中缀表达式求值样例全是正数一切正常。结果加了-32这种用例直接崩溃因为操作数栈是空的pop了不存在的元素。后来学了补0大法才彻底解决。这里提醒一句机试题目描述里没说没有负数你就要默认它可能会有考点往往就藏在这种不起眼的地方。4.3 考前两周的复习节奏安排如果从现在开始算距离考试还有两周我的建议是不要再去学任何新算法了把复习重心压回高频模板和老题重做。第一周每天固定刷三到四道高频类型题链表、二叉树、最短路、DP、并查集、模拟题轮着来每道题都必须完整提交AC不允许在IDE里看完输出就算完。第二周进入全真模拟状态每天下午卡时间做一套完整题目4到6题统一按两个小时计中间不查资料、不暂停模拟考场的紧张感。每天睡前花半小时背模板不是背代码而是背每个模板的适用条件和边界坑。比如LIS的lower_bound和upper_bound分别对应什么条件、带权并查集的合并公式怎么推导、Dijkstra的堆节点什么时候跳过。这些知识点在两小时的考场高压环境里不可能现场推导靠的就是考前反复念到形成条件反射。我个人在实际操作中的体会是机试复习最忌讳的其实是“自我感动式刷题”每天刷十几道却全是重复确认自己会的真正薄弱的地方永远不碰。最好的备考节奏反而是每做一道题都问自己一遍这题考察的核心是什么我能不能不看模板徒手写出来如果两个问题里有一个答案是否定的这道题就不算过关必须重做。把这六类基础题吃透哈工大机试至少不会成为你复试中的短板。