PAT甲级考前整理之一网址：https://www.cnblogs.com/jlyg/p/7525244.html，主要总结了前面131题的类型以及易错题及坑点。
PAT甲级考前整理三网址：https://www.cnblogs.com/jlyg/p/10364727.html主要是讲132题开始的题目。
考前注意：
1、写函数（有返回值的函数）容易忘记返回值，可能本地运行没问题，但是提交了就会有问题。
2、不要把strlen()函数写到for、while的循环中，有时候会超时，最好是 int len = strlen(str);提前求出来。
3、用sort比较的时候，比较函数 int comp(const ST& st1,const ST& st2);如果在comp中调用ST的fun函数，fun函数必须加上const,例子 int fun()const{return 0;}
4、二位数组初始化不要直接赋值，比如int a[10][10] ={0}，是错误的，应该使用memset(a,0,sizeof(a));（一维数组也最好不要直接复制，通过循环复制最好）
5、不要使用gets，PAT系统不支持。可以使用fprintf,使用fprintf注意最后一个字符是‘\n‘,特别是比较的时候就不相等了
6、使用freopen("1.txt","r",stdin);来减少测试的时间。
7、输出时注意单复数，比如单数是a、is，复数是加s、are。
8、不要还没输入完就用break跳出，不然会有问题，具体可以看我以下代码和代码中的注释，例题PAT1122
View Code9、输出id和编号的时候，如果你存储是数字，请加上前面补足比如4位整型，%04d，用%d的时候就有问题了，比如0001输出就是1。
STL总结：
1.vector
#include<iostream> #include<cstdio> #include<vector> using namespace std; void display(vector<int> vi) { for(int i=0;i<vi.size();++i) printf("%d ",vi[i]); printf("\n"); } int main() { vector<int> vi; vi.push_back(1); vi.push_back(3); display(vi); //插入 vi.insert(vi.begin()+1,2); display(vi); //删除 vi.erase(vi.begin()+2); display(vi); //清空 vi.clear(); return 0; }
2.queue与priority_queue
#include<iostream> #include<queue> #include<vector> #include<cstdio> using namespace std; int main() { //优先队列会自动排序 priority_queue<int,vector<int>,greater<int> >pq; pq.push(3); pq.push(2); pq.push(1); while(!pq.empty()) { //queue的话是front函数 int data = pq.top(); pq.pop(); printf("%d ",data); } printf("\n"); return 0; }
3.map
#include<iostream> #include<cstdio> #include<map> using namespace std; int main() { map<int,int> mii; mii.insert(pair<int,int>(1,1)); mii[2] = 2; printf("删除前：%d\n",mii[2]); //删除key=2的值 mii.erase(2); printf("删除后：%d\n",mii[2]); return 0; }
4.string
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; int main() { char str[] = "hello world"; string s(str); printf("%s\n",s.c_str()); int index = s.find(‘ ‘); string s2 = s.substr(0,index); string s3 = s.substr(index+1,s.length()-index-1); printf("%s\n%s\n",s2.c_str(),s3.c_str()); //字符串追加 string newstr = ""; newstr += s2; newstr += "-"; newstr += s3; printf("%s\n",newstr.c_str()); //字符串比较 s2 = "aabc",s3="aacc"; printf("%d\n",s2.compare(s3)); }
5.set
#include<iostream> #include<cstdio> #include<set> #include<algorithm> using namespace std; void display(char* str,set<int> si) { printf("%s: ",str); set<int>::iterator it = si.begin(); for(;it != si.end();it++) printf("%d ",*it); printf("\n"); } int main() { set<int> s1; set<int> s2; s1.insert(1); s1.insert(2); s1.insert(3); s2.insert(3); s2.insert(4); s2.insert(5); s2.insert(6); display("s1",s1); display("s2",s2); //erase的参数是key s2.erase(6); display("s2",s2); set<int> s3,s4; //交集 set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s3,s3.begin())); //并集 set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(s4,s4.begin())); display("交集",s3); display("并集",s4); return 0; }
一些树的算法：
如何判断一颗树是完全二叉树，例题可以看PAT1123，可以用一个队列，每次加入一个节点的左右节点，并且pop出该节点，如果该节点为空，则跳出循环，如果该树是完全二叉树，则队列中应该都是null，如果存在非空，就说明不是完全二叉树
bool isCBT(Node* root)
{
queue<Node*> q;
q.push(root);
Node* node;
while(node=q.front())
{
q.push(node->left);
q.push(node->right);
q.pop();
}
while(!q.empty())
{
if(q.front()) return false;
else q.pop();
}
return true;
}
二叉树的层级遍历（非递归）
bool bFirst = true;
void level_travel(Node* root)
{
queue<Node*> q;
q.push(root);
Node* node;
while(node=q.front())
{
if(bFirst) bFirst = false;
else printf(" ");
printf("%d",node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
q.pop();
}
}
判断图是否遍历所有点以下是错误的例子（PAT1126）
void dfs(int curI,int istep)
{
if(istep==n)
{
flag = true;
return;
}
for(int nextI=1;nextI<=n;++nextI)
{
if(Map[curI][nextI]&&!bVis[nextI])
{
bVis[nextI] = true;
dfs(nextI,istep+1);
}
}
}
如 图
1
3 2 4
从2节点遍历，1,3,4，它的step为2
应该用以下判断：判断sum是否等于顶点个数。
int sum=0;
void dfs(int curI,int istep)
{
++sum;
for(int nextI=1;nextI<=n;++nextI)
{
if(Map[curI][nextI]&&!bVis[nextI])
{
bVis[nextI] = true;
dfs(nextI,istep+1);
}
}
}
二叉树的遍历可以看https://www.cnblogs.com/jlyg/p/10354622.html，主要整理了几种二叉树遍历的类型，如已知中序和前序求后序？已知前序和后序求中序？已知中序完全二叉树求广度？已知先序的搜索二叉树求后序？
有时间可以看一下AVL树的模板：https://www.cnblogs.com/jlyg/p/7521434.html
其他：
Dijkstra模板：https://www.cnblogs.com/jlyg/p/7404082.html
并查集的例题：https://www.cnblogs.com/jlyg/p/7356992.html
DFS和BFS肯定是要必会的，这里就不多讲了。
PAT甲级考前整理（2019年3月备考）之二，持续更新中.....
原文：https://www.cnblogs.com/jlyg/p/10364696.html