2019年秋季PAT甲级复盘+总结

  这次PAT甲级总体来说还是偏简单的,没有特别坑的测试点,也算是运气比较好,顺利的拿到满分,可以全力备战了。在这里简答分享一下当天的流水,以及对PAT甲级考试的一些心得体会。

考场

  由于报名的比较晚了,杭州除了传媒已经没有多余的场地,遂只能选择在下沙传媒学院考试,事实上如果愿意承担风险的话,完全可以等到截止报名前几天,此时会有很多学生退考,多关注报名页就可以抢占到玉泉校区的位置。
  到传媒是12点左右,来到生活区的美食广场,已经物是人非,爱吃的店面都已经搬走了,只剩下干锅的店面还在,但是老板也已经换过了。正直学生军训的时候,到处都是军训的学生和教官,到了现教5楼才见到了众多前来考试的考生,心情不免开始紧张起来,粗略的观察一下,大部分考生都是98~99年的,不免感叹老矣。

考试过程

  上机看了下环境Dev-C++、VC2010、Eclipse、PyCharm,环境还是比较齐全的。开始考试,粗略的看了下第一题,最大公约数加3000ms的时限,心里感到一阵凉凉,辗转相除法已经忘记了,不知道推不推的出来,于是直接跳过。
  第二题Merging Linked Lists,心里感到一喜,类似的题目题库里出现过很多了,例如1052 Linked List Sorting1074 Reversing Linked List1097 Deduplication on a Linked List,考前一天还刷过一道,码字、提交、一次过,唯一感到一点的不爽的就是VC2010的代码格式化功能比较弱,例如for(int i=0;i&ltcount;i++并不会格式化为for(int i = 0; i < count; i++),算是逼死我这个强迫症了。
  第三题Postfix Expression,改编自2017年考研408真题,真题求得是中缀表达式,题意很好理解,变形的二叉树后续遍历,码字调试,但是只要执行到std::string text; std::cin >> text;必定会产生异常,不知道是VS2010的原因,还是msvc编译器的原因,平时练习使用macOS + VS Code + clang + lldb,完全没有想到会有这种情况。写个简单的后序遍历,直接提交,过了一个点,把没有左子树的情况加上,Lucky,直接过。瞄了眼右边的哥们还在调第一题,看样子跳过第一题是个明确的选择。
  第四题Dijkstra Sequence,判断给定序列是否可能是Dijkstra寻找顶点的序列,直接码字,加点判断条件,竟然一次过,这题30分比较水,最简单的Dijkstra算法,完全不用考虑多条件的判断。此时看了下时间60分钟,当时的排名和另一个考生并列第一。
  回到第一题Forever,仔细看了下题目,发现最多只会求到89的最大公约数,内心已经止不住的开始膨胀,码字,竟然只过了第一个点,果然第一题一般是最坑人的,最后一题是最水的。重新看下题目,发现漏了一个条件,求的是大于2的质数,需要把2排除,补上判断,纳尼只过了前两个点。此时已经有考生拿到满分了,开始无尽的焦虑,在优化了公约数的算法,将整体算法从递归改为迭代等等尝试后,仍然没有头绪,此时离做完后3题已经80分钟过去了,难道又要报名冬季的PAT了吗。冷静下来重新读了下题目,发现最后的结果要排个序,套个map提交,过了前三个点,剩下最后一个超时。思考一下,剪枝将不可能的情况下直接排除,直接过,4个点耗时居然都小于10ms。
  至此拿到了满分,提前了半小时完成,同个考场有一个哥们大概比我快了20分钟。据说后面服务器还崩溃了,延长了考试时间。
  考试的代码位于我的Github仓库

考试心得

  这次考前大概刷了50道题,题库还剩30题,准备的不多,题库里有个哥们刷了5遍题库。这次甲级偏简单,相比于上一次的难度少很多,除了第一题几乎没有坑的测试点,其实第一题也不算特别坑,也没有题意复杂的题目,如果后三题即使某一道有坑,我可能也没时间调第一题了。回想今年春季的考试,前三题每一道题到最后都有一个点过不去,手动捂脸。据姥姥的微博,本场有154个满分,3900+的报名,但是证书上只显示了2600+,也就说有1300个人直接白给,白送30万,不过考场上确实有很多空位子。

考试趣事

  开始考试的时候瞄了一眼左边的哥们,是个93年的,打开了Dev-C开始撸代码。在我做第二题期间,一直唉声叹气,不停的在Dev-C、Eclipse、PyCharm之间轮换使用,每次打开写了两行代码便换下一个IDE。在我做完两题后,这个哥们喊来了老师,要求需要PHP环境,一口老血吐出来,第一次见到用PHP撸PAT的,平时练习居然用的也是PHP,不亏是世界上最好的编程语言,手动狗头,这个哥们可能是个PHP开发。最后老师表示无能为力,让他去另一个教室找主管老师,没想到这个哥们回来以后直接打开了百度搜索C++语法,接着就被系统自动终止考试了,据说老师让他尽力写。

PAT心得

  总的来说甲级涉及的都是基本的数据结构,没有涉及特别复杂的算法,有的题目可能需要仔细读题或是仔细分析,部分题目的测试点非常坑人,需要仔细思考每一种情况。强烈建议在中国大学MOOC上学习姥姥的数据结构课程,在练习时,建议自己思考思路,遇到过不了的点,也自己思考没有考虑到的情况,锻炼自己的思维能力。PAT非常爱考两个算法Dijkstra单源最短路径以及并查集,尤其是并查集,有些题目的题意和并查集完全不相关,但是最后的结果要用并查集处理,树的概念以及树的操作也几乎每次都会出题,需要常练习。

附注

  PAT考试从2019年开始,已经不再将真题放入真题题库了,需要在教育超市购买仿真卷,才能提交测试。据姥姥说每次考试的真题将会在2年后,免费开放加入题库。