2019冬季PAT甲级真题解析：算法拆解与考场策略

1. 2019年冬季PAT甲级考试全景回顾

1.1 这场考试的位置与分量

PAT（Programming Ability Test）甲级，在计算机相关专业的学生和职场人心里一直有点特殊地位。它不像ACM-ICPC那样强调高压对抗和极限思维，也不像期末考试那样偏重理论记忆，它考的是“给你一台电脑、一份题、三个小时，你能不能把实际问题转换成算法，再用代码干净利落地跑通”。甲级证书在很多公司的技术面筛选中是有实际参考价值的，尤其对于应届生，一份90分以上的成绩单，往往比简历上写的“熟悉数据结构与算法”更有说服力。

2019年冬季这场考试（通常安排在12月初），我当时也参加了。考完出来和几个同场的朋友交流，大家比较一致的感受是：整体难度比2018年冬季和2019年春季那两场要温和一些，尤其是前两道题，基本没有设置太多障碍，只要平时刷题量达标、手速正常，拿分比较稳。但第三题和第四题依然有足够的区分度——想上90分，必须对图论和复杂数据结构的应用有真正的理解，单纯背模板过不了关。

每年PAT甲级都是四道题，满分100分，一般按20分、25分、25分、30分的配比出题（偶尔有微调），考试时间180分钟。这个分值分布本身就是一种暗示：第一题是送分题，第二题是基础题，第三题是拉分题，第四题是压轴题。2019年冬季这场的分值分布也遵循了这个规律，所以考场上的时间分配策略，本质上是在跟这个分值结构做博弈。

1.2 难度感知与考场策略的联动

我回忆了一下，2019年冬季场的前两道题，风格偏向“模拟+基础数据结构”，只要你审题仔细、边界条件处理到位，基本20分钟到40分钟可以搞定。很多考友反映第一题甚至可以用“暴力模拟”直接莽过去，连优化都不用做——这在PAT甲级里并不常见，因为出题人通常会在第一题埋一个小坑，比如数据范围让你需要稍微想一下存储方式，或者逻辑顺序上有个反转。但这场的第一题确实相对直白。

真正拉开差距的是第三题和第四题。第三题我记得是图论相关，隐含了最短路径或者连通性的判断逻辑，如果你只掌握了DFS/BFS的裸写，没有理解“图论问题如何映射到数据结构”这一层，很容易在“怎么建图”这个环节卡住。第四题则涉及更复杂的数据结构操作，这类题历年都是用来筛选高分段选手的，2019年冬季也不例外。

从结果来看，2019年冬季的高分比例比前几场要高。身边考完晒分的朋友里，80分以上不在少数，90分也有好几个。这说明题目难度整体下调是事实，但也带来一个副作用：分数线被拉高了，如果你只拿了70分出头，在同届考生里就没什么优势。所以我的核心观点是：面对难度温和的场次，比的不是谁会做难题，而是谁在基础题上不丢分、在中等题上拿满细节分。这个思路贯穿了我下面所有的方法论。

2. 四类核心题型的算法拆解

2.1 模拟与链表操作题：审题比编码更费脑

PAT甲级的第一题，常年以“模拟”为底色。所谓模拟题，就是题目描述了一个看得见的场景和规则，你不需要发明新算法，只需按规则一步步实现。2019年冬季的第一题属于这类，核心点在于链表的操作和排序。

链表题看着简单，实际翻车率极高。原因在于PAT里的链表题不会直接给你next指针，而是给你一串“地址-值-下一地址”的三元组，你需要自己整理出真正在链上的节点。很多人第一次写会掉进一个坑：直接把所有输入节点都当成链表上的节点来处理，但题目里往往混入了若干个“孤儿节点”——它们出现在输入中，但根本不在你关心的那条链上。

正确的处理姿势是：

1. 用一个大数组（通常100000左右）按下标存节点的值和next地址，数组下标就是节点地址。
2. 从head地址开始，一路沿着next走一遍，把经过的节点地址按顺序收集到一个vector里。
3. 所有后续操作（反转、去重、排序、输出）只针对这个vector里的节点。

模拟题的代码通常不短，但每个分支都很简单，真正考验的是你能不能把题目描述翻译成逻辑。我的习惯是先在草稿纸上画一下数据流：输入长什么样、处理中间过程产生什么、输出需要什么格式。尤其是输出格式，PAT对每个字符都严格，空格、换行、-1的写法都错不得。2019年冬季这场就有不少人第一题因为输出格式不规范被扣了分，非常可惜。

还有一个细节：链表题里如果操作后链表为空，输出什么？如果只有一个节点，输出什么？这些极端情况都必须在提交前自己构造数据测一遍。考场上的时间压力下，人很容易“写完跑通样例就交”，但PAT的样例通常只覆盖happy path，边界全靠自己补。

2.2 树的遍历与重建：递归思想是根

第二题十有八九是树。树的题目在PAT甲级里几乎场场必考，因为二叉树的前序、中序、后序、层序遍历，以及通过两种遍历序列重建二叉树，考察的是递归思想、指针/下标边界控制，非常经典。

2019年冬季场考的树题，核心是“已知前序/后序和中序遍历，重建二叉树，再进行某种遍历输出”。思路是固定的：在中序序列里找到根节点的位置，它左边是左子树的中序序列，右边是右子树的中序序列；同时在前序/后序序列里对应的区间也就确定了。递归构建即可。

这里面最大的坑是递归参数的边界。我见过太多人写这类题时，递归函数里四个下标参数inL, inR, preL, preR传着传着就乱了。我的建议是：不要吝啬参数个数，宁可多传几个下标，也不要靠全局变量偷偷摸摸地算偏移。每次递归时要明确“当前这棵子树的中序区间是[inL, inR]，前序区间是[preL, preR]”，然后用根节点在中序里的位置k来计算左子树的节点数numLeft = k - inL，右子树的区间随手就能推出来：

Node* build(int preL, int preR, int inL, int inR) { if (preL > preR) return NULL; Node* root = new Node(); root->data = pre[preL]; int k = inL; while (in[k] != pre[preL]) k++; int numLeft = k - inL; root->lchild = build(preL + 1, preL + numLeft, inL, k - 1); root->rchild = build(preL + numLeft + 1, preR, k + 1, inR); return root; }

另外有个常被忽略的考点：如果题目给的是后序+中序，那重建逻辑改成从后序序列的最后一个元素定位根，其他思路完全一样。如果给的是层序+中序，则需要用“层序序列中第一个出现在当前中序区间的节点就是根”的规律来构建。平时刷题我建议把这三种重建都写一遍，考场遇到哪种都不慌。

2.3 图论与最短路径：建图是分水岭

第三题进入图论。2019年冬季这场的图论题，核心知识点是Dijkstra最短路径算法，但嵌套了附加条件——比如“路径最短的前提下，总花费最少”或“路径最短的前提下，经过的节点数最多”。这种双关键字最短路，是PAT甲级的经典考法。

Dijkstra算法的标准写法并不难，难的是改造成多关键字版本。很多人一上来就试图把两个条件揉进一个dist数组里，结果dist更新逻辑越写越乱。正确做法是：dist数组只维护第一关键字（路径长度），另开一个数组（比如cost数组或cnt数组）维护第二关键字，在if (dist[v] > dist[u] + edge)更新最短路径时，把第二关键字也同步重置；在else if (dist[v] == dist[u] + edge)相等时，再比较第二关键字决定是否更新。

// 多关键字Dijkstra核心框架 if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; cost[v] = cost[u] + c; // 第二关键字重置 pre[v] = u; } else if (dist[v] == dist[u] + w && cost[v] > cost[u] + c) { cost[v] = cost[u] + c; // 第一关键字相等时更新第二关键字 pre[v] = u; }

另一个重要考点是“如何把题目描述转换成图”。有些题不会直接说“这是一张图”，而是给你一堆城市、道路、距离、花费，或者给你一个矩阵让你自己建邻接表。建图这个环节，恰恰是很多人的分水岭——题目看懂了，但是不知道数据往哪个结构里塞。我的经验是：凡涉及“多个对象之间存在联系、联系有代价/距离”，第一反应就建图；节点个数少（200以内）用邻接矩阵，多则用邻接表。

图中还有一个高频陷阱：题目里的图不一定是连通的，也不一定是无向的。如果某条边是单向的，你按无向图建了邻接表，那Dijkstra算出来的结果从第一个样例开始就是错的，而且很难排查。我建议拿到数据描述先圈出“有向还是无向”这几个字，然后再动手写代码。

2.4 数据结构综合应用：压轴题的生存法则

第四题作为30分的压轴题，历年风格是“用高级数据结构解决复杂问题”，比如并查集+排序、树状数组、平衡二叉树、堆、哈希映射的综合应用。2019年冬季这场也延续了这个传统，考察的知识点组合相对冷门，真正考验的是你能否在有限时间内判断出“该用哪个数据结构”并正确实现。

面对压轴题，我的策略可能和很多人不一样：不强求满分。因为在180分钟的时限下，如果你花40分钟硬啃第四题结果没调通，等于白白浪费了能用来检查前面题目的大块时间。但完全不碰也不行，因为第四题往往有一些容易拿的子任务，比如第一小问只是简单的排序+输出，或者数据范围较小的case用暴力法也能过一部分。

一个比较实用的策略是：先读题5分钟，判断核心数据结构是什么、自己有没有把握完整写出来。如果把握不大，先跳过，去做检查；等前三题稳了、还有富余时间，再回来写第四题的暴力版或部分分版。PAT的评分是按测试点给分的，暴力版拿一半分是完全可能的。

我还想强调并查集。这个数据结构在PAT甲级压轴题里出现频率极高，因为它实现简单、思想巧妙，特别适合考“建模能力”。核心就三行——找根（路径压缩）和合并（按秩合并）：

int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void unionSet(int a, int b) { int ra = find(a), rb = find(b); if (ra != rb) parent[ra] = rb; }

难的不是实现，而是“你怎么知道这道题要用并查集”。我的判断依据是：题目里出现了“连通、分组、集合、共同”等描述，并且数据量较大（节点数超过10000），很可能就是并查集。比如“哪些人属于同一个社交圈子”“哪些计算机病毒样本属于同一个家族”这类题目，并查集就是最优解。

3. 从“能做题”到“稳拿分”：我的备考与实战方案

3.1 刷题策略：按题型横向突破，而非按套题纵向刷

很多初次备考PAT甲级的同学，习惯是做整套真题，做完一套对答案，再做下一套。这个方式不是不行，但效率偏低。我的做法是分阶段：

• 阶段一（基础期）：按知识点刷题，二叉树、图论、排序、哈希、模拟各刷20-30道，目标是建立“看到题目就能反应出它属于哪个知识模块”的直觉。
• 阶段二（整合期）：做整套真题，但要严格控制时间，模拟考场环境。每年有三场（春季、夏季、冬季），真题资源完全够用。
• 阶段三（冲刺期）：只刷近两年的真题，重点研究第三题和第四题的出题倾向，同时整理自己容易犯的低级错误清单。

这个策略背后的逻辑很简单：PAT的题目虽然每年都是新的，但知识点的分布高度稳定。你横向突破了每个知识点，再来看套题，本质上就是把这些模块按出题人的意愿组合起来而已。

有一个刷题原则我想特别强调：不要只看题解不写代码。很多人在论坛上看别人贴的代码觉得“看懂了”，真到了考场上自己写，不是这里忘了初始化，就是那里边界写错。必须亲自动手把每道题的代码敲出来、提交跑通、拿到满分，这道题才算真正过了。我给自己定的标准是：每道题都要拿到该题型的满分，如果拿了部分分，必须搞清楚剩下扣分点在哪里。

3.2 语言选择与输入输出：细节决定生死

PAT甲级支持C/C++、Java和Python。如果你刷题量还不大，我建议直接选C++。原因有三个:

第一，C++的STL在写数据结构和图论算法时有压倒性优势，vector、map、set、queue、priority_queue能省掉大量样板代码。第二，PAT的评测环境对C++的时间限制通常比较宽裕，而用Python写OJ题，同样的算法可能因为解释执行太慢直接被卡超时。第三，网上绝大多数题解和参考代码都是C++写的，你学起来比对着一门小众语言方便得多。

既然选了C++，就不得不提cin/cout和scanf/printf之争。我的建议是：考试时只要涉及大量输入，就用scanf/printf；如果习惯用cin/cout，必须在main函数开头加那行“魔法”：

ios::sync_with_stdio(false); cin.tie(0);

考试时间宝贵，这个细节平时就要养成肌肉记忆。还有一个相关技巧：读整行字符串时用cin.getline()或getline()，但要小心前面是否残留了换行符。我2019年冬季备考时，有一次调了一道题半个小时，最后发现是读入整数后直接getline()把换行符读了进去，导致字符串全为空。从那以后，我遇到混合输入（先数字后字符串）都会在整数读完后追加一个getchar()吃掉换行。

3.3 考场上的时间分配：前30分钟决定成败

180分钟做4道题，我的分配方案是：第一题30分钟以内，第二题40分钟以内，第三题50分钟，第四题剩余时间机动。这个方案的逻辑是：前两题是基本盘，必须快、准、稳；第三题是拉分项，值得投入；第四题能拿几分算几分，不执着。

每道题我给自己设了“止损线”：如果一道题写了30分钟还没过样例，立刻停下，重新读一遍题。很多时候卡住不是因为代码难写，而是题意的某个细节理解偏了。2019年冬季我考场上也有一次类似经历——做题做到一半发现自己的输出格式和题面要求不一致，幸好发现得早，改完还来得及。

还有一个很多考友忽略的点：做完一道题后，提交前务必自己构造几个边界数据测试。比如链表为空、树只有一个节点、图不连通、序列长度是1或最大值。这些case如果能在自己手里先跑一遍，就能避免大量因边界条件导致的罚分。我给自己定的规矩是：不到万不得已，不提交第一次就完事，至少自测三组数据再交。

4. 高频翻车点与排查实录

4.1 运行时错误排查：段错误往往不是“访问越界”这么简单

PAT报错类型里，段错误是最让人头疼的，因为它不会告诉你是哪一行出了问题。我总结的经验是，段错误的原因通常是这四类：

• 数组下标越界：访问了负数下标或者超过声明大小的下标。
• 栈溢出：递归深度过大，比如树的链状结构下递归建树或DFS。
• 空指针访问：链表操作或树操作里没有判空就访问了成员。
• 除零错误：求平均值或百分比时，分母可能是0。

排查的方法论是：先看数据范围，再检查递归深度，最后检查所有数组大小。如果代码里开了vector，注意下标从0开始还是从1开始；如果题目给的节点编号从1到N，你开数组时习惯性多开一位，通常就能规避越界。

还有一个场景特别容易中招：用递归遍历树或图时，如果图里存在环，记忆化搜索或visited数组标记不当，会无限递归导致栈溢出。判断标准是：写递归前先问自己一句“这棵树/这个图能保证无环吗？”不能保证就老老实实加visited标志。

4.2 超时的常见根源：不是算法复杂度太高，而是常熟太大

很多考生一看到超时，就以为是自己的算法不够高级，其实PAT题目的时限设置通常比较合理，朴素算法在大多数测试点上也能跑过。超时最常见的原因是STL容器使用不当。

比如map和unordered_map的选择：如果不需要有序性，只是拿来做查找或计数，务必用unordered_map，哈希查找的均摊复杂度是O(1)，而map是红黑树，O(log n)的查找在循环里会放大很多倍。再比如能用vector就少用list，能用数组就少用vector——数组的访问速度永远是最快的。

另一个隐蔽的常数开销是频繁的string拼接或复制。C++的string在拼接时会重新分配内存，如果你在一个循环里不断str = str + "x"，大量时间会耗在内存拷贝上。有个代码级别的优化习惯：能用char[]就别用string；如果非用string不可，尽量提前reserve容量。

结合2019年冬季考场上的实际情况，我有一次就是第三题用Dijkstra时，优先队列里存了太多重复的节点信息，导致时间复杂度退化，最后把“松弛成功再入队”这个条件加上，才跑进时限。这个优化其实是Dijkstra的标准写法，但平时练习时很多人写的是“无条件入队”的简化版，一上考场就被大数据卡住了。

4.3 逻辑边界：题目里那些“不会明说”的坑

PAT题目有一个特点：表面上给的条件都有用，但有些隐含条件需要自己推导。最常见的隐含坑包括：

• “保证有解”不等于“保证唯一解”。如果题目没有说答案唯一，输出要求里可能写的是“任意合法解”，这时你何必在非关键维度上纠结最优。
• “正整数”和“非负整数”的差距：一个是0不能接受，一个是0可以做边界。数据结构里的下标、计数，都要注意有没有可能是0。
• 题目描述的“第k大”到底是第k大的元素还是第k小的元素？这个定义在中国OJ里经常打架，必须以题目描述为准，不能凭经验。

我在2019年冬季备考期间踩过一个类似坑：那道题要求输出“从大到小排名第k的学校”，我以为是从小到大，结果样例都没跑通。后来仔细读题才发现“第k大”的定义，改一行比较逻辑就过了。这个教训让我养成了一个习惯：每道题的输出要求读三遍，尤其是“大、小、前、后、升序、降序”这类词，宁可在读题上多花两分钟，也不在实现后返工。

4.4 常见问题速查表

5. 备考之外：一些更底层的体会

写到这里，想聊一些考完之后才慢慢意识到的东西。PAT甲级表面上是一场考试，但它真正训练的是把一个模糊的问题变成清晰的逻辑链条的能力。这种能力不会因为你考完就把证书锁进抽屉而消失——处理业务需求时拆解模块、写复杂功能时考虑边界条件、排查线上问题时定位根因，本质上都是同一套思维。

我个人在备考过程中最大的收获，其实是养成了“读题三步走”的习惯：第一步，圈出数据范围（决定算法级别）；第二步，圈出输出要求（决定实现细节）；第三步，圈出所有“保证”和“不保证”的约束（决定边界处理）。这个习惯在我后来的工作和写代码中都受益匪浅。

关于要不要报班、要不要上培训班，我的观点一直没变：PAT完全可以自学，但需要一个系统的刷题计划和一个可以交流的圈子（对象是谁不重要）。一个人闷头刷题最大的问题是容易陷入“我以为我懂了”的幻觉，而跟别人交流同一道题的不同解法，会迅速打破这种幻觉。如果身边没有一起备考的人，多看看公开的题解讨论，也有同样的效果。

最后再分享一个考场小技巧：时间到之前5分钟，如果还有题目没提交完整，不要再写新逻辑了，立刻检查所有已经写好的代码有没有“提交前忘记注释掉的调试输出”。调试输出导致大面积答案错误，是每年考场都会上演的悲剧。稳妥、审慎、留有余量——这不只是PAT的应试策略，也是工程师该有的素养。