[数据结构与算法]2021.9.11周六PAT甲级考试复盘与总结

周六PAT甲级考试复盘与总结

先说结论：仍未步入“高手”行列；现在的学习节奏与方法是对的，有十万分的必要坚持下去。

题目很简单，总体来讲极其可惜： T1 和 T3 考试时实在没有找到 bug 出在哪里，目前 T1 的 bug 已经找到，我们先且复盘考试。

复盘

浙江大学计算机程序设计能力考试（Programming Ability Test，简称PAT），据说浙江大学 CS 平均分 70 分，于是我也想试试。

考完试我觉得这个 70 分没有什么意义：

• 首先，本次这四道题目极其简单
• 其次， CS 的学生也并非有平日练习数据结构算法题的习惯，算法这个东西，大部分题目：「无他，唯手熟尔」

这次考 83 分十分可惜，可惜在题目太简单了，最后半小时，我就在死死盯着屏幕：逻辑上没问题啊？而且测试用例都通过了，怎么就有判分用例过不去呢？

昨天晚上睡前刷了刷知乎，果然大家都是甲级满分…恍然大悟 T1 在哪出了问题。

经验1：认真读题，不可臆测

第一题说：计算机保存一个数组，未必要在物理空间里申请一段连续的地址。

比如一个 int (32 bit) 数组长度为 20 ，其地址可能是：

// 首地址 元素个数
1024 10
0 5
2048 5

给我询问，问我第几个元素的地址是多少。

很简单的查询问题，怕超时，我还写了前缀和和二分（实际上知乎上说直接暴力枚举找都不会超时…）。

这题有两个坑点，我考试时全踩了：

• 最后问我，开了多少个内存空间？
  • 我以为，比如一共查询了两个数 0 和 19 ，那就妥妥地用到 1024 这块还有 2048 这块返回 2 呗；于是写个 bool used[N]; 计数
  • 结果着实被教育了一把：你要开到 19 ，0 到 19 之间的不开吗？因此你返回查询过的最大内存块编号就行了
• 如果查询全部越界，你也得返回 1 个地址空间而不是 0
  • 我已经看不到题目了，但是据说题目中其实写了：至少开一块地址空间！

这就很服气，原来一直以来，都是题目理解错了；而我一直以为是自己的逻辑问题，没有再读题。

PAT 甲级题目都是英文的，确实很考英文阅读理解。

经验2：继续刷题，打出自信

其实 T1 都错题也有自己不自信的锅：

• 逻辑是对的，但我非得认为“一定是自己哪里写的有疏漏”
• 如果我能咬定：“好，逻辑没问题了，我去再读一遍题目”，那将会是截然不同的结果

y 总就有这个自信，他讲过的每道题都会先说思路，然后亲手敲一遍，最后现场 debug 。自信来自于实力强大，如果我能强大到：『这个思路，这个实现，就没问题！如果出错了，一定是题目没理解对！』自然也不会有本次考试的可惜。

T3 我也没做成满分，我怀疑是 dfs 写得不好，周日上午打力扣也是，比完才意识到 dfs 有逻辑漏洞。我现在已经无法再看到当时的题目和代码了，也没必要纠结，再多做递归题目就是了。

经验3：复习没用，继续开眼

前 3 道题做的不好，于是跳到 T4 。

当时很慌，看到 T4 更慌了：靠，我要是考前复习下建树多好。

我除了 8 月份简单捋过两个序列遍历建树的代码就没再想过了。也确实没空。

但是记住了一条核心原则：有了中序遍历序列，则可以找到中心点，然后递归下去。

于是硬着头皮，竟然写出来了， 30 分满分。递归真的很神奇，觉得算法可能有点麻烦，但是写的时候才发现递归帮我们把好多逻辑自动实现了。

因此现在更应该：

• 把复习的时间更多地花在刷新题上
• 好好记笔记，好好总结，争取学一遍就有学懂学透，少被模板，多理解核心思路，省着以后再回来看

总结

强烈给大家推荐 y 总的 PAT 课，虽然我算是他比较差的学生了（感觉很多人考了满分）：AcWing.com PAT甲级辅导课

我 8 月 9 号买的， 9 月 6 号刷完，之后就没怎么碰过了。收获不小，关于算法细节的咱们以后慢慢唠。

算法这部分，上述三个经验总结起来，就一句话：现在的学习节奏与方法是对的，有十万分的必要坚持下去！ 现在的学习节奏与方法是对的，有十万分的必要坚持下去！ 现在的学习节奏与方法是对的，有十万分的必要坚持下去！

接下来准备干掉 y 总的算法提高课和算法竞赛进阶指南，这两节课内容太多了，先挑重点攻破吧！