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 combined;
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 → 小规模矩阵/子矩形统计问题