C++二级GESP 全考点详细解析

1.1.3 常见错误

• 忘记写main()函数：程序无法编译。
• main()函数返回非int类型（如void main()）：不符合C++标准（部分编译器支持但不推荐）。
• 头文件未包含（如未写#include <iostream>却使用cout）：编译报错'找不到标识符'。

1.2 数据类型与变量

1.2.1 基本数据类型

C++的基本数据类型可分为整型、浮点型、字符型、布尔型四类，具体如下表：

注意：实际存储空间可能因编译器/系统不同略有差异（如32位与64位系统的long类型）。

1.2.2 变量与常量

• 变量：内存中可修改的存储单元，需先声明后使用，格式为类型名 变量名 [= 初始值];。
  示例：int age = 18;（声明一个整型变量age并初始化为18）。
• 常量：内存中不可修改的值，常用const关键字声明，格式为const 类型名 常量名 = 初始值;。
  示例：const double PI = 3.14159;（声明一个双精度常量PI）。

1.2.3 类型转换

• 隐式转换（自动转换）：由编译器自动完成，遵循'低精度→高精度'原则。
  示例：int a = 5; double b = a;（int转double，值为5.0）。
• 显式转换（强制转换）：手动指定转换类型，格式为(目标类型) 表达式或目标类型(表达式)。
  示例：double c = 3.14; int d = (int)c;（double转int，值为3，截断小数部分）。

1.2.4 易错点

• 变量未初始化直接使用：可能导致不可预测的结果（如int x; cout << x;）。
• 字符型变量的赋值：需用单引号' '（如char ch = 'A';），双引号会导致字符串（如char ch = "A";会报错）。
• 浮点型精度问题：double计算可能存在微小误差（如0.1 + 0.2可能不等于0.3）。

1.3 运算符与表达式

1.3.1 算术运算符

包括+（加）、-（减）、*（乘）、/（除）、%（取余）、++（自增）、--（自减）。

注意：

• /对整型操作数执行整除（如7/2=3），对浮点型执行普通除法（如7.0/2=3.5）。
• %仅适用于整型（如7%2=1），且操作数不能为负数（不同编译器处理方式可能不同）。
• 自增/自减运算符的位置影响优先级：a++（先使用a再自增） vs ++a（先自增再使用a）。

1.3.2 关系与逻辑运算符

• 关系运算符：==（等于）、!=（不等于）、>（大于）、<（小于）、>=（大于等于）、<=（小于等于），结果为bool类型（true或false）。
• 逻辑运算符：&&（逻辑与，同真为真）、||（逻辑或，有真为真）、!（逻辑非，取反）。

短路特性：

• &&左边为false时，右边不再计算（如false && (a=5)不会修改a）。
• ||左边为true时，右边不再计算（如true || (a=5)不会修改a）。

1.3.3 赋值与优先级

• 赋值运算符：=（基本赋值）、+=（加后赋值）、-=（减后赋值）等，如a += 3等价于a = a + 3。
• 运算符优先级：需牢记（可参考C++运算符优先级表），必要时用括号明确顺序（如(a + b) * c vs a + b * c）。

1.4 输入与输出

C++的输入输出通过iostream库实现，使用cout（输出）和cin（输入）对象，配合流插入符<<和流提取符>>。

1.4.1 输出（cout）

• 基本格式：cout << 表达式1 << 表达式2 << ... ;
• 换行：endl（输出换行并刷新缓冲区）或\n（仅换行）。
• 格式化输出：通过iomanip库中的函数（如setw()设置宽度、setprecision()设置小数位数）。

示例：

#include <iostream>
#include <iomanip> // 需包含格式化头文件
using namespace std;

int main() {
    int num = 123;
    double pi = 3.1415926;
    cout << "整数：" << num << endl; // 输出：整数：123
    cout << "浮点数（默认6位）：" << pi << endl; // 输出：浮点数（默认6位）：3.14159
    cout << "浮点数（保留2位）：" << fixed << setprecision(2) << pi << endl; // 输出：浮点数（保留2位）：3.14
    cout << "宽度为10，右对齐：" << setw(10) << num << endl; // 输出：宽度为10，右对齐： 123（前面有7个空格）
    return 0;
}

1.4.2 输入（cin）

• 基本格式：cin >> 变量1 >> 变量2 >> ... ;
• 输入类型需与变量类型匹配（否则可能导致错误）。

示例：

int a, b;
cout << "请输入两个整数：";
cin >> a >> b; // 输入时用空格或换行分隔
cout << "和为：" << a + b << endl;

第二章 流程控制

流程控制是程序根据条件或循环执行不同代码块的机制，GESP二级重点考察顺序结构、选择结构、循环结构三大类。

2.1 顺序结构

程序默认按代码编写顺序逐条执行，是最基本的流程控制。

2.2 选择结构（分支语句）

选择结构根据条件判断决定执行哪段代码，包括if语句和switch语句。

2.2.1 if语句

if语句有三种形式：单分支、双分支、多分支。

语法格式：

// 单分支：条件成立时执行代码块
if (条件表达式) {
    代码块 1;
}

// 双分支：条件成立执行代码块 1，否则执行代码块 2
if (条件表达式) {
    代码块 1;
} else {
    代码块 2;
}

// 多分支：按顺序判断条件，执行第一个成立的分支
if (条件 1) {
    代码块 1;
} else if (条件 2) {
    代码块 2;
} else {
    代码块 3; // 所有条件不成立时执行
}

示例：判断成绩等级

int score;
cout << "请输入成绩（0-100）：";
cin >> score;
if (score >= 90) {
    cout << "优秀" << endl;
} else if (score >= 80) {
    cout << "良好" << endl;
} else if (score >= 60) {
    cout << "及格" << endl;
} else {
    cout << "不及格" << endl;
}

易错点：

• 条件表达式需用括号()包裹（即使只有一条语句）。
• else必须与前一个未匹配的if配对，避免逻辑错误。

2.2.2 switch语句

switch语句用于多分支选择，条件必须是整型或枚举类型（C++17支持字符串字面量，但二级考试中通常为整型）。

语法格式：

switch (表达式) {
case 常量 1:
    代码块 1;
    break; // 跳出 switch，避免穿透
case 常量 2:
    代码块 2;
    break;
default: // 所有 case 不匹配时执行
    代码块 3;
}

示例：判断星期几

int day;
cout << "请输入星期（1-7）：";
cin >> day;
switch (day) {
case 1:
    cout << "星期一" << endl;
    break;
case 2:
    cout << "星期二" << endl;
    break;
case 3:
    cout << "星期三" << endl;
    break;
case 4:
    cout << "星期四" << endl;
    break;
case 5:
    cout << "星期五" << endl;
    break;
case 6:
    cout << "星期六" << endl;
    break;
case 7:
    cout << "星期日" << endl;
    break;
default:
    cout << "输入错误" << endl;
}

注意：

• case后的常量必须唯一且与switch表达式类型一致。
• 若省略break，会发生'穿透'（执行下一个case的代码），需谨慎使用（如多条件共享代码块时）。

2.3 循环结构

循环结构用于重复执行某段代码，直到条件不满足。GESP二级重点考察for、while、do-while三种循环，以及循环嵌套、break和continue的使用。

2.3.1 for循环

for循环适用于已知循环次数或明确终止条件的场景。

语法格式：

for (初始化表达式; 条件表达式; 更新表达式) {
    循环体;
}

执行流程：

1. 执行初始化表达式（仅执行一次）。
2. 判断条件表达式：若为true，执行循环体；若为false，退出循环。
3. 执行更新表达式（如i++），回到步骤 2。

示例：计算 1 到 100 的和

int sum = 0;
for (int i = 1; i <= 100; i++) {
    sum += i;
}
cout << "1 到 100 的和为：" << sum << endl; // 输出：5050

2.3.2 while循环

while循环适用于未知循环次数，仅知道终止条件的场景。

语法格式：

初始化表达式;
while (条件表达式) {
    循环体;
    更新表达式;
}

执行流程：

1. 执行初始化表达式。
2. 判断条件表达式：若为true，执行循环体；否则退出。
3. 执行循环体和更新表达式，回到步骤 2。

示例：打印 1 到 10 的偶数

int i = 1;
while (i <= 10) {
    if (i % 2 == 0) {
        cout << i << " ";
    }
    i++;
}
// 输出：2 4 6 8 10

2.3.3 do-while循环

do-while循环与while类似，但至少执行一次循环体（先执行后判断）。

语法格式：

初始化表达式;
do {
    循环体;
    更新表达式;
} while (条件表达式);

示例：用户输入验证（确保输入正数）

int num;
do {
    cout << "请输入一个正数：";
    cin >> num;
} while (num <= 0); // 若输入非正数，重复输入
cout << "你输入的正数是：" << num << endl;

2.3.4 循环嵌套

循环内部包含另一个或多个循环，称为循环嵌套。外层循环每执行一次，内层循环执行全部次数。

示例：打印金字塔（5 层）

for (int i = 1; i <= 5; i++) { // 控制层数（1-5 层）
    for (int j = 1; j <= 5 - i; j++) { // 打印空格（每层前导空格数为 5-i）
        cout << " ";
    }
    for (int k = 1; k <= 2 * i - 1; k++) { // 打印星号（每层星号数为 2i-1）
        cout << "*";
    }
    cout << endl; // 每层结束后换行
}

输出结果：

 *
 ***
 *****
*******
*********

2.3.5 break与continue

• break：终止当前所在的最内层循环，跳出循环体。
• continue：跳过当前循环体的剩余代码，直接进入下一次循环的条件判断。

示例：寻找 100 以内的第一个素数

bool isPrime = true;
for (int i = 2; i <= 100; i++) {
    for (int j = 2; j < i; j++) {
        if (i % j == 0) { // 发现因子，不是素数
            isPrime = false;
            break; // 终止内层循环
        }
    }
    if (isPrime) {
        cout << "100 以内第一个素数是：" << i << endl;
        break; // 终止外层循环
    } else {
        isPrime = true; // 重置标志，检查下一个数
    }
}

2.4 程序阅读与填空（真题示例）

题目 1：以下代码的输出结果是？

int i = 1;
while (i <= 5) {
    cout << i * 2 << " ";
    i += 2;
}

答案：2 4 6 8 10

题目 2：补全代码，计算 1 到 n 的和（n 由用户输入）。

int n, sum = 0;
cin >> n;
for (i = 1; i <= n; i++) {
    sum += i;
}
cout << sum << endl;

答案：for；i++

第三章 数组与字符串

数组是存储同类型数据的连续内存空间，用于批量处理数据。字符串是字符数组的特殊应用（以\0结尾）。

3.1 一维数组

3.1.1 定义与初始化

语法格式：类型名 数组名 [长度];（长度必须是常量表达式，C++11 支持constexpr或auto推导）。

初始化方式：

• 完全初始化：int arr[5] = {1, 2, 3, 4, 5};（指定所有元素）。
• 不完全初始化：int arr[5] = {1, 2};（前两个元素为 1、2，其余为 0）。
• 省略长度：int arr[] = {1, 2, 3};（长度由初始化列表推导为 3）。

3.1.2 访问与遍历

通过下标访问元素（下标从 0 开始），遍历通常用循环实现。

示例：遍历数组并求最大值

int arr[5] = {3, 7, 2, 9, 4};
int maxVal = arr[0]; // 初始化为第一个元素
for (int i = 1; i < 5; i++) {
    if (arr[i] > maxVal) {
        maxVal = arr[i];
    }
}
cout << "最大值：" << maxVal << endl; // 输出：9

3.2 二维数组

3.2.1 定义与初始化

二维数组是'数组的数组'，语法为类型名 数组名 [行数][列数];。

初始化方式：

• 按行初始化：int matrix[2][3] = {{1,2,3}, {4,5,6}};（2 行 3 列）。
• 省略行数：int matrix[][3] = {{1,2}, {3,4}, {5,6}};（行数由初始化列表推导为 3）。

3.2.2 访问与遍历

通过[行下标][列下标]访问元素（下标均从 0 开始），遍历需嵌套循环（外层控制行，内层控制列）。

示例：打印二维数组

int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        cout << matrix[i][j] << " ";
    }
    cout << endl;
}

输出结果：

1 2 3
4 5 6
7 8 9

3.3 字符串处理

C++中的字符串有两种表示方式：C风格字符串（字符数组）和string类（需包含<string>头文件）。二级考试重点考察C风格字符串。

3.3.1 C风格字符串

• 定义：char str[] = "hello";（本质是字符数组，末尾自动添加\0作为结束标志）。
• 输入输出：用cin（遇空格停止）或getline(cin, str)（读取整行，包括空格）。

示例：读取整行字符串

char str[100];
cout << "请输入一句话：";
cin.getline(str, 100); // 第二个参数是数组长度，防止溢出
cout << "你输入的是：" << str << endl;

3.3.2 常用字符串操作

• 获取长度：strlen(str)（需包含<cstring>头文件）。
• 复制字符串：strcpy(dest, src)（将src复制到dest）。
• 连接字符串：strcat(dest, src)（将src追加到dest末尾）。
• 比较字符串：strcmp(str1, str2)（返回 0 表示相等，正数表示str1>str2，负数相反）。

示例：字符串拼接

#include <cstring>
char str1[20] = "Hello";
char str2[20] = "World";
strcat(str1, " "); // str1变为"Hello "
strcat(str1, str2); // str1变为"Hello World"
cout << str1 << endl;

3.4 程序阅读与填空（真题示例）

题目 1：以下代码的输出结果是？

int arr[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
cout << arr[1][2] << endl;

答案：6（行下标 1 对应第二行，列下标 2 对应第三列）。

题目 2：补全代码，输入一个字符串，统计其中数字字符的个数。

char str[100];
int count = 0;
cin.getline(str, 100);
for (int i = 0; str[i] != '\0'; i++) {
    if (str[i] >= '0' && str[i] <= '9') {
        count++;
    }
}
cout << "数字个数：" << count << endl;

第四章 函数

函数是封装代码块的模块，用于实现特定功能，提高代码复用性。GESP二级重点考察函数的定义、调用、参数传递与递归。

4.1 函数的基本概念

4.1.1 函数的定义与声明

• 定义：包含函数类型、名称、参数列表和函数体。
  语法：返回类型 函数名 (参数列表) { 函数体; return 返回值; }（void类型无需return）。
• 声明：在调用函数前告知编译器函数的类型和参数（避免编译错误），格式与定义的头部相同，以分号结尾。

示例：

// 函数声明（可在头文件或调用前）
int add(int a, int b);

// 主函数
int main() {
    int sum = add(3, 5); // 调用函数
    cout << sum << endl;
    return 0;
}

// 函数定义
int add(int a, int b) {
    return a + b;
}

4.2 参数传递

函数参数分为形参（形式参数）和实参（实际参数）。C++中参数传递默认是值传递（拷贝实参的值给形参，修改形参不影响实参）。

4.2.1 值传递

形参是实参的副本，函数内对形参的修改不会影响实参。

示例：

void swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

int main() {
    int x = 1, y = 2;
    swap(x, y); // 调用后 x=1，y=2（未改变）
    cout << x << " " << y << endl;
    return 0;
}

4.2.2 引用传递（扩展）

引用是变量的别名（C++特有），通过引用传递（&符号），函数内对形参的修改会影响实参。

示例：

void swap(int &a, int &b) { // 形参是引用
    int temp = a;
    a = b;
    b = temp;
}

int main() {
    int x = 1, y = 2;
    swap(x, y); // 调用后 x=2，y=1（已交换）
    cout << x << " " << y << endl;
    return 0;
}

4.3 函数的嵌套与递归

4.3.1 嵌套调用

函数 A 调用函数 B，函数 B 调用函数 C，称为嵌套调用。

示例：计算阶乘的阶乘（(3!)!)

int factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    return n * factorial(n - 1);
}

int main() {
    int result = factorial(factorial(3)); // factorial(3)=6，factorial(6)=720
    cout << result << endl; // 输出：720
    return 0;
}

4.3.2 递归函数

递归是指函数在其定义中直接或间接调用自身，需满足终止条件和递归步骤。

示例：计算斐波那契数列第 n 项（F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)）

int fib(int n) {
    if (n == 1 || n == 2)
        return 1; // 终止条件
    return fib(n - 1) + fib(n - 2); // 递归步骤
}

int main() {
    cout << "斐波那契第 5 项：" << fib(5) << endl; // 输出：5（1,1,2,3,5）
    return 0;
}

4.4 局部变量与全局变量

• 局部变量：在函数或代码块内定义的变量，仅在作用域内有效。
• 全局变量：在函数外定义的变量，整个程序均可访问（建议少用，可能导致命名冲突）。

示例：

int global = 10; // 全局变量

void func() {
    int local = 20; // 局部变量
    cout << "全局变量：" << global << endl; // 输出：10
    cout << "局部变量：" << local << endl; // 输出：20
}

int main() {
    func();
    // cout << local << endl; // 报错：local 是 func 的局部变量，此处不可见
    return 0;
}

4.5 程序阅读与填空（真题示例）

题目 1：以下代码的输出结果是？

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

int main() {
    cout << f(6) << endl;
    return 0;
}

答案：8（斐波那契数列第 6 项：1,1,2,3,5,8）。

题目 2：补全代码，用递归计算 n 的 k 次方（n^k）。

int power(int n, int k) {
    if (k == 0)
        return 1; // 任何数的 0 次方为 1
    return n * power(n, k - 1); // 递归：n^k = n * n^(k-1)
}

第五章 结构体

结构体（struct）是用户自定义的数据类型，用于将不同类型的数据组合成一个整体（如学生信息、商品属性）。

5.1 结构体的定义与使用

5.1.1 结构体的定义

语法格式：

struct 结构体名 {
    类型 1 成员名 1;
    类型 2 成员名 2;
    // ... 其他成员
};

示例：定义学生结构体

struct Student {
    char name[20]; // 姓名（字符数组）
    int age;       // 年龄
    double score;  // 分数
};

5.1.2 结构体变量的声明与初始化

• 声明：结构体名 变量名;（如Student stu1;）。
• 初始化：按成员顺序初始化（C++11 支持指定成员初始化）。

示例：

// 方式 1：逐个赋值
Student stu1;
strcpy(stu1.name, "张三"); // 字符数组需用 strcpy 赋值
stu1.age = 18;
stu1.score = 90.5;

// 方式 2：初始化列表（C++11）
Student stu2 = {"李四", 17, 95.0};

5.1.3 结构体数组与作为函数参数

• 结构体数组：存储多个同类型结构体变量的数组。
  示例：Student class1[30];（存储 30 名学生的信息）。
• 作为函数参数：可将结构体变量或数组作为参数传递（值传递或引用传递）。

示例：打印学生信息

void printStudent(Student s) {
    cout << "姓名：" << s.name << "，年龄：" << s.age << "，分数：" << s.score << endl;
}

int main() {
    Student stu = {"王五", 19, 88.5};
    printStudent(stu); // 传递结构体变量
    return 0;
}

5.2 程序阅读与填空（真题示例）

题目 1：以下代码的输出结果是？

struct Point {
    int x;
    int y;
};

int main() {
    Point p = {3, 5};
    cout << p.x + p.y << endl;
    return 0;
}

答案：8（3+5=8）。

题目 2：补全代码，定义一个结构体Book（包含书名title（字符数组）、价格price（double）），并声明一个变量book1初始化为{"C++入门", 49.9}。

struct Book {
    char title[50];
    double price;
};
Book book1 = {"C++入门", 49.9};

第六章 文件操作

文件操作用于将数据持久化存储到磁盘（如保存用户信息、读取配置文件）。GESP二级重点考察文件的打开、读写与关闭。

6.1 文件的基本操作

6.1.1 文件的打开与关闭

使用fstream库中的ifstream（输入文件流，读文件）、ofstream（输出文件流，写文件）、fstream（读写文件）类。

步骤：

1. 包含头文件：#include <fstream>。
2. 创建文件流对象：ifstream inFile;（读）、ofstream outFile;（写）。
3. 打开文件：对象.open("文件名", 模式);（模式常用ios::in（读）、ios::out（写）、ios::app（追加）、ios::binary（二进制））。
4. 判断是否打开成功：if (!对象.is_open()) { 错误处理; }。
5. 关闭文件：对象.close();。

6.1.2 文件的读写

• 文本模式：以字符形式读写（自动转换换行符，如Windows的\r\n转Linux的\n）。
• 二进制模式：以字节形式读写（保留原始数据，适合图片、视频等）。

6.2 文本文件的读写

6.2.1 写文本文件（ofstream）

使用<<运算符或fprintf函数（类似cout）。

示例：保存学生信息到文本文件

#include <fstream>
#include <string>
using namespace std;

int main() {
    ofstream outFile("students.txt", ios::out); // 打开文件（覆盖模式）
    if (!outFile.is_open()) {
        cout << "文件打开失败！" << endl;
        return 1;
    }
    // 写入数据
    outFile << "姓名\t年龄\t分数" << endl; // 表头
    outFile << "张三\t18\t90.5" << endl;
    outFile << "李四\t17\t95.0" << endl;
    outFile.close(); // 关闭文件
    cout << "文件写入成功！" << endl;
    return 0;
}

6.2.2 读文本文件（ifstream）

使用>>运算符（按空格分隔）或getline函数（按行读取）。

示例：读取学生信息并输出

#include <fstream>
#include <iostream>
#include <string>
using namespace std;

int main() {
    ifstream inFile("students.txt", ios::in); // 打开文件（读模式）
    if (!inFile.is_open()) {
        cout << "文件打开失败！" << endl;
        return 1;
    }
    string line;
    while (getline(inFile, line)) { // 按行读取
        cout << line << endl;
    }
    inFile.close();
    return 0;
}

6.3 二进制文件的读写

二进制文件直接存储数据的二进制形式，效率高，适合存储结构体等复杂类型。

6.3.1 写二进制文件（ofstream）

使用write方法，参数为数据指针和字节数（sizeof(类型)）。

示例：保存学生结构体到二进制文件

#include <fstream>
using namespace std;

struct Student {
    char name[20];
    int age;
    double score;
};

int main() {
    Student stu = {"张三", 18, 90.5};
    ofstream outFile("student.bin", ios::out | ios::binary); // 二进制写模式
    outFile.write((char*)&stu, sizeof(Student)); // 强制转换为 char*指针
    outFile.close();
    cout << "二进制文件写入成功！" << endl;
    return 0;
}

6.3.2 读二进制文件（ifstream）

使用read方法，参数为目标地址和字节数。

示例：从二进制文件读取学生信息

#include <fstream>
#include <iostream>
using namespace std;

struct Student {
    char name[20];
    int age;
    double score;
};

int main() {
    Student stu;
    ifstream inFile("student.bin", ios::in | ios::binary); // 二进制读模式
    inFile.read((char*)&stu, sizeof(Student));
    cout << "姓名：" << stu.name << "，年龄：" << stu.age << "，分数：" << stu.score << endl;
    inFile.close();
    return 0;
}

6.4 程序阅读与填空（真题示例）

题目 1：以下代码的功能是？

#include <fstream>
int main() {
    ofstream f("test.txt");
    f << "Hello GESP";
    f.close();
    return 0;
}

答案：创建一个名为test.txt的文本文件，并写入字符串"Hello GESP"。

题目 2：补全代码，从二进制文件data.bin中读取一个整数（假设文件中仅存储一个整数）。

#include <fstream>
int main() {
    ifstream inFile("data.bin", ios::in | ios::binary);
    int num;
    inFile.read((char*)&num, sizeof(int));
    inFile.close();
    cout << num << endl;
    return 0;
}

第七章 基础算法（GESP二级重点）

GESP二级算法部分主要考察排序算法（冒泡、选择、插入）和查找算法（顺序、二分），需理解思想、掌握实现并分析时间复杂度。

7.1 排序算法

排序是将数据按特定顺序（升序/降序）排列的过程。

7.1.1 冒泡排序（Bubble Sort）

思想：相邻元素比较，大的往后移（升序），每轮将最大的元素'冒泡'到末尾。
步骤：

1. 外层循环控制轮数（n-1轮，n为数组长度）。
2. 内层循环比较相邻元素，交换逆序对。
3. 优化：若某轮无交换，说明已有序，提前终止。

示例代码（升序）：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped)
            break; // 优化：无交换则退出
    }
}

时间复杂度：平均/最坏O(n²)，最好O(n)（已排序时）。

7.1.2 选择排序（Selection Sort）

思想：每轮找到当前未排序部分的最小值，放到已排序部分的末尾。
步骤：

1. 外层循环控制已排序部分的末尾位置（i从 0 到n-2）。
2. 内层循环遍历未排序部分（j从i到n-1），找到最小值的索引。
3. 交换最小值与当前位置i的元素。

示例代码（升序）：

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
    }
}

时间复杂度：始终O(n²)（无论数据是否有序）。

7.2 查找算法

查找是在数据中寻找特定值的位置。

7.2.1 顺序查找（Sequential Search）

思想：从第一个元素开始逐个比较，直到找到目标或遍历完数组。
适用场景：无序数据或数据量小。

示例代码：

int sequentialSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // 返回索引（找到）
        }
    }
    return -1; // 未找到
}

时间复杂度：O(n)。

7.2.2 二分查找（Binary Search）

思想：仅适用于有序数组，每次取中间元素比较，缩小查找范围（折半）。
步骤：

1. 初始化左边界left=0，右边界right=n-1。
2. 当left <= right时，计算中间位置mid=(left+right)/2。
3. 若中间元素等于目标，返回mid；若小于目标，调整左边界left=mid+1；否则调整右边界right=mid-1。
4. 循环结束未找到，返回 -1。

示例代码（升序数组）：

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止整数溢出
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

时间复杂度：O(log n)（效率远高于顺序查找）。

7.3 程序阅读与填空（真题示例）

题目 1：以下代码实现了哪种排序算法？

void sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        swap(arr[i], arr[minIdx]);
    }
}

答案：选择排序。

题目 2：补全二分查找代码，若找到目标值，输出其索引；否则输出 -1。

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int target = 5;
    cout << binarySearch(arr, 5, target) << endl; // 输出：2
    return 0;
}

第八章 GESP二级备考指南

8.1 考试题型分析

GESP二级考试采用上机考试形式，题型包括：

• 选择题（20题，每题2分，共40分）：考察语法基础、概念理解。
• 判断题（10题，每题2分，共20分）：判断代码正误或概念正确性。
• 程序阅读题（3题，每题8分，共24分）：分析代码输出或逻辑。
• 程序填空题（2题，每题8分，共16分）：补全关键代码实现功能。
• 编程题（1题，共20分）：根据题目要求编写完整程序。

8.2 高频考点总结

• 必考点：循环结构（for/while嵌套）、数组与字符串操作、函数调用与递归、文件读写。
• 次考点：结构体定义与使用、简单排序与查找算法、类型转换与运算符优先级。

8.3 备考建议

1. 夯实基础：熟练掌握各章节知识点，理解语法规则（如break/continue的区别）。
2. 多做真题：通过历年真题熟悉题型和考点，总结易错点（如数组越界、文件打开模式）。
3. 练习编程：动手编写代码实现功能（如冒泡排序、文件复制），注意调试（使用cout输出中间变量）。
4. 注意细节：变量初始化、数组下标从 0 开始、字符串结束符\0、文件关闭等。

结语

GESP二级是编程能力的重要里程碑，本文覆盖了所有核心知识点，结合示例与真题解析，助你系统备考。记住：编程能力的提升离不开理解 + 实践，多敲代码、多思考、多总结，你一定能顺利通关！