GESP-C++四级考试核心知识点与编程模板

（5）结构体做函数参数：

void printStudent(const Student &s) { cout << s.name; } 

（6）const 使用场景：

传递函数参数时防止修改原结构体。

4. 函数（Function）

(1) 声明与定义：

int add(int a, int b); // 声明 int add(int a, int b) { return a + b; } // 定义 

(2) 调用：

int c = add(2,3); 

(3) 形参 & 实参：

形参：函数定义中的变量 实参：调用函数时传入的值

(4) 变量作用域：

局部变量：函数内部定义，仅函数内有效 全局变量：函数外定义，全局可访问

(5) 参数传递方式：

// 值传递 void f(int x) { x++; } // 引用传递 void f(int &x) { x++; } // 指针传递 void f(int *x) { (*x)++; } 

5. 递推算法（Recurrence / DP）

(1) 基本思想：

通过前面已知的结果推导后续结果

(2) 递推关系式：

f(n) = f(n-1) + f(n-2); 

(3) 例：斐波那契：

int fib(int n) { if(n<=2) return 1; return fib(n-1)+fib(n-2); } 

6. 排序算法

(1) 冒泡排序：

for(int i=0;i<n-1;i++) for(int j=0;j<n-1-i;j++) if(a[j]>a[j+1]) swap(a[j], a[j+1]); 

(2) 插入排序：

for(int i=1;i<n;i++){ int key=a[i], j=i-1; while(j>=0 && a[j]>key){ a[j+1]=a[j]; j--; } a[j+1]=key; } 

(3) 选择排序：

for(int i=0;i<n-1;i++){ int min_idx=i; for(int j=i+1;j<n;j++) if(a[j]<a[min_idx]) min_idx=j; swap(a[i],a[min_idx]); } 

(4) 算法分析：

• 时间复杂度：O(n²)
• 空间复杂度：O(1) 稳定性：

选择 → 不稳定 冒泡、插入 → 稳定

7. 文件操作

// 重定向输入输出 freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); // 文件读写 ofstream fout("data.txt"); fout << "Hello\n"; fout.close(); ifstream fin("data.txt"); string s; fin >> s; fin.close(); 

8. 异常处理

try { int x = 10/0; } catch(exception &e) { cout << "Error: " << e.what(); } 

二、GESP-C++ 考试四级编程题模板

1. 二维数组处理模板

#include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N][N]; int main() { int n,m; cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; // 示例操作：求二维数组元素和 int sum = 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum += a[i][j]; cout << sum << endl; return 0; }

2. 结构体数组排序模板

#include <bits/stdc++.h> using namespace std; struct Item { string name; int price; int priority; }; bool cmp(const Item &a, const Item &b) { if(a.priority != b.priority) return a.priority < b.priority; if(a.price != b.price) return a.price < b.price; return a.name < b.name; } int main() { int n; cin >> n; Item items[n]; for(int i=0;i<n;i++) cin >> items[i].name >> items[i].price >> items[i].priority; sort(items, items+n, cmp); for(int i=0;i<n;i++) cout << items[i].name << endl; return 0; }

3. 最大连续子序列/区间处理

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; int cnt=1, mx=1; for(int i=1;i<n;i++){ if(a[i]==a[i-1]+1) cnt++; else cnt=1; mx = max(mx, cnt); } cout << mx << endl; return 0; }

4. 二维矩阵最大矩形/子矩形

#include <bits/stdc++.h> using namespace std; const int N = 15; int a[N][N]; int main(){ int n,m; cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; int ans=0; for(int u=1;u<=n;u++) for(int l=1;l<=m;l++) for(int d=u;d<=n;d++){ int chk=1; for(int r=l;r<=m;r++){ for(int x=u;x<=d;x++) chk &= a[x][r]; if(!chk) break; ans = max(ans, (r-l+1)*(d-u+1)); } } cout << ans << endl; return 0; }

5. 矩阵/字符处理

#include <bits/stdc++.h> using namespace std; char s[105][105]; int main(){ int n,m; cin >> n >> m; for(int i=1;i<=n;i++) cin >> s[i]+1; // 输出子矩阵 int x1,x2,y1,y2; cin >> x1 >> x2 >> y1 >> y2; for(int i=x1;i<=x2;i++){ s[i][y2+1]=0; cout << s[i]+y1 << endl; } return 0; }

6. 常见遍历方向数组模板

const int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右 for(int k=0;k<4;k++){ int ni = i + d[k][0]; int nj = j + d[k][1]; }

7. 前缀和 / 子矩阵和模板

int sum[N][N]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j] = a[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]; // 区域和 int x1,y1,x2,y2; int ans = sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; 

8. 排序 + 条件统计模板

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; sort(a.begin(), a.end()); int ans=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(a[i]<a[j]) ans++; cout << ans << endl; }

三、C++ 四级考前快速复习汇总表

1. 基础知识点

2. 算法复杂度

四、CCF GESP 四级 C++ 编程题模板库（速查表）

1. 数组/二维数组基础模板

1、一维数组输入/输出

int a[N], n; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) cout << a[i] << " "; 

解析：

• 考场常用输入 n 个数并输出。
• 下标可从 1 或 0 开始。

2、二维数组输入/输出

int a[N][N], n, m; cin >> n >> m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin >> a[i][j]; 

解析：

• 适合矩阵处理题，如最大子矩形、子矩阵和。
• 可以与 前缀和/子矩阵计算 模板结合。

2. 排序模板

1、冒泡排序（可指定区间）

void bubbleSort(int *a, int l, int r){ bool flag = true; while(flag){ flag = false; for(int i=l;i<r;i++){ if(a[i] > a[i+1]){ swap(a[i], a[i+1]); flag = true; } } } }

解析：

• 可对数组部分区间排序。
• 小规模 n ≤ 1000 时可用。

2、STL 排序（数组）

（1）数组排序：下标从 0 开始

int a[10]; int n = 10; sort(a, a+n); // 排序 a[0] ~ a[9] 

• 这是 C++ 默认习惯，也是 STL 容器的标准索引方式

（2）数组排序：下标从 1 开始（考试常用）

int a[110]; int n; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; sort(a+1, a+n+1); // 排序 a[1] ~ a[n] 

• a+1 指向 a[1]
• a+n+1 是 开区间右端点，所以最后会排序到 a[n]

（3）总结：

数组排序 从 0 开始 → sort(a, a+n) 数组排序 从 1 开始 → sort(a+1, a+n+1)

3、STL 排序（vector）

vector<int> v; sort(v.begin(), v.end()); 

vector 下标一定是 0 开始.begin() 指向第一个元素.end() 指向最后元素之后的位置（开区间）不需要加 +1，直接用 .begin(), .end()

3. 矩阵/子矩阵处理模板

1、检查固定子矩阵匹配（2024 年 9 月编程题第一题）

bool check(int xa,int ya){ for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(w[xa+i][ya+j]!=match[i][j]) return false; return true; }

• 适合 4x4 或固定大小图形匹配题。

2、可变大小矩形检查（2024 年 6 月第一题）

bool check(int xa,int ya,int xb,int yb){ int cnt[2]={0}; for(int i=xa;i<=xb;i++) for(int j=ya;j<=yb;j++) cnt[w[i][j]]++; return cnt[0]==cnt[1]; }

• 适合统计矩形中某些条件数量。
• 可结合 暴力枚举 或 前缀和优化。

3、最大子矩形（2024 年 6 月第一题）

int ans = 0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int ii=i;ii<=n;ii++) for(int jj=j;jj<=m;jj++) if(check(i,j,ii,jj)) ans = max(ans,(ii-i+1)*(jj-j+1)); cout << ans << "\n"; 

• 使用暴力枚举查找满足条件的最大矩形。

4. 递推/构造序列模板

1、构造特殊序列（2024 年 12 月第一题）

a[1]=1; vis[1]=1; for(int i=2;i<=n;i++){ if(a[i-1]-i<=0 || vis[a[i-1]-i]) a[i]=a[i-1]+i; else a[i]=a[i-1]-i; vis[a[i]]=1; } sort(a+1,a+n+1); 

2、分析：

用于生成满足约束的序列。vis[] 用于记录已使用数字。

5. 滑动/区间和子数组模板

1、最大区间和/和满足条件的子序列（2024 年 6 月第二题）

sort(a+1,a+n+1); int ans=0; for(int i=1;i<=n;i++){ int sum=0; for(int j=i;j>=1;j--){ if(a[i]-a[j]<=k) sum+=a[j]; else break; } ans = max(ans,sum); } cout << ans << "\n"; 

2、分析：

用于 连续/可滑动窗口求和。常见题型：限制差值 k 的最大和。

6. 排序 + 贪心/统计模板

6.1 贪心匹配/计数（2024 年 3 月第二题）

sort(a+1,a+n+1); int ans=0,s=1; for(int j=1;j<=m;j++) for(int k=s;k<=n;k++){ if(j<=a[k]){ ans++; a[k]=j; s=k; break; } } cout << ans; 

2、分析：

贪心选择最小可行元素。常见题型：分配/匹配问题。

7. 字符串相似性判断模板

1、判断是否相似（2024 年 3 月第一题）

bool isSimilar(string A,string B){ int m=A.size(), n=B.size(); if(abs(m-n)>1) return false; if(m==n){ int diff=0; for(int i=0;i<m;i++) if(A[i]!=B[i]) if(++diff>1) return false; return true; } else { string &shorter=(m<n?A:B), &longer=(m<n?B:A); int i=0,j=0,diff=0; while(i<shorter.size() && j<longer.size()){ if(shorter[i]!=longer[j]){ if(++diff>1) return false; ++j; } else { ++i; ++j; } } return true; } }

2、分析：

用于检查两个字符串是否最多相差一个字符。可扩展到字符串编辑距离问题。

8. 字符串排序 + 合并检查模板

1、字典序排序 + 合并（2024 年 12 月第二题）

sort(s+1,s+n+1); string; for(int i=1;i<=n;i++) combined += s[i]; bool ok=true; for(int i=1;i<combined.size();i++) if(combined[i]<combined[i-1]) ok=false; cout << ok << "\n"; 

2、分析：

适合题型：多字符串排序后检查整体非下降。可以用 STL sort。

9. 四级考试需要掌握编程知识点

1. 数组/矩阵模板 → 矩阵最大子矩形、子矩阵和
2. 排序模板 → 冒泡、STL、区间排序、字符串排序
3. 递推/构造模板 → 特殊序列生成
4. 贪心/滑动窗口 → 区间和、最大和、分配匹配
5. 字符串模板 → 相似性判断、字典序排序、合并检查
6. 暴力枚举 + check → 小规模矩阵/子矩形统计问题