PAT甲级考纲（最少的时间换尽可能多的分数）

骑猪看日落 2023-07-22 09:16 5阅读 0赞

**下面的考纲从最重要的、考试概率最大的开始讲起，用最少的时间得最多的分数。祝大家考一个好成绩！**

### 图论算法★★★★★ ###

图论算法几乎每年都有，99%会考，剩下1%是出卷老师啊想晃你一下。

### 搜索算法DFS/BFS★★★★ ###

假如出题老师手下留情，可能会出图的搜索问题。搜索算法一般以DFS和BFS为主，简单一点就是纯算法，难一点就是加上各种条件和**剪枝**。无论是在上机考试还是在PAT中，都属于基础题目，不一定出，但是出了你必须会。  
同时需要学会的配套算法还有**迭代**和**递归**，**强联通分量**和**连通分量**，所以迭代和递归不需要单独训练，可以跟搜索算法同时做练习。一道题目可以分别用DFS和BFS做一遍，加强熟练度。要会统计联通分量的个数。  
经典题目为“走迷宫”、“算水里有几块陆地”之类的题目，必须会做，都是下酒小菜。

练习题：PAT A 1106，PAT A 1103，PAT A 1091，PAT A 1013(统计强联通分量的个数)

### 最短路径★★★★★ ###

这是上机考试中图论算法最容易考的一点，不考这个考什么（PAT-A考到的可能性没这么大，但是万一考到了也跟尴尬）。  
**PAT-A最难的会让你输出最短路径，并且加条件，例如若路径相同则输出价格较小的一条，当价格相同时再输出最少时间的一条，最后输出最小值和路径。**  
所以这一条套路必须会，会一题即可：PAT A 1111

其他练习：PAT A 1003，PAT A 1018，PAT A 1030，PAT A 1087

### 图论知识★★★★ ###

在上机考试中这个点不经常考，但是在PAT中这个点不难，但是经常考。  
图论知识就是让你判断这个图是不是一个怎么样怎么样定义的图，这里面用到的方法其实还是搜索算法，只不过加上条件而已。只不过比较头疼的是题目给你的定义，题目给的定义不一定跟我们学过的离散数学一模一样，但是也是大差不差。所以在做题之前先看一眼中文的定义有个概念会加快读题速度，最后只要注意你理解的定义和题目给的定义有什么区别就行了。这块主要的出错点是自己设计的判断是否全面，可能出现不能全部AC的情况。  
下面给大家整理的是我遇到的一些图论知识的题目，见过题目即可，再变形也变不到哪里去的。

#### 哈密顿图 ####

哈密顿图 ：经过图中所有的节点的圈 。

1.是否是N+1个点。  
2.结点编号是否在范围内  
3.除起点外，每个点是否只出现了1次  
4.经过的边是否存在  
5.起点是否等于终点  
练习题：PAT A 1122

#### 欧拉图 ####

首先用深度搜索（或者并查集）判断是否是联通图，如果不联通则不是欧拉图。然后统计每个节点的度数，就能判断。

1.Eulerian path:欧拉路径 （每条边经过一次）  
2.Eulerian circuit：欧拉回路（起点终点是同一个点的欧拉路径）  
3.连通图中每个点的度数为偶数，则存在欧拉回路。这个图成为欧拉图。  
4.如果有两个点的度数为奇数，存在欧拉路径不存在欧拉回路。这个图称为半欧拉图。  
练习题：PAT A 1126

#### maximal clique ####

（也是给的一个什么定义，其实都是大差不差的）  
练习题：PAT A 1142

#### 旅行商环路 ####

练习题：PAT A 1150

### 并查集★★★ ###

并查集不难，学会套路即可。最多会让你最后**统计**有几个并集、每个并集里有多少元素。

练习题：PAT A 1118，PAT A 1107  
忒麻烦的一题：PAT A 1114

### 拓扑排序★★★ ###

拓扑排序跟并查集一样，可能会考，反正也不难，会一题就行。  
练习题：PAT A 1146

### 最小生成树★★★ ###

好像没考过，掌握Prim算法和Kruskal算法的基本使用即可。

### 树★★★★★ ###

树这玩意，也是PAT每年必考啊，但是PAT的考风跟上机考试不一样，这里总结的PAT风格题目，其他同学可以拿来巩固数据结构。  
考PAT的胖友每个点掌握一题，天下无敌。

### 树的遍历和性质★★★★ ###

每种类型会一题即可，要理解中序后序前序的遍历方法和转化，到能推出公式的情况就天下无敌。除此之外，也会牵扯到递归、迭代、队列的使用。

#### 已知先序中序求后序 ####

变形练习：PAT A 1043

#### 已知先序后序求中序 ####

练习题：PAT A 1119

#### 求结点数量 ####

练习题：PAT A 1115，PAT A 1127

#### 知道树的结构求层次 ####

练习题：PAT A 1123

#### 已知中序后序求层次 ####

PAT A 1127  
变形：1064

#### 已知前序中序求后序 ####

练习题：PAT A 1138

#### 已知层序求后序 ####

练习题：PAT A 1147

#### 判断是否是完全二叉树 ####

练习题：PAT A 1110

### 中缀表达式 ###

PAT基本不考，但是会了给你数据结构老师长点面子。考研复试的最好准备一下，考了写不出来有点蛋疼。这也是经常跟迭代和递归一起考的，建议多找几题来练习练习。  
PAT A 1130

### 找共同祖先 ###

这个最好会一下，虽然可能性不大。但是这是对数据结构最起码的尊重…  
PAT A 1143，PAT A 1151

### 建树★★ ###

建树太复杂不咋考。考到也就是模板，会者就默，不会者弃。大家有空就看，没空放弃。看了反正估计也不考，考了没看也不亏…

#### 建AVL树 ####

练习题：PAT-A 1066，PAT A 1123

#### 建二叉搜索树 ####

练习题：PAT A 1115

### STL和数据结构★★★★★ ###

STL在PAT中会刻意考察，一般在第二题。题目不难，题意复杂，浪费时间多，看题目太长可以最后做。在考研上机中，会掺和到各种题目里面，用和不用都能做，但是可能牵扯到**空间**、**时间**和**解法简便性**的问题。建议做题前首先考虑用这个数据结构合不合适，可不可以把题解决掉。否则用了再换重新写很浪费时间。  
过程中涉及到**字符串与数字的转化**、**哈希存储**等方法。  
必须掌握的有：vector,set,map(unprdered\_map),queue(priority\_queue),stack。  
嵌套的数据结构考的不是很多。

### PAT专用题目★★★★ ###

题目非常长，输入非常多，从简单开始多练习。  
各种让你用数据结构**存储**、**排序**、**查找**和**输出**。最难到STL的运算符重载，会一道题即可。  
**值得写的一道考点非常全面的一题**：PAT A 1153  
这道无敌无敌无敌大题目，会了天下无敌，包括我上面描述的所有考点，涉及多种数据结构，也涉及到了STL运算符的重载。也是我考试的题目，我懒得写一遍了，太长了，大家自己研究查查答案吧。这题是我耗时最多的题，题目看完都20分钟过去了。

练习题：PAT A 1129，PAT A 1121，PAT A 1124，PAT A 1137，PAT A 1141，PAT A 1149

你若还不熟的其他练习题：PAT A 1012，PAT A 1016，PAT A 1022，PAT A 1025，PAT A 1028，PAT A 1039，PAT A 1047，PAT A 1054，PAT A 1055，PAT A 1062，PAT A 1063，PAT A 1071，PAT A 1075，PAT A 1080，PAT A 1083，PAT A 1100

### 数组、哈希和散列★★★ ###

专门考到的可能性不大，但是总是透露在各个题目之中。当你想不到合适简便的存储方法的时候不妨考虑下哈希吧！除此之外，也看下哈希存储的几种**避免冲突**的方法，这个可能让你**模拟先存后取算平均路径**。

哈希表：PAT A 1145  
练习题：PAT A 1048、PAT A 1050、PAT A 1092、PAT A 1084

### 链表★★ ###

链表你要是不会就有点说不过去了，把数据结构书上的掌握，考研涉及的题目用程序写出来，就差不多了。一般会考**查找**、**插入**、**删除**、**排序(原地反转)**、**查找共同的节点**等。想难得话也可以很难，那是故意考数学和逻辑的。总之基本的编程掌握，剩下的看脑子了。我这类题目没有专门看过，就网上挑了几个给大家看看。

练习题：PAT A 1032、PAT A 1052、PAT A 1074、PAT A 1097

### 队列和堆栈★★ ###

队列和堆栈更偏向于应用，要是专门考的话，应该也一眼就能看出来。队列可以夹在BFS和层次遍历里面练习。题目我就不找了，应该不难。

PS：**哈夫曼树**一个简单解决方法就是priority\_queue()，哈夫曼树的相关题目可以准备一下

### 动态规划★★★ ###

PAT中动态规划出现次数不是很多，即使考的话是基本模板题。考研上机中动态规划可能会作为压轴题出现，所以要多练习和体会。

### 最长不下降（上升）子序列★★★★★ ###

这是经典题目，可能会出变形，你认出来真面目即可。  
练习题：PAT A 1045  
经典变形：1045

### 最大连续子序列★★★★★ ###

经典。  
练习题：PAT A 1007

### 判断回文★★★ ###

经典的二维题目。  
练习题：PAT A 1040

### 贪心算法★★★ ###

练习题：PAT A 1125，PAT A 1033，PAT A 1037，PAT A 1038，PAT A 1067，PAT A 1070

### 0-1背包★★★ ###

练习题：PAT A 1068

### 排序和基本搜索★★★ ###

会数据结构书上的：二分搜索、快速排序、冒泡排序等。基本算法，这里不再提。  
考研上机必须作为基础题目。PAT的话感觉没咋考过…考的话应该也不难…总之想到了就不难…

### 堆排序★★★ ###

这个模块特地提一下堆排序，是重要且容易考的。  
堆的话，掌握两个点即可：**堆的建立、排序**。  
给大家一段参考代码，会了基本没什么问题。  
练习题： PAT A 1147，PAT A 1098

> /\*  
> 第一步：构建最小（大）堆  
> 第二步： 向下（上）调整 O(log\_2 n)  
> */  
> \#include  
> \#include  
> using namespace std;  
> \#define MAX 9  
> int a\[MAX+1\] = \{0,5,3,1,7,4,2,0,6,8\}; //后9个数排序  
> void swap(int x, int y)\{  
> int t = a\[x\];  
> a\[x\] = a\[y\];  
> a\[y\] = t;  
> \}  
> void adjustDown(int r, int n)\{  
> int child = 2*r;  
> int val = a\[r\];  
> while(child <= n)\{  
> if(child < n && a\[child\] > a\[child+1\]) child++;//选取孩子较小的那个  
> if(val < a\[child\]) break; //若父节点最小，则不需要调整  
> a\[child/2\] = a\[child\];  
> child \*= 2; //到下一层  
> \}  
> a\[child/2\] = val;  
> \}  
> int main()\{  
> /*建最小堆*/  
> for(int i = MAX/2; i > 0; i–)\{//从第一个非叶子节点开始  
> adjustDown(i, MAX);  
> \}  
> cout<<“建堆：”;  
> for(int i=1;i<=MAX;i++)\{  
> cout<<a\[i\]<<" “;  
> \}  
> cout<<endl;  
> /*排序*/  
> for(int i = MAX; i > 1; i–)\{  
> swap(1,i);  
> adjustDown(1,i-1);  
> \}  
> cout<<“排序：”;  
> for(int i = MAX;i > 0; i–)\{  
> cout<<a\[i\]<<” ";  
> \}  
> cout<<endl;  
> return 0;  
> \}

### 数学、逻辑、模拟、字符串、递归等★★★ ###

这个为啥放在一起讲呢，明明别的书都是分开讲的。因为剩下的都是基础，没有模板可套，考验脑子分析问题和建模能力。给你再多例题也白搭，到时候换个新的会做的人还是会做，不会做的人还是不会做。不过不用太紧张，这种题目一般放在第一题，作为简单题考查。编程能力够了之后就不用训练太多，但是了解一些经典题目和算法还是有必要的。给大家整理一些我碰到的。

#### 素数判断★ ####

素数判断有几种方法，请都掌握.  
练习题：PAT A 1116

#### 推公式的★ ####

练习题：PAT A 1104

#### 数位和★ ####

其实也可以看成字符串处理问题…  
练习题：PAT A 1120

#### 逻辑题★★ ####

螺旋矩阵问题：PAT A 1117，PAT A 1113，PAT A 1109  
8皇后问题：PAT A 1128  
回文：PAT A 1136，PAT A 1140，PAT A 1144

### 模拟★★★ ###

这个模拟啥的都有可能，其实就编程能力的问题。  
练习题：PAT A 1105

### 字符串处理★★★★ ###

一般专门考察会涉及到一个字符一个字符的处理的细节性问题，混在别的题目考的话是考输入、输出、转化等整体性的问题。  
自己看一下C++ string的用法，这个渗透于各个题目中。  
练习题：PAT A 1112，PAT A 1108，PAT A 1140

### 递归★★★ ###

单独考的话会跟数学一起考，考察建模、分析问题能力。经常和图什么的混在一起考。  
练习题：PAT A 1130，PAT A 1131

### 尺取法★★ ###

这个是自己想到的一种方法，后来发现有个学名叫“尺取法”…  
练习题：PAT A 1044

### 枚举★ ###

没办法就暴力呗…  
练习题：PAT A 1148

### 大数★ ###

都是很简单，其实可以看作是字符串处理。加减会做，乘除不用会；  
练习题：PAT A 1023，PAT A 1024

### 找出下一个排列★ ###

嗯…可以当作逻辑题自己推倒的，也不难，但是C++有封装好的方法给大家提示一下…我自从知道了之后就再也不自己推倒了…

> //最后一个排列没有下一个排列，用next\_permutation会返回false  
> \#include  
> \#include  
> \#include  
> \#define MAX 7  
> using namespace std;  
> int a\[MAX\] = \{2,1,4,7,6,3,5\};  
> vector v(a, a+MAX);  
> void shuchu()\{  
> for(int i=0;i<v.size();i++)\{  
> cout<<v\[i\]<<" ";  
> \}  
> cout<<endl;  
> \}  
> int main()\{  
> shuchu();  
> next\_permutation(v.begin(), v.end());  
> shuchu();  
> prev\_permutation(v.begin(), v.end());  
> shuchu();  
> return 0;  
> \}