PAT 甲级 刷题日记|总结 习惯 刷题计划（动态更新ing）
2021-08-09 本文已影响0人
九除以三还是三哦
甲级考察大纲
在达到乙级要求的基础上，还要求：
1· 具有充分的英文阅读理解能力；
2· 理解并掌握基础数据结构，包括：线性表、树、图；
3· 理解并熟练编程实现经典高级算法，包括哈希映射、并查集、最短路径、拓扑排序、关键路径、贪心、深度优先搜索、广度优先搜索、回溯剪枝等；
4· 具备较强的问题抽象和建模能力，能实现对复杂实际问题的模拟求解。
刷题计划
- 第一遍：按知识点刷题：原本是按照晴神宝典来刷，但是里面涉及的题目不全，知识点的复习已经在前期完成，所以此处的按照网上的经验贴的分类来进行。
- 第二遍：按顺序刷题、配合教育超市模拟题练习
好习惯
通过经验贴以及自己的感受，总结了一些好习惯，在以后的刷题中一定要保持：
- 单词积累
- 自己思考：这点很重要，自己动手才能检验出掌握程度
- 代码完成后，与示范代码对比总结
小经验点
- 输入输出一定严格比对
- 结尾多余的空格
- 输出字符的大小写问题
- 调试过程的代码一定在提交时注释掉
- 字符串
- 字符串转数字 num = stoi（str）超级好用！会有异常
- 数字转字符串 to_string(int/double)都可以
- 作为基本能力，几乎在所有题目中都会考察，但难度较低
- 链表
- 一般考察静态链表，都是25分的题，会建立、遍历即可
- 树
- 编号从1到n或者从0到n-1，就可以使用静态树
- 二叉排序树
- 二叉排序树的中序遍历是升序序列：该性质考察较多
- 给定结构填充树 / 给定输入序列建树 得到的二叉排序树都是唯一的
- 注意题目所给的二叉树定义——相同的数，放在左子树还是右子树中
- 图论
- 题目一般较长，且包含很多细节
- 节点名称是字符串时的处理方法：用两个map，对应名字到ID和ID到名字，初始时ID顺序分配，并保存记录即可。
- 其他
- 用万能开头时， 包含index变量会报错
- 大于 小于 不大于 不小于（no more than这些）一定要注意有没有等号，非常细节。
题型总结
以下题目均是笔者刷过的，保证分类的准确性（包含最新年份）
| 大知识点 | 小知识点 | 题目 | 总结 |
|---|---|---|---|
| 模拟 | 1031 1080 1105 1109 2020春-2 2020春-4 | ||
| 逻辑问题 | 1023 1082 10921093 1116 1117 1121 1124 1125 1128 1132 1136 1137 1139 1140 1144 1148 2020秋-1 2020秋-2 2020冬-2 | 一般会涉及字符串 读懂题 | |
| 数学问题 | 1078 1096 1104 1100 1152 2021春-1 2020冬-1 2020春-1 | 找规律，素数问题经常出现 | |
| 分数 | 1081 1088 | 最小公倍数、最大公约数 | |
| 静态链表 | 1032 1097 1133 | ||
| stl | map | 1116 1149 | |
| set | 1063 1120 1129 2020春-2 | ||
| 排序 | 普通排序 | 1113 1089(插入 合并排序)1098(堆排 插入排序） | 经典的排序算法要能手撕 |
| 结构体排序 | 1101 1025 1083 1095 1141 1153 2021春-2 | 难点不在排序 | |
| 字符串排序 | 1038 | 巧用sort | |
| 二叉树 | 完全二叉树 | 1064 1123 1147 1155 | |
| 二叉排序树 | 1043 1064 1099 1115 1135 1143（LCA） | 巧用性质 | |
| 遍历建树 | 1020 1127（后+中序建树） 1086 1138（先+中序建树） 1102 1119（后+前序确定树）2020秋-3 | ||
| 遍历 | 1102 1130 | ||
| 堆 | 1098 2021春-3 | ||
| 二叉平衡树 | 1066 1123 1135 | 模板固定 | |
| 一般树 | 一般树的遍历 | 1090 1106 1079 1004 1094 2020冬-3 | |
| 图论 | 基本考察 | 1122 1142 1134 1154 2020春-3 | |
| 哈希 | 1078 1145 | ||
| 拓扑排序 | 1146 2020秋-4 | ||
| 连通图、连通分量 | 1013 1021 1126 | ||
| 最短路径 | 1003 1018 1030 1072 1087 1111 2020秋-4 2021春-4 | 模板固定，可能会与dfs结合 | |
| 并查集 | 1107 1114 1118 | 模板固定，难度较低 | |
| 搜索 | DFS、 BFS | 1013 1018 1076 1091 1126 1103 1131 2020冬-4 | |
| 其他 | 树形数组 | 1057 | |
| 其他 | 贪心 | 1033 1070 2021春-2 |
