如果你刷PAT乙级已经刷到了1051题差不多也到了最容易放弃的时候。前一百道题还能靠for循环、if-else、printf硬刚过去但从这个区间开始题目的难度肉眼可见地爬坡链表、树、堆、DFS/BFS陆续登场题面包装也越来越花哨。举个真实的例子题号1037那道题把背景搬到了霍格沃茨名义上是魔法世界找零钱本质上就是给你几个数、做一轮循环判断读题时千万别被哈利波特的剧情带跑。1051~1100这50道题正是从会语法迈向会算法的过渡地带。这篇文章不打算按题号逐题讲我按知识板块、题型套路、常见坑点和刷题策略这四个维度拆一遍。不管你是在校学生准备考研复试还是工作党想补算法基础只要你正在经历这个区间按这套思路去刷效率会比盲写高很多。1. 这50题到底在考什么——先看清战场全貌1.1 题号区间就是难度梯度PAT乙级题库是长期积累的结果题号越靠后整体难度确实在缓慢上升。1000题以前的卷子很多题就是一个排序加一个输出甚至一个printf就能过但到了1051~1100这个区间单纯靠暴力枚举格式化输出就能AC的比例明显下降取而代之的是需要你理解数据组织方式的题目。这个区间我自己的感受是它不像甲级那样要求你掌握高级数据结构的设计能力但也不会再像前面那样喂饭。链表不会用数组模拟树的三序遍历只会背模板不理解递归本质遇到图就只能干瞪眼。所以把这50道题当成一次算法基础补课来刷心态会好很多学到的东西也最扎实。1.2 高频考点分布根据我对这个题号区间的观察考点分布大致可以分成这么几块考点模块大致占比典型考查方式纯模拟题25%左右日期计算、找零钱、按规则变换数据字符串处理20%左右字符串查找、替换、进制转换、统计数学计算15%左右最大公约数、素数判断、分数四则运算链表/静态链表10%左右链表反转、链表去重、链表排序树15%左右前中后序遍历、层序遍历、重建二叉树图/搜索10%左右DFS/BFS遍历、连通分量统计堆/其他5%左右堆排序、优先队列的应用这个比例不是精确统计但能反映一个趋势纯模拟题仍然占大头数据结构题占了三成以上。这意味着刷到这个区间如果还在用每次现场想一个数组怎么存的方式来解题效率会非常低。你需要的是模板化的代码积累。1.3 这个区间最容易被忽视的一点读题成本到1051之后题目描述往往不再是一句话而是带大段背景故事、输入输出的说明里藏着细节。PAT的套路是真正关键的约束条件常常藏在注意或者输入格式的尾巴上。我自己刷题时踩过最离谱的一次是忘了处理输入中的重复元素导致查了半天。所以我的习惯是拿到题先别急着写花两分钟把输入格式、输出格式、数据范围这三样先划出来。数据范围决定了你这题能不能开大数组、需不需要用long long、循环能不能写三层。这一步做不好后面写代码容易白费功夫。2. 送分题和高频基础题拿下它们就稳了一半2.1 纯模拟题的破题套路模拟题在1051~1100区间大量存在特点是你不需要任何复杂算法只需要按题意一步步把过程用代码描述出来。难的不是过程而是边界和细节。举一个通用的例子日期计算。给两个日期算相差天数或者给你某年某月某日算星期几这种题的核心套路是先定义天数累计函数。每月的天数不能拍脑门写死需要处理闰年判断能被4整除但不能被100整除或者能被400整除的是闰年。int isLeap(int y) { if (y % 400 0) return 1; if (y % 100 0) return 0; if (y % 4 0) return 1; return 0; } int monthDays[2][13] { {0,31,28,31,30,31,30,31,31,30,31,30,31}, {0,31,29,31,30,31,30,31,31,30,31,30,31} }; int daysFrom0(int y, int m, int d) { int res 0; for (int i 1; i y; i) res isLeap(i) ? 366 : 365; for (int i 1; i m; i) res monthDays[isLeap(y)][i]; res d; return res; }这种代码写成函数后续任何日期题都能套。我自己刷题的体会是模拟题不能靠瞎试来debug一定要在草稿纸上把过程推一遍把例子的每一步手算结果写下来然后拿程序输出跟手算结果比对。只要样例过了再考虑边界值比如跨年、闰年2月29日这种特殊日子。2.2 字符串处理乙级永远的主战场字符串题在1051~1100区间几乎每隔几题就出现一次。C语言处理字符串说实话是比C要痛苦不少但只要掌握几个固定姿势就不慌。最基础的几个操作读入字符串用scanf(%s)只能读不含空格的词如果要读一行带空格的要用gets(s)或者fgets(s, MAX, stdin)。注意在scanf(%d)之后用gets前面一定要先getchar()把残留的换行符吃掉不然第一行会读到空串。这个坑我见过太多人踩而且踩得很憋屈——代码逻辑明明全对就是输入串了一位。#include stdio.h #include string.h int main() { int n; scanf(%d, n); getchar(); // 吃掉换行 char s[1005]; for (int i 0; i n; i) { gets(s); // 处理字符串 } return 0; }字符串转数字、字符串比较、字符串拼接这三个操作C语言分别对应atoi/sscanf、strcmp、strcat。还有一个高频操作是字符串中某个字符的计数直接循环加指针遍历。值得一提的还有字符串哈希统计类题目——比如统计一行文本中每个单词出现的次数。这种题用C语言其实也不难用strtok按空格和标点切分就行。但strtok会修改原字符串需要用strdup先拷贝一份否则查起错来很头疼。2.3 数学计算题gcd、素数、分数四则运算数学题是PAT乙级绕不开的一类好在它们考的数学知识都不深。最大公约数用辗转相除法这个模板必须背下来int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }分数四则运算是很多人觉得麻烦但其实是套路的题。核心思路是所有中间结果都用假分数保存约分在每一步运算后都做一遍避免中间结果溢出。分子分母超过int范围时果断用long longPAT的分数题特别爱在中间结果上设爆发点不加long long就会给出一个莫名其妙的浮点错误。素数判断在乙级里也反复出现。基础写法是用sqrt优化int isPrime(int n) { if (n 1) return 0; for (int i 2; i * i n; i) { if (n % i 0) return 0; } return 1; }一个容易被忽略的点i * i n这个写法n接近10^9时i*i可能溢出。更稳的写法是用i n / i。在1051~1100这个区间的素数判断题里n一般不会给到那种极限值但养成用i n / i的习惯总是没坏处的。还有个高频数学点是进制转换。10进制转n进制的方法就是不断取余数、反向拼接n进制转10进制则是从高位往低位乘加。这个也建议写成两个独立函数一劳永逸。3. 中后段题目的真正分水岭链表、树、图和堆3.1 链表题静态数组模拟是万能解法这里说的链表题在PAT乙级里通常是给一个内存地址、值和下一个地址的格式。很多人一看到地址就想去malloc这是思路不对。PAT乙级的链表题尤其是1051之后出现的几乎全部可以用静态链表解决——开三个数组用下标模拟指针。#define MAXN 100005 int head, n; int data[MAXN], nextAddr[MAXN]; // 读入所有节点后从头节点开始遍历一遍得到链表的有效顺序 int order[MAXN], cnt 0; for (int p head; p ! -1; p nextAddr[p]) { order[cnt] p; // p本身是“地址”data[p]是值 }这里有个很大的坑输入给的节点不一定都在链表上。有的节点是孤立存在的遍历时压根不会走到。如果不去重按所有节点排序或者统计就会得到错误答案。正确做法永远是先从head出发沿next走一遍收集有效节点再做后续操作。链表反转类的题目用上面的order数组做起来特别直观。把order数组里的地址倒序输出或者从后往前重设next都能实现反转。比如要对一段链表做区间反转就操作order的下标区间不需要真的改每个节点的next指针输出的时候直接按order的顺序输出就行。这种思路比靠修改next字段的实现方式简单得多也不容易出错。3.2 树的遍历与重建递归必须背成肌肉记忆树是1051~1100区间很多考生第一次明显感到不太行的知识点。树题在PAT乙级里不会考红黑树、平衡树考的是最基础的给一棵二叉树的前序中序或后序中序让你输出层序或者反过来给层序和某种序列求出另一种遍历结果。先记住一个底层规律中序序列配合任何另一序列都能唯一确定一棵二叉树。为什么因为前序/后序/层序都能给出根节点而中序能告诉你根节点的左右子树各包含哪些节点。记住这个核心逻辑重建二叉树就不用靠死记硬背。struct Node { int data; int left, right; } tree[1005]; int build(int preL, int preR, int inL, int inR) { if (preL preR) return -1; int root tot; tree[root].data pre[preL]; int k pos[pre[preL]]; // 用 pos 数组记录中序中每个值的位置 int numLeft k - inL; tree[root].left build(preL 1, preL numLeft, inL, k - 1); tree[root].right build(preL numLeft 1, preR, k 1, inR); return root; }层序遍历用的是队列循环不是递归void levelOrder(int root) { int q[1005], front 0, rear 0; q[rear] root; while (front rear) { int now q[front]; if (tree[now].left ! -1) q[rear] tree[now].left; if (tree[now].right ! -1) q[rear] tree[now].right; } }有一个必须注意的细节用数组模拟队列时队列空间一定要开够。二叉树的节点总数可能到几千有些人的队列数组就开了100结果越界还不知道报错成了运行错误。树的题目数组统一开成节点总数的两倍以上不会亏。3.3 图的遍历与连通分量1051~1100区间里的图论题说实话很少考到Dijkstra这种级别。最常见的是给一个无向图统计连通分量的数量或者判断两个点是否连通。解法就是DFS或BFS遍历。int G[1005][1005]; int visited[1005]; void dfs(int u, int n) { for (int v 1; v n; v) { if (!visited[v] G[u][v]) { visited[v] 1; dfs(v, n); } } }统计连通分量就是循环每个未访问的节点每进入一次dfscount加一。这套模板用在朋友圈、社交网络类题目上几乎不用改。如果遇到图比较大但边稀疏的题邻接矩阵可能开不下10000个点就存不下了要改用邻接表。C语言里可以用vector这样写#include vector using namespace std; vectorint G[10005]; visited[u] 1; for (int i 0; i G[u].size(); i) { int v G[u][i]; if (!visited[v]) dfs(v); }这里的核心还是visited数组的标记时机。我建议在入栈之前就标记不要等到出栈的时候再标记否则在环图中会反复入栈时间直接爆炸。这个细节靠BFS时特别重要。3.4 堆手写父节点调整别偷懒堆排序和建堆在1051~1100区间也偶有出现。C语言可以直接手写堆调整函数核心是向下调整和向上调整两个操作。建堆的经典写法是从最后一个非叶子节点开始向下调整。void downAdjust(int heap[], int low, int high) { int i low, j 2 * i; while (j high) { if (j 1 high heap[j 1] heap[j]) j; if (heap[j] heap[i]) { int t heap[i]; heap[i] heap[j]; heap[j] t; i j; j 2 * i; } else break; } }堆的题目出现频率不算特别高但一旦出现通常就是判断给定序列是否是大根堆或者输出堆排序的每次调整结果。这类题的关键是理解堆是一棵完全二叉树可以用数组线性存储。下标从1开始能让父子关系简单很多下标为i的节点左孩子是2i右孩子是2i1。为了这个便利我从一开始就习惯把数组下标1空出来不用实际存值从1开始能少踩很多坑。4. 从思路到AC几组可以直接抄的代码模板4.1 一条完整的静态链表排序题流程这里给出一个我很常用、也推荐你直接用的模板它涵盖链表排序的核心步骤。假设题目给了若干节点每个节点有地址、数据、下一个地址要求按数据升序输出链表。完整流程分四步存节点、遍历链表收集有效节点、按数据排序、格式化输出。#include stdio.h #include stdlib.h #define MAXN 100005 typedef struct { int addr; int data; int next; } Node; Node nodes[MAXN]; // 以地址为下标存储 Node valid[MAXN]; // 收集链表中有效节点 int cmp(const void *a, const void *b) { return ((Node *)a)-data - ((Node *)b)-data; } int main() { int head, n; scanf(%d %d, head, n); for (int i 0; i n; i) { int addr, data, next; scanf(%d %d %d, addr, data, next); nodes[addr].addr addr; nodes[addr].data data; nodes[addr].next next; } int cnt 0; for (int p head; p ! -1; p nodes[p].next) { valid[cnt] nodes[p]; } qsort(valid, cnt, sizeof(Node), cmp); if (cnt 0) { printf(0 -1\n); return 0; } printf(%d %05d\n, cnt, valid[0].addr); for (int i 0; i cnt; i) { if (i ! cnt - 1) { printf(%05d %d %05d\n, valid[i].addr, valid[i].data, valid[i 1].addr); } else { printf(%05d %d -1\n, valid[i].addr, valid[i].data); } } return 0; }几个关键点你可能注意到了输出地址时的%05d是为了补足5位零遍历时用p nodes[p].next而不是直接遍历所有输入节点排序后要重新指定每个节点的后继地址。这些都是链表题里最容易出错的细节直接背下来可以少踩很多坑。有人会问这样排序后的next字段和原链表不一定一致输出真的没问题吗在PAT的链表题目里输出格式是按当前有效链表的顺序输出每个节点地址、数据、下一节点地址所以只要最终输出符合顺序就行不必维持原始的next字段。理解到这一层你就能明白为什么很多题解敢直接对valid数组排序。4.2 两种树遍历模板递归序和层序树的中序前序重建二叉树模板我已经在上面给出了。这里再补一个更简洁的已知中序和后序输出前序的递归函数这种题也经常出现void toPre(int inL, int inR, int postL, int postR) { if (inL inR) return; int root post[postR]; int k posIn[root]; ans[ansCnt] root; int leftLen k - inL; toPre(inL, k - 1, postL, postL leftLen - 1); toPre(k 1, inR, postL leftLen, postR - 1); }这个模板的核心不变后序的最后一个节点是根在中序里找到根的位置就能算出左子树长度leftLen左子树在后序中的范围是从postL到postLleftLen-1右子树从postLleftLen到postR-1。理解了这个不管题目要求输出什么序你都能改造。层序输出的那个模板我在3.2节给过了这里补充一个更稳妥的空树保护如果root -1直接return或者打印空行不然可能会因为访问tree[-1]而段错误。4.3 图的简单BFS模板BFS在图类题目里的地位不亚于DFS尤其适合求最短步数或者层数类的问题。PAT乙级里曾经出现过类似从某个城市出发能到达的所有城市数量的题目用BFS非常直观void bfs(int s, vectorint G[], int n) { int q[10005]; int front 0, rear 0; int visited[10005] {0}; visited[s] 1; q[rear] s; int count 0; while (front rear) { int u q[front]; count; for (int i 0; i G[u].size(); i) { int v G[u][i]; if (!visited[v]) { visited[v] 1; q[rear] v; } } } }注意BFS中visited的标记时机节点入队时标记而不是出队时标记。如果出队时才标记同一层的节点可能被反复加入队列导致重复访问甚至死循环。这是BFS最容易错也最难查的一类bug。5. 实战中跑不掉的坑调试、超时和边界条件5.1 运行错误的头号原因数组越界和非法访问PAT判题时常见的运行时错误C语言里多半是段错误。根源几乎都是数组越界或者访问了-1下标。比如树的题目里递归访问了空节点、链表的题目里访问了不存在的地址、静态数组开的太小。我的排查方法很土但有效先在本地把数组开到题目上限的两倍再加一个打印语句输出当前递归深度或者循环次数基本就能定位到是哪一次访问出了问题。有时是递归没有终止条件导致栈溢出这种你在本地运行会直接卡死一看便知。5.2 浮点精度陷阱PAT乙级很少直接考浮点数运算但只要涉及除法、尤其是分数比较就容易掉进精度陷阱。比如判断a/b是否等于c/d别直接比较浮点数正确做法是交叉相乘a * d c * b用整数判断完全避免浮点误差。如果题目明确要求保留几位小数那用printf(%.2f, x)就行但要注意四舍五入。C语言的printf四舍五入在浮点边缘可能会出现银行家舍入的情况。为了避免这种问题最稳妥的做法是对要输出的值加一个极小修正量比如printf(%.2f, x 1e-8)。这个1e-8的修正量不会影响真实值但能规避很多边界上的舍入错误。5.3 超时先看数据范围再决定算法1051~1100区间里超时的题一般不是恶意刁难而是考察你是否会用合理的算法。比如统计某字符出现次数有人用双重循环数据一大就超时。正确做法是一次遍历统计复杂度从O(n²)降为O(n)。还有个常见的低效点字符串拼接。C语言里循环strcat会导致二次复杂度因为每次拼接都要扫描到字符串最后。如果你需要在循环里反复拼接建议用字符数组维护一个写指针char res[100000]; int pos 0; for (...) { res[pos] curChar; } res[pos] \0;复杂度是O(n)远比strcat快。很多刷题者之所以卡在1e5级别的数据上就是因为用了这种隐藏的O(n²)写法。5.4 输入输出提速的实用细节PAT乙级的数据规模一般不大scanf和printf通常足够。但如果遇到大规模输入可以加一行语句提升IO速度C里ios::sync_with_stdio(false); cin.tie(0);如果坚持C语言也可以用getchar()手写快读函数但其实针对乙级题大多数情况下没必要。真遇到大数据量的题优先排查算法复杂度而不是纠结IO优化。我见过不少人在输入输出上较劲结果发现真正卡时间的是一层多余的循环。5.5 最冤的扣分点输出格式PAT对输出格式的要求非常严格多一个空格、少一个换行都会判格式错误。这里有两个通用规则行末不要有多余空格。稳妥写法是用变量控制第一个元素前不打空格后面的元素都先打一个空格再打数据。每行输出完要有换行符。反面教材是我自己经历过的一次输出数组时忘了末尾换行判题直接格式错误当时找了好久才找到问题。后来我养成了一个习惯——写完输出代码刻意检查每个printf末尾有没有\n检查循环中最后一个元素是不是没有多余空格。这两条在PAT的送分题里也算高频失分点。6. 怎么刷这50题效率最高——我的实际策略6.1 按专题刷而不是按题号刷很多人打开题库就从头往后做这其实是最低效的方式。1051~1100之间虽然整体难度爬坡但题目是杂乱的今天链表明天数学后天字符串你的脑子还没形成某类题型的套路就切换了战场刷完很容易忘。我的做法是把这50道题按知识点归类找一个星期只做链表题再找一个星期只做树题同类题目放在一起横向对比。你会发现链表题套路高度相似树的重建问题也就那几种变形。等一个专题的题刷完相关的套路就刻进肌肉记忆了遇到同类型的题哪怕没做过也能凭直觉写出七八成。6.2 卡题15分钟就放手刷题时最容易陷入的泥潭是一道题死磕两小时。我的规则是15分钟没有任何思路直接看题解看懂以后关掉题解自己重新写一遍。注意是看懂后就自己写而且隔两三天之后要再独立写一遍。只看不写的后果是眼睛会了手不会真正上考场或做套题时会原形毕露。用这个方法过一遍1051~1100第一轮可能慢但第二轮你独立能AC的比例会远超第一轮。这个区间值得刷两遍第二遍的收获甚至比第一遍还大。6.3 错题本比题数更重要我刷题时准备了一个错题本但记录的并不是题目和题解而是我为什么错了。常见分类是边界条件漏了、算法选错了、语法有盲区、格式没注意。每一类错题背后往往对应一个坏习惯而不是一个知识点。比如边界条件漏了这一类我总结出的高频诱因是只看题目的例子没自己想边界数据。后来我每道题写完都会主动试三组数据——最大值、最小值、单节点特殊情况。这个习惯帮我避开了很多次提交才AC的尴尬。当你把错题本的规律总结出来再遇到类似错误时你会更容易一眼锁定问题。6.4 时间分配上的建议假设你是在职备考或者课业之余刷题每天能抽出的时间有限。我建议工作日每天1到2题周末集中做一个专题3到4题。保持节奏比一天猛刷十题然后歇一周有效得多。刷到1051~1100这个区间遇到难题是正常的别自我怀疑硬着头皮写写完复盘一个月下来你的算法手感会有质的提升。我个人刷这50题时的感受是前面1000题你可能在积累信心后面这50题才是真正把基础算法打通的过程。哪怕有些题第一遍过不了只要你能把题解逻辑完全吃透、隔几天再独立写出来你就已经比大部分只会背答案的人强了。这也是PAT乙级这道坎最值得跨过去的原因——它逼着你把数据结构的手感练出来而不是停留在语法层面。