前言
CCF 编程能力等级认证，英文名 Grade Examination of Software Programming（以下简称 GESP），由中国计算机学会发起并主办。
GESP 是全国唯一打通 CSP-J/S（全国青少年信息学奥林匹克竞赛和 CSP 初赛）的编程能力等级认证。
通过 GESP 认证，学生可以获得免考 CSP-J/S 初赛的机会，大大提高了参加更高水平编程竞赛的机会和优势。此外，GESP 的考试大纲与 CSP-J/S 的大纲基本吻合。
一、GESP 三级标准
1. 知识点详述
（1）了解二进制数据编码：原码、反码、补码。 （2）掌握数据的进制转换：二进制、八进制、十进制、十六进制。 （3）掌握位运算：与 (&)、或 (|)、非 (~)、异或 (^)、左移 (<<)、右移 (>>) 的基本使用方法及原理。 （4）了解算法的概念与描述，熟练运用自然语言、流程图、伪代码方式来描述算法。 （5）C++ 一维数组基本应用。 （6）掌握字符串及其函数的使用包括但不限于大小写转换、字符串搜索、分割、替换。 （7）理解枚举算法、枚举算法的原理及特点，可以解决实际问题。 （8）理解模拟算法、模拟算法的原理及特点，可以解决实际问题。
2. 考核目标
掌握计算机中常用进位制、位运算及数据编码的知识，掌握一维数组、字符串类型及其函数的使用，掌握枚举法、模拟法的原理和运用技巧，对于较简单的实际问题能构造算法、描述算法、实现算法并调试程序。
3. 知识块
4. 知识点描述
| 编号 | 知识块 | 知识点 |
|---|---|---|
| 1 | 数据编码 | 原码、反码、补码 |
| 2 | 进制转换 | 二进制、八进制、十进制、十六进制 |
| 3 | 位运算 | 与 (&)、或 ( |
| 4 | 算法与描述 | 枚举法、模拟法自然语言描述、流程图描述、伪代码描述 |
| 5 | 数据结构 | 一维数组 |
| 6 | 字符串及其函数 | 大小写转换、字符串搜索、分割、替换等 |
5. 题型分布
| 单选题 | 判断题 | 编程题 |
|---|---|---|
| 15 道（2 分/道） | 10 道（2 分/道） | 2 道（25 分/道） |
考试时间 120 分钟。
二、计算机知识
2.1 二进制数据编码（原码、反码、补码）
计算机中有符号数（可表示正负）以'符号位 + 数值位'存储，符号位：0 表示正数，1 表示负数；数值位长度由数据类型决定（如 char 占 8 位，int 占 32 位）。
2.1.1 原码
- 定义：直接表示'符号位 + 数值的二进制'，是最直观的编码方式。
- 示例（以 8 位 char 为例）：
// 正数：5 的原码 = 00000101（符号位 0，数值位 0000101）
// 负数：-5 的原码 = 10000101（符号位 1，数值位 0000101）
- 问题：存在'正负 0'（+0 原码 00000000，-0 原码 10000000），导致计算矛盾。
2.1.2 反码
- 定义：正数反码 = 原码；负数反码 = 符号位不变，数值位按位取反（0 变 1，1 变 0）。
- 示例（8 位 char）：
// 5 反码 = 00000101（与原码一致）
// -5 反码 = 11111010（符号位 1 不变，数值位 0000101 取反为 1111010）
- 问题：仍存在'正负 0'（-0 反码 11111111），未解决计算问题。
2.1.3 补码（计算机实际存储方式）
- 定义：正数补码 = 原码；负数补码 = 反码 + 1（末尾加 1，若有进位则传递）。
- 示例（8 位 char）：
// 5 补码 = 00000101
// -5 补码 = 11111010 + 1 = 11111011
- 优势：解决'正负 0'问题（+0 和 -0 补码均为 00000000），简化减法运算（a - b = a + (-b)，只需加法器）。
2.2 进制转换
在计算机中，数据常以不同进制表示。
2.2.1 进制的表示
- 十进制：日常使用，由 0-9 组成，C++ 中直接书写（如 123）。
- 二进制：由 0-1 组成，C++ 中以 0b 前缀表示（如 0b101 表示 5）。
- 八进制：由 0-7 组成，C++ 中以 0 前缀表示（如 017 表示 15）。
- 十六进制：由 0-9、A-F（或 a-f）组成，C++ 中以 0x 前缀表示（如 0x1F 表示 31）。
2.2.2 转换方法
- 非十进制转十进制
规则：按'位权展开求和'，位权 = 基数 ^ 位索引（从右往左，起始索引为 0）。
示例：
- 二进制 1011 转十进制： 1×2³ + 0×2² + 1×2¹ + 1×2⁰ = 8 + 0 + 2 + 1 = 11
- 十六进制 0x3A 转十进制： 3×16¹ + 10×16⁰ = 48 + 10 = 58（A 代表 10）
- 十进制转非十进制
规则：整数部分'除基取余，逆序排列'；小数部分'乘基取整，顺序排列'。
示例：
- 十进制 13 转二进制： 13 ÷ 2 = 6 余 1 6 ÷ 2 = 3 余 0 3 ÷ 2 = 1 余 1 1 ÷ 2 = 0 余 1 逆序取余得 1101。
- 十进制小数 0.625 转二进制： 0.625 × 2 = 1.25 → 整数部分为 1（二进制小数第一位），剩余小数部分 0.25 0.25 × 2 = 0.5 → 整数部分为 0（二进制小数第二位），剩余小数部分 0.5 0.5 × 2 = 1.0 → 整数部分为 1（二进制小数第三位），剩余小数部分 0（转换结束） 将取出的整数部分按顺序排列，得到 0.101
- 二进制与八 / 十六进制互转
- 二进制转八进制。
规则：将二进制数从右往左每 3 位分为一组，若最左侧不足 3 位，则在左侧补 0 凑满 3 位；每组 3 位二进制对应 1 位八进制数（0-7），最后拼接所有结果。
示例：二进制数 10110：
- 1.分组：从右往左每 3 位一组。 二进制数 10110 共 5 位，从右往左拆分： 右侧第一组：110（最后 3 位） 剩余左侧：10（只有 2 位，不足 3 位）
- 2.补 0 凑位：对左侧不足 3 位的部分，在左边补 0，凑成 3 位。 左侧剩余的 10 补 1 个 0 → 010
- 3.分组结果：010（补 0 后）和 110
- 4.每组转换为八进制： 010 对应的十进制是 0×2² + 1×2¹ + 0×2⁰ = 2 → 八进制为 2 110 对应的十进制是 1×2² + 1×2¹ + 0×2⁰ = 6 → 八进制为 6
- 5.拼接结果：将两组的八进制数按顺序拼接 → 26
- 二进制转十六进制。
规则：将二进制数从右往左每 4 位分为一组，若最左侧不足 4 位，则在左侧补 0 凑满 4 位；每组 4 位二进制对应 1 位十六进制数（0-9、A-F，其中 A=10，B=11…F=15），最后拼接所有结果。
示例：二进制数 10110 :
- 1.分组：从右往左每 4 位一组。 二进制数 10110 共 5 位，从右往左拆分： 右侧第一组：0110（最后 4 位） 剩余左侧：1（只有 1 位，不足 4 位）
- 2.补 0 凑位：对左侧不足 4 位的部分，在左边补 0，凑成 4 位。 左侧剩余的 1 补 3 个 0 → 0001
- 3.分组结果：0001（补 0 后）和 0110
- 4.每组转换为十六进制： 0001 对应的十进制是 0×2³ + 0×2² + 0×2¹ + 1×2⁰ = 1 → 十六进制为 1 0110 对应的十进制是 0×2³ + 1×2² + 1×2¹ + 0×2⁰ = 6 → 十六进制为 6
- 5.拼接结果：将两组的十六进制数按顺序拼接 → 16
- 八进制转二进制。
规则：将八进制的每一位数字，转换为对应的 3 位二进制数（不足 3 位时在左侧补 0），最后拼接所有结果。
示例：八进制数 265 ：
- 1.拆分八进制的每一位：2、6、5
- 2.每一位转换为 3 位二进制： 八进制 2 → 二进制 010（2 的二进制是 10，补 1 个前导 0 凑 3 位） 八进制 6 → 二进制 110（6 的二进制是 110，刚好 3 位） 八进制 5 → 二进制 101（5 的二进制是 101，刚好 3 位）
- 3.拼接结果：010 + 110 + 101 = 010110101 因此，八进制 265 转换为二进制是 010110101（可省略前导 0，简写为 10110101）。
- 十六进制转二进制。
规则：将十六进制的每一位数字（0-9、A-F），转换为对应的 4 位二进制数（不足 4 位时在左侧补 0），最后拼接所有结果。
示例：十六进制数 3A7 ：
- 1.拆分十六进制的每一位：3、A、7（A 代表 10）
- 2.每一位转换为 4 位二进制： 十六进制 3 → 二进制 0011（3 的二进制是 11，补 2 个前导 0 凑 4 位） 十六进制 A（10）→ 二进制 1010（10 的二进制是 1010，刚好 4 位） 十六进制 7 → 二进制 0111（7 的二进制是 111，补 1 个前导 0 凑 4 位）
- 3.拼接结果：0011 + 1010 + 0111 = 001110100111 因此，十六进制 3A7 转换为二进制是 001110100111（可省略前导 0，简写为 1110100111）。
- 二进制转八进制。
规则：将二进制数从右往左每 3 位分为一组，若最左侧不足 3 位，则在左侧补 0 凑满 3 位；每组 3 位二进制对应 1 位八进制数（0-7），最后拼接所有结果。
示例：二进制数 10110：
2.3 位运算
位运算是直接对整数的二进制位进行操作的运算，效率极高，常用于底层编程、状态压缩等场景。GESP 三级要求掌握 6 种基本位运算：
2.3.1 基本位运算符
| 运算符 | 名称 | 作用（对二进制位） | 示例（以 8 位为例） |
|---|---|---|---|
| & | 与 | 两位均为 1 则为 1，否则为 0 | 00001010 & 00000111 = 00000010 |
| | | 或 | 两位有 1 则为 1，否则为 0 | 0001010 |
| ~ | 非 | 0 变 1，1 变 0（单目运算符） | ~00001010 = 11110101 |
| ^ | 异或 | 两位不同则为 1，相同则为 0 | 00001010 ^ 00000111 = 00001101 |
| << | 左移 | 整体左移 n 位，右侧补 0（相当于 ×2ⁿ） | 00001010 << 2 = 00101000 |
| >> | 右移 | 整体右移 n 位，左侧补符号位（相当于 ÷2ⁿ） | 10001010 >> 2 = 11100010（负数） |
三、C++ 知识
3.1 一维数组
数组是相同类型数据的连续集合，一维数组是 GESP 三级的核心数据结构，用于存储批量数据。
3.1.1 数组的定义与初始化
定义：数据类型 数组名 [长度];（长度必须是常量）。
// 方式 1：指定长度并初始化（未赋值元素默认为 0）
int arr1[5] = {1, 2, 3}; // arr1 = [1, 2, 3, 0, 0]
// 方式 2：省略长度，由初始化元素个数决定
int arr2[] = {4, 5, 6}; // 长度为 3，arr2 = [4, 5, 6]
3.1.2 数组的访问与遍历
访问：通过索引（从 0 开始）访问，如 arr[0]（第一个元素）。 遍历：常用 for 循环遍历所有元素：
int arr[] = {10, 20, 30, 40};
int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度（4）
for (int i = 0; i < len; i++) {
cout << arr[i] << " "; // 输出：10 20 30 40
}
3.1.3 数组作为函数参数
数组传参时，实际传递的是首地址，需额外传递长度：
// 求数组元素和
int sumArray(int arr[], int len) {
int sum = 0;
for (int i = 0; i < len; i++) {
sum += arr[i];
}
return sum;
}
int main() {
int nums[] = {1, 2, 3, 4};
int len = 4;
cout << "和为：" << sumArray(nums, len); // 输出 10
return 0;
}
3.2 字符串及其函数
字符串是字符的序列，C++ 中常用 char 数组和 string 类（更便捷）表示，需掌握字符串的基本操作。
3.2.1 字符串的定义
// 1. char 数组（需以'\0'结尾，表示字符串结束）
char str1[] = "hello"; // 自动添加'\0'，长度为 6（h,e,l,l,o,\0）
// 2. string 类（需包含<string>头文件，无需手动加结束符）
#include <string>
string str2 = "world";
3.2.2 常用字符串函数
- 长度与拼接
- length()/size()：返回字符串长度。
-
- 或 append()：拼接字符串。
string s1 = "abc", s2 = "def";
cout << s1.length(); // 输出 3
cout << s1 + s2; // 输出"abcdef"
- 大小写转换
- 需结合头文件的 toupper()（转大写）和 tolower()（转小写）：
#include <cctype>
string s = "AbC";
for (int i = 0; i < s.size(); i++) {
s[i] = toupper(s[i]); // 转大写，结果为"ABC"
}
- 查找与替换
- find(sub, pos)：从 pos 位置开始查找子串 sub，返回起始索引（未找到返回 string::npos 注意判断其值为 -1）。
- replace(pos, len, sub)：从 pos 位置替换 len 个字符为 sub。
string s = "hello world";
int pos = s.find("world"); // pos=6
if (pos != string::npos) {
s.replace(pos, 5, "C++"); // 替换为"hello C++"
}
- 分割字符串
- substr(pos, count)：用于从字符串中提取子串。
- 参数说明：
- pos：子串的起始位置（从 0 开始计数），默认值为 0。
- count：子串的长度，默认值为 std::string::npos（一个静态常量，表示'直到字符串末尾'）。
- 参数说明：
- substr(pos, count)：用于从字符串中提取子串。
示例：
string s = "I love C++";
string delimiter = " ";
size_t pos = 0;
while ((pos = s.find(delimiter)) != string::npos) {
string part = s.substr(0, pos); // 截取从 0 到 pos 的子串
cout << part << endl; // 输出"I"、"love"
s.erase(0, pos + delimiter.length()); // 移除已处理部分
}
cout << s; // 输出"C++"
3.3 枚举算法
枚举算法（穷举法）是逐一尝试所有可能解，从中找出符合条件的解，适合解空间较小的问题。
3.3.1 核心思想
- 确定枚举范围（可能解的集合）；
- 明确判断条件（解需要满足的规则）；
- 遍历所有可能解，筛选出符合条件的解。
3.4 模拟算法
模拟算法是按问题的实际流程，用代码一步步重现过程，从而得到结果，适合解决规则明确的过程性问题。
3.4.1 核心思想
- 分析问题的步骤和规则；
- 用变量模拟过程中的关键状态；
- 按步骤逐步更新状态，直至过程结束。
