🖥️ 第1课：计算机基础与编程环境
认识计算机、了解编程语言发展史、掌握 C++ 程序的基本框架。
📖 故事导入
💡 小明第一次打开编程软件，看到满屏的英文和符号，心想："这也太难了吧！" 别担心，其实一个最简单的 C++ 程序只需要 5 行代码。今天我们就从这 5 行代码开始，走进编程的世界。
🧱 一、计算机的组成
1.1 硬件（看得见摸得着的部分）
硬件 作用 生活类比
CPU（中央处理器） 执行计算和指令——计算机的"大脑" 大脑 内存（RAM） 临时存储正在运行的数据——断电丢失 草稿纸 硬盘（HDD/SSD） 永久存储文件——断电不丢失 笔记本 输入设备 键盘、鼠标——把信息"送进"电脑 耳朵/眼睛 输出设备 显示器、打印机——把结果"呈现"出来 嘴巴/手
1.2 软件
系统软件 ：Windows、macOS、Linux——管理硬件、为其他软件提供运行环境应用软件 ：编译器（Dev-C++、Code::Blocks）、浏览器、游戏等
📜 二、计算机发展简史
阶段 时间 核心元件 代表
第一代 1946-1958 电子管 ENIAC（世界上第一台通用电子计算机） 第二代 1958-1964 晶体管 体积缩小、功耗降低 第三代 1964-1970 集成电路（IC） 性能大幅提升 第四代 1970至今 大规模集成电路 个人电脑（PC）普及
📝 冯·诺依曼体系结构 是现代计算机的基础，核心思想是存储程序 ——将程序和数据都存放在内存中，由 CPU 依次读取执行。五大部件：运算器、控制器、存储器、输入设备、输出设备。
💻 三、编程语言的发展
机器语言 ：一串 0 和 1——只有计算机能直接理解汇编语言 ：用助记符代替 0/1，如 ADD、MOV高级语言 ：接近人类语言，如 C++、Python、Java
3.1 C++ 程序从编写到运行
1 编写源代码 ：在编辑器中写 .cpp 文件2 编译 ：编译器检查语法，翻译成机器码 .obj3 链接 ：把目标文件和库"拼"成可执行文件 .exe4 运行 ：双击 .exe 执行程序
📝 C++ 是编译型语言 ，代码必须先编译才能运行。
📝 四、C++ 程序的基本结构
// 我的第一个C++程序
#include <iostream> // 预处理指令——引入输入输出库
using namespace std; // 使用标准命名空间
int main() { // 主函数——程序入口
cout << "Hello, World!" ;
return 0 ; // 返回0，表示程序正常结束
}
#include <iostream>：预处理指令，引入输入输出功能using namespace std;：使用标准命名空间int main()：主函数，每个程序有且仅有一个，程序从这里开始执行return 0;：返回 0 表示程序正常结束
🏷️ 五、标识符与关键字
5.1 标识符命名规则
由字母、数字、下划线 组成
不能以数字开头 ：3score ❌ → score3 ✅不能是关键字 C++ 严格区分大小写 ：Score 和 score 是不同的标识符
5.2 常见关键字
int float double
char bool if
else for while
do break continue
return const true
false using namespace
✍️ 六、注释
// 这是单行注释：从 // 到行尾都是注释
/*
这是多行注释（块注释）
可以跨越多行
*/
💡 写注释是好习惯！编译器会完全忽略 注释。
📝 七、真题演练 （点击选项作答）
以下题目参考 GESP 一级 C++ 历年真题风格编写，考察"计算机组成、发展史、编程环境与C++基本结构"核心知识点。
📌 第 1 题 冯·诺依曼体系结构的核心思想是（ ）。
A. 存储程序
B. 并行计算
C. 人工智能
D. 云计算
📌 第 2 题 世界上第一台通用电子计算机是（ ）。
A. IBM PC
B. ENIAC
C. Apple II
D. 天河一号
📌 第 3 题 计算机中，CPU 相当于人体的（ ）。
A. 眼睛
B. 大脑
C. 心脏
D. 手
📌 第 4 题 以下关于内存（RAM） 的说法，正确的是（ ）。
A. 可以永久保存数据
B. 断电后数据会丢失
C. 只能读取不能写入
D. 是计算机最慢的存储设备
📌 第 5 题 C++ 程序总是从（ ）函数开始执行。
A. start()
B. begin()
C. main()
D. run()
📌 第 6 题 C++ 中，单行注释 使用（ ）。
A. /* 和 */
B. //
C. #
D. --
📊 真题考点统计 ：GESP 一级计算机基础考点包括 ① 冯·诺依曼体系（存储程序）② ENIAC ③ 硬件组成与作用 ④ C++ 程序结构（main 函数入口）⑤ 注释符号。常出概念选择题。
📦 第2课：变量的定义与使用
变量是程序存储数据的"盒子"，必须先声明、后使用。
📖 故事导入
🎒 想象你有一个书包，里面有不同的口袋：大口袋放课本，小口袋放橡皮。编程中的变量 就像这些口袋——每个口袋（变量）有自己的名字，能放不同类型的东西（数据类型），而且放的东西可以换（值可变）。
🧪 一、变量的声明与初始化
变量使用前必须先声明 （告诉编译器"我要一个某类型的变量"）。
int age; // 声明：我要一个叫 age 的整数变量
age = 10 ; // 赋值：把 10 放进 age
int score = 95 ; // 声明+初始化一步到位
double pi = 3.14 ;
char grade = 'A' ;
bool isPass = true ;
1.1 命名规范
变量名要有意义 ：score 比 s 好一万倍
不能以数字开头：1st ❌ → first ✅
不能有空格：my score ❌ → myScore 或 my_score ✅
1.2 变量的值可以改变
int x = 5 ;
x = 10 ; // x 从 5 变成 10
x = x + 3 ; // x 变成 13
🔒 二、常量
用 const 关键字定义值不可改变的"变量"：
const int MAX = 100 ; // MAX 的值永远是 100
MAX = 200 ; // ❌ 编译错误！常量不可修改
const double PI = 3.14159 ; // 圆周率，不会变
💡 使用常量的好处：程序更安全（防止误改），更易维护（改一处即可）。
📝 三、真题演练 （点击选项作答）
以下题目参考 GESP 一级 C++ 历年真题风格编写，考察"变量声明、命名规范、常量与赋值"核心知识点。
📌 第 1 题 以下变量声明合法 的是（ ）。
A. int 1st;
B. int first;
C. int my score;
D. int!score;
📌 第 2 题 const int MAX = 100; 之后，再执行 MAX = 200; 会（ ）。
A. 编译错误（常量不可修改）
B. MAX 变成 200
C. 运行时错误
D. 被忽略，MAX 仍是 100
📌 第 3 题 以下变量名中，命名最好 的是（ ）。
A. int s;
B. int studentScore;
C. int x1;
D. int abc123;
📌 第 4 题 执行 int x = 5; x = x + 3; 后，x 的值是（ ）。
A. 5
B. 3
C. 8
D. 15
📌 第 5 题 C++ 中，变量使用前必须 （ ）。
A. 用 cout 输出
B. 先声明
C. 加 const
D. 赋值为 0
📌 第 6 题 const 关键字的作用是（ ）。
A. 让变量可以改变
B. 定义常量，值不可修改
C. 加快程序运行速度
D. 声明变量
📊 真题考点统计 ：GESP 一级变量考点包括 ① 声明语法 ② 命名规则（不能数字开头/空格/特殊符号）③ const 常量 ④ 变量可重新赋值。常出语法判断题。
📊 第3课：基本数据类型
int、float、double、char、bool——五大基本类型，各有各的用途。
📊 一、五种基本数据类型
类型 关键字 占字节 取值范围（约） 用途
整型 int4 字节 -21亿 ~ 21亿 存整数：年龄、分数、个数 单精度浮点 float4 字节 ±3.4×10³⁸ 存小数（精度约7位） 双精度浮点 double8 字节 ±1.7×10³⁰⁸ 存小数（精度约15位） 字符型 char1 字节 -128 ~ 127 存单个字符：'A'、'7' 布尔型 bool1 字节 true / false存真假值：开关、判断结果
⚠️ 一级考点： int 的除法会截断小数部分 ，如 7 / 3 结果是 2 而不是 2.333。
🔤 二、字符与 ASCII 码
计算机存储字符时，实际存储的是整数编号 ——ASCII 码。
区域 ASCII 范围 记忆要点
数字 0–9 48 – 57 起点 '0' = 48 大写字母 A–Z 65 – 90 起点 'A' = 65 小写字母 a–z 97 – 122 起点 'a' = 97
💡 大小写字母之间相差 32 （97-65=32）。
2.1 大小写转换
char lower = 'g' ;
char upper = lower - 32 ; // 'g'(103) - 32 = 71('G')
cout << upper; // 输出 G
char ch = 'g' ;
ch = ch - 'a' + 'A' ; // 更优雅的写法：小写转大写
📝 三、真题演练 （点击选项作答）
以下题目参考 GESP 一级 C++ 历年真题风格编写，考察"基本数据类型、int 除法截断、ASCII 码与大小写转换"核心知识点。
📌 第 1 题 C++ 中，7 / 3 的结果是（ ）。
A. 2.333
B. 2
C. 3
D. 2.3333
📌 第 2 题 字符 'g' 的 ASCII 码值是（ ）。
A. 65
B. 103
C. 97
D. 71
📌 第 3 题 char ch = 'g'; ch = ch - 32; 后，ch 变成（ ）。
A. 'g'
B. 'G'
C. 'a'
D. 编译错误
📌 第 4 题 存储"是否及格"（true/false），最适合的类型是（ ）。
A. int
B. char
C. bool
D. float
📌 第 5 题 与 float 相比，double 的优势 是（ ）。
A. 占用内存更少
B. 精度更高（约 15 位有效数字）
C. 只能存整数
D. 运行更快
📌 第 6 题 大写字母 'A'(65) 和小写 'a'(97) 相差（ ）。
A. 26
B. 32
C. 48
D. 65
📊 真题考点统计 ：GESP 一级数据类型考点包括 ① int 除法截断 ② ASCII 三组值（48/65/97）③ 大小写差 32 ④ bool 用途 ⑤ float/double 精度。常出语法判断和读代码题。
⌨️ 第4课：输入输出语句
让程序"说话"（cout）和"听话"（cin）——交互的基础。
📤 一、输出 —— cout
#include <iostream>
using namespace std;
int main() {
cout << "Hello, World!" ; // 输出字符串
cout << 2026 ; // 输出数字
cout << endl; // 换行
cout << "总分：" << 95 << endl; // 链式输出
int age = 12 ;
cout << "年龄：" << age << "岁" << endl;
// 输出：年龄：12岁
return 0 ;
}
1.1 endl 换行
endl 的作用是换行并刷新缓冲区 。也可以用 "\n" 仅换行。
📥 二、输入 —— cin
int age;
cout << "请输入你的年龄：" ;
cin >> age; // 程序暂停，等待用户输入，按回车确认
cout << "你今年" << age << "岁" << endl;
2.1 连续输入多个值
int a, b, c;
cin >> a >> b >> c; // 输入 10 20 30（空格隔开），a=10 b=20 c=30
2.2 cin 的重要特性
cin 遇到空格、Tab、回车 会自动停止本次读取
读入整数时会自动跳过前面的空白字符
⚠️ 用 cin 读取 char 型变量时，空格、Tab、回车会被自动跳过 。
🎯 GESP 历年真题演练（共 6 题）
📌 第 1 题 在 C++ 中，cout << "Hello"; 的输出结果是（ ）。（ ）
A. 输出 Hello（不带引号）
B. 输出 "Hello"（带引号）
C. 输出 cout Hello
D. 编译错误
📌 第 2 题 endl 的作用是（ ）。（ ）
A. 输出单词 endl
B. 换行但不刷新缓冲区
C. 换行并刷新缓冲区
D. 结束程序
📌 第 3 题 以下代码 int a,b; cin >> a >> b; 如果输入 "10 20"，a 和 b 的值分别是（ ）。（ ）
A. a=10, b=空
B. a=10, b=20
C. a=空, b=20
D. a=1020, b=空
📌 第 4 题 cin 在读取 int 类型数据时，遇到什么会停止本次读取？（ ）（ ）
A. 只有回车
B. 只有空格
C. 空格、Tab、回车都会
D. 只有分号
📌 第 5 题 代码 cout << "总分：" << 95 << "分" << endl; 的输出结果是（ ）。（ ）
A. 总分：95分（不换行）
B. 总分：95分（换行）
C. 总分：<<95<<分
D. 编译错误
📌 第 6 题 以下哪一项是正确的 C++ 输入语句？（ ）（ ）
A. cin << a;
B. cin >> a;
C. cout >> a;
D. input(a);
➕⚖️ 第5课：基本运算
算术运算、关系运算、逻辑运算——让程序拥有计算能力和判断能力。
🔢 一、算术运算符
运算符 含义 示例 结果 备注
+加法 10 + 313— -减法 10 - 37— *乘法 10 * 330— /除法 10 / 33⚠️ 整数除法截断小数 %取余 10 % 31⚠️ 只能用于整数
1.1 整数除法的"坑"
int r1 = 7 / 3 ; // r1 = 2（不是2.333！）
double r2 = 7.0 / 3 ; // r2 = 2.33333（正确！）
1.2 取余的妙用
7 % 2 → 1 // 奇数
8 % 2 → 0 // 偶数
1.3 复合赋值运算符
写法 等价于
a += 5a = a + 5a -= 3a = a - 3a *= 2a = a * 2a /= 4a = a / 4a %= 3a = a % 3
1.4 自增与自减
int a = 5 , b;
b = a++; // b = 5, a = 6（先赋值，后加）
b = ++a; // b = 7, a = 7（先加，后赋值）
⚠️ GESP 一级经典考点：前置 vs 后置的区别！
1.5 运算符优先级
括号 > 乘除取余 > 加减，同级从左到右。拿不准就加括号 ！
📏 二、关系运算符
运算符 含义 示例
>大于 a > b<小于 a < b>=大于等于 a >= 5<=小于等于 a <= 3==等于 a == 5!=不等于 a != b
🚨 头号陷阱：== 和 = 的区别！ == 是等于判断 ，= 是赋值 。if (x = 5) 不会报错，但永远为真！
🧠 三、逻辑运算符
运算符 含义 口诀
&&逻辑与（AND） 都真才真 ||逻辑或（OR） 一真即真 !逻辑非（NOT） 真变假，假变真
3.1 短路求值
A && B ：A 为 false 时，B 不执行A || B ：A 为 true 时，B 不执行
🎯 GESP 历年真题演练（共 6 题）
📌 第 1 题 C++ 中 5 / 2 的结果是（ ）。（ ）
A. 2.5
B. 2
C. 3
D. 2.0
📌 第 2 题 10 % 3 的结果是（ ）。（ ）
A. 3
B. 1
C. 0
D. 3.33
📌 第 3 题 a += 3 等价于（ ）。（ ）
A. a = 3
B. a = a + 3
C. a = a - 3
D. a + 3
📌 第 4 题 执行 int a = 5; cout << a++; 后，输出结果和 a 的值分别是（ ）。（ ）
A. 输出5, a=6
B. 输出6, a=6
C. 输出5, a=5
D. 输出6, a=5
📌 第 5 题 3 + 4 * 5 的结果是（ ）。（ ）
A. 35
B. 23
C. 17
D. 60
📌 第 6 题 在 C++ 中，(5 > 3) && (2 > 4) 的值是（ ）。（ ）
A. true(1)
B. false(0)
C. 5
D. 编译错误
🔀 第6课：选择结构（if-else）
让程序根据不同的条件走不同的路——实现"智能"的第一步。
📖 故事导入
🚦 十字路口，红灯停绿灯行——这就是最基本的条件判断。在 C++ 中，if-else 就是程序的"红绿灯"。
🔄 一、三种 if 结构
1.1 单分支（如果…就…）
int score;
cin >> score;
if (score >= 60 ) {
cout << "及格！" << endl;
}
1.2 双分支（如果…就…否则…）
if (score >= 60 ) {
cout << "及格！" ;
} else {
cout << "不及格，继续加油！" ;
}
1.3 多分支（如果…否则如果…否则…）
if (score >= 90 ) {
cout << "优秀" ;
} else if (score >= 75 ) {
cout << "良好" ;
} else if (score >= 60 ) {
cout << "及格" ;
} else {
cout << "不及格" ;
}
⚠️ 多分支是从上到下依次判断的，一旦某个条件为真，后面的条件不再判断 。
🪆 二、if 嵌套
int num;
cin >> num;
if (num > 0 ) { // 外层：是正数吗？
if (num % 2 == 0 ) { // 内层：是偶数吗？
cout << "正偶数" ;
} else {
cout << "正奇数" ;
}
}
else 总是和它上面最近的、尚未配对的 if 组成一对。
📝 三、常见考题
判断奇偶 ：if (n % 2 == 0)判断闰年 ：if (year%400==0 || (year%4==0 && year%100!=0))判断三角形 ：两边之和大于第三边求最大值 ：用 if 比较两个或三个数
🎯 GESP 历年真题演练（共 6 题）
📌 第 1 题 以下代码的输出是（ ）。int x = 10;（ ）
A. A
B. B
C. AB
D. 无输出
📌 第 2 题 if (x = 5) 在 C++ 中表示（ ）。（ ）
A. 判断 x 是否等于 5
B. 把 5 赋值给 x，且条件为 true
C. 语法错误
D. 判断 x 是否不等于 5
📌 第 3 题 以下关于 else 的说法，正确的是（ ）。（ ）
A. else 可以单独使用
B. else 必须和最近的未配对 if 配对
C. 一个 if 可以有多个 else
D. else 后面必须跟条件
📌 第 4 题 代码 int score=85; if(score>=90) cout<<"A"; else if(score>=80) cout<<"B"; else cout<<"C"; 输出（ ）。（ ）
A. A
B. B
C. C
D. ABC
📌 第 5 题 以下哪个条件正确判断"x 在 1 到 10 之间（含）"？（ ）（ ）
A. if(1 <= x <= 10)
B. if(x >= 1 && x <= 10)
C. if(x >= 1 || x <= 10)
D. if(x > 1 && x < 10)
📌 第 6 题 if (0) cout << "YES"; 会输出什么？（ ）（ ）
A. YES
B. NO
C. 0
D. 无输出
🔄 第7课：while 循环
让程序反复做同一件事——只要条件满足，就永不停止。
📖 故事导入
🏃 操场跑圈："跑够10圈就停"——这就是一个 while 循环！特点：先看看条件是否满足，满足就继续，不满足就停。
🔁 一、while 循环基本语法
while (条件) {
// 循环体：条件为真时反复执行
}
1.1 输出 1 到 10
int i = 1 ; // ① 初始化循环变量
while (i <= 10 ) { // ② 判断条件
cout << i << " " ;
i++; // ③ 改变循环变量，避免死循环
}
1.2 求累加和 1+2+...+100
int sum = 0 , i = 1 ;
while (i <= 100 ) {
sum += i;
i++;
}
cout << sum; // 输出 5050
⚠️ 二、死循环
如果条件永远为真 ，循环将永不停止。
🚨 写循环口诀：①初始化；②条件；③改变循环变量。 三步缺一不可！
2.1 逐位拆解数字（经典应用）
int n = 12345 ;
while (n > 0 ) {
cout << n % 10 << " " ; // 输出最后一位
n /= 10 ; // 去掉最后一位
}
// 输出：5 4 3 2 1
🎯 GESP 历年真题演练（共 6 题）
📌 第 1 题 int i=1; while(i<=5){ cout<<i<<" "; i++; } 输出是（ ）。（ ）
A. 1 2 3 4 5
B. 1 2 3 4
C. 1 2 3 4 5 6
D. 0 1 2 3 4 5
📌 第 2 题 int sum=0,i=1; while(i<=100){ sum+=i; i++; } 循环结束时 sum 的值是（ ）。（ ）
A. 100
B. 5050
C. 4950
D. 101
📌 第 3 题 以下哪个是死循环 （永远不会结束）？（ ）（ ）
A. while(0) {}
B. while(1) { break; }
C. while(1) {}
D. int i=0; while(i<10) i++;
📌 第 4 题 以下代码输出什么？int n=123; while(n>0){ cout<<n%10; n/=10; }（ ）
A. 123
B. 321
C. 1
D. 12
📌 第 5 题 while 循环的条件判断在什么时候进行？（ ）（ ）
A. 每次循环体执行完之后
B. 每次循环体执行之前
C. 只在第一次时判断
D. 循环体执行到一半时
📌 第 6 题 int i=10; while(i>0){ i-=3; } 循环执行几次？（ ）（ ）
A. 3次
B. 4次
C. 5次
D. 10次
🔄 第8课：for 循环
初始化、条件、更新三合一——for 是最常用的循环结构。
📖 故事导入
📋 "抄写单词 10 遍"——你知道要抄几遍（10遍），每抄完一遍就在心里数"还剩9遍、8遍…完成！" 这种明确知道次数 的重复，最适合 for。
🔁 一、for 循环基本语法
for (初始化; 条件; 更新) {
// 循环体
}
// 执行流程：
// ① 执行"初始化"（只执行一次）
// ② 判断"条件"：真 → ③；假 → 退出
// ③ 执行"循环体"
// ④ 执行"更新"，回到 ②
1.1 经典示例
// 输出 1 到 10
for (int i = 1 ; i <= 10 ; i++) {
cout << i << " " ;
}
// 输出 10 到 1
for (int i = 10 ; i >= 1 ; i--) {
cout << i << " " ;
}
// 输出 0 到 20 的偶数
for (int i = 0 ; i <= 20 ; i += 2 ) {
cout << i << " " ;
}
⚖️ 二、for 与 while 对比
维度 for while
适用场景 已知循环次数 只知循环条件 结构 初始化、条件、更新写在一起 初始化在外面、更新在循环体内
// 两者可以互相转换
for (int i = 0 ; i < 10 ; i++) { cout << i; }
// 等价 while：
int i = 0 ;
while (i < 10 ) { cout << i; i++; }
⏸️ 三、break 和 continue
关键字 作用 类比
break跳出整个循环 下课铃响，直接离开教室 continue跳过本次循环 ，进入下一次跳过不会的题，继续做下一题
// break：找到第一个能被7整除的数就停
for (int i = 1 ; i <= 100 ; i++) {
if (i % 7 == 0 ) { cout << i; break ; }
}
// continue：只输出奇数
for (int i = 1 ; i <= 10 ; i++) {
if (i % 2 == 0 ) continue ;
cout << i << " " ; // 输出：1 3 5 7 9
}
🎯 GESP 历年真题演练（共 6 题）
📌 第 1 题 for(int i=1; i<=5; i++) cout<<i<<" "; 输出是（ ）。（ ）
A. 1 2 3 4 5
B. 0 1 2 3 4
C. 1 2 3 4
D. 0 1 2 3 4 5
📌 第 2 题 break 在循环中的作用是（ ）。（ ）
A. 暂停本次循环，进入下一次
B. 立即结束整个循环
C. 结束程序
D. 什么也不做
📌 第 3 题 for(int i=1; i<=10; i++){ if(i%2==0) continue; cout<<i<<" "; } 输出是（ ）。（ ）
A. 2 4 6 8 10
B. 1 3 5 7 9
C. 1 2 3 4 5 6 7 8 9 10
D. 无输出
📌 第 4 题 以下 for 循环与哪个 while 循环等价？for(int i=0; i<10; i++){ ... }（ ）
A. int i=0; while(i<10){ i++; ... }
B. int i=0; while(i<10){ ... i++; }
C. int i=0; while(i<=10){ ... i++; }
D. while(i<10){ int i=0; ... i++; }
📌 第 5 题 for( ; ; ) 表示什么？（ ）（ ）
A. 语法错误
B. 死循环
C. 不执行任何操作
D. 只执行一次
📌 第 6 题 以下 for 循环中变量 i 的作用域是？for(int i=0; i<5; i++){ } cout<<i;（ ）
A. 整个程序
B. 整个函数
C. 仅 for 循环内部
D. 编译错误（i 未定义）
🔄 第9课：do-while 循环
先执行一次再说——不管条件如何，循环体至少执行一次。
📖 故事导入
🎮 游戏菜单："请选择难度——①简单 ②普通 ③困难"。不管玩家选什么，菜单都要至少显示一次 。这种"先执行再判断"的场景，最适合 do-while。
🔁 一、do-while 基本语法
do {
// 循环体（至少执行一次）
} while (条件); // ← 注意这里有分号！
// 示例：用户输入验证
int choice;
do {
cout << "请输入难度（1-3）：" ;
cin >> choice;
} while (choice < 1 || choice > 3 );
⚖️ 二、三种循环对比总结
循环 判断时机 最少执行 适用场景
while先判断，后执行 0 次 只知条件 for先判断，后执行 0 次 已知次数 do-while先执行，后判断 至少 1 次 至少执行一次
🎯 GESP 历年真题演练（共 6 题）
📌 第 1 题 do-while 循环与 while 循环最重要的区别是（ ）。（ ）
A. 语法不同
B. do-while 至少执行一次循环体
C. while 更快
D. do-while 不能嵌套
📌 第 2 题 int i=0; do{ cout<<i; i++; }while(i<3); 输出是（ ）。（ ）
A. 012
B. 123
C. 01
D. 0123
📌 第 3 题 int x=10; do{ cout<<x; }while(x<5); 输出是（ ）。（ ）
A. 无输出
B. 10
C. 死循环
D. 编译错误
📌 第 4 题 以下哪种场景最适合用 do-while？（ ）（ ）
A. 已知循环次数
B. 至少需要执行一次的操作（如输入验证）
C. 可能一次都不执行的循环
D. 无限循环
📌 第 5 题 int i=5; while(i<5){ cout<<i; } 与 int i=5; do{ cout<<i; }while(i<5); 输出分别是（ ）。（ ）
A. 都无输出
B. 无输出 和 5
C. 5 和 无输出
D. 都输出 5
📌 第 6 题 下列哪种写法会导致编译错误？（ ）（ ）
A. while(true) {}
B. do {} while(true);
C. for(;;) {}
D. while() {}
🎯 第10课：顺序·分支·循环综合应用
将前面 9 课融会贯通，解决真实问题——这才是编程的魅力。
🧩 一、三种基本结构
任何程序都由这三种结构组合而成。没有例外。
📐 综合示例一：判断素数
int n;
cin >> n;
bool isPrime = true ;
for (int i = 2 ; i < n; i++) {
if (n % i == 0 ) {
isPrime = false ;
break ;
}
}
if (isPrime && n > 1 )
cout << "是素数" ;
else
cout << "不是素数" ;
🔢 综合示例二：数字反转
int n, rev = 0 ;
cin >> n;
while (n > 0 ) {
rev = rev * 10 + n % 10 ;
n /= 10 ;
}
cout << rev;
// 输入：123 → 输出：321
📊 综合示例三：统计数字
// 输入 n 个数，统计正数、负数、零各有多少个
int n, num, pos = 0 , neg = 0 , zero = 0 ;
cin >> n;
for (int i = 0 ; i < n; i++) {
cin >> num;
if (num > 0 ) pos++;
else if (num < 0 ) neg++;
else zero++;
}
cout << pos << " " << neg << " " << zero;
🎯 GESP 历年真题演练（共 6 题）
📌 第 1 题 以下哪个数不是 素数（质数）？（ ）（ ）
A. 2
B. 7
C. 9
D. 11
📌 第 2 题 以下代码的功能是（ ）。int n,rev=0; cin>>n;（ ）
A. 统计数字位数
B. 数字反转
C. 求各位数字之和
D. 判断素数
📌 第 3 题 程序设计（结构化编程）的三种基本结构是（ ）。（ ）
A. 顺序、分支、循环
B. 输入、计算、输出
C. 主函数、子函数、库函数
D. 顺序、选择、函数
📌 第 4 题 统计一个整数 n 的位数，下列代码正确的是（ ）。（ ）
A. int cnt=0; while(n>0){ n/=10; cnt++; }
B. int cnt=0; while(n>0){ cnt++; n%=10; }
C. int cnt=n;
D. int cnt=0; while(n>0){ cnt+=n%10; n/=10; }
📌 第 5 题 判断一个年份 year 是否为闰年的正确条件是（ ）。（ ）
A. year%4==0
B. year%4==0 && year%100!=0 || year%400==0
C. year%400==0
D. year%4!=0
📌 第 6 题 int n=1234; cout<<n/100%10; 输出是（ ）。（ ）
A. 1
B. 2
C. 3
D. 4
📋 GESP 一级 · 考点速查表
# 知识模块 核心考点
1 计算机基础与编程环境 硬件组成、计算机发展史、冯·诺依曼结构、C++程序基本框架、标识符、关键字、注释 2 变量的定义与使用 声明、初始化、赋值、const 常量、命名规则 3 基本数据类型 int/float/double/char/bool、ASCII码、大小写转换 4 输入输出语句 cin/cout/endl、连续输入输出、cin 空白字符处理 5 基本运算 +-*/% / 复合赋值 / 自增自减 / 整数除法截断 / 关系运算（==与=区别）/ 逻辑运算（短路求值） 6 选择结构 if / if-else / 多分支 / 嵌套if / else配对规则 7 循环结构 while / for / do-while / break / continue / 死循环
🏆 TOP 5 高频考点
整数除法截断 ：7/3=2，想得到小数需 7.0/3== 和 = 的区别 ：if(x==5) 判断 vs if(x=5) 赋值（永真）自增自减前置/后置 ：a=i++（先赋值后加）vs a=++i（先加后赋值）循环三要素 ：初始化 → 条件 → 更新，缺一可能死循环ASCII 三大关键值 ：'0'=48，'A'=65，'a'=97
💾 第1课：计算机存储
电脑的内存、硬盘、U盘……到底有什么区别？一起揭开计算机存储的秘密！
📖 故事导入
📚 小红写作业时，桌上放着课本（翻开来参考）、草稿纸（临时写写画画）、便利贴（重要公式贴眼前）。小明说："电脑存储也是这个道理——课本是硬盘，草稿纸是内存，便利贴是缓存！ "
🧠 一、什么是计算机存储？
计算机存储 就是电脑"记住"信息的地方。按功能分为两大类：内存 （临时记忆，断电即忘）和外存 （永久记忆，断电不丢）。
存储类型 特点 例子
内存 速度快、断电丢失 RAM、ROM、Cache 外存 速度慢、永久保存 硬盘、U盘、光盘
📝 二、RAM——随机存取存储器
RAM（Random Access Memory） 是电脑的"草稿纸"：
CPU 运行时在这里临时 存放数据和程序
可读可写 ，速度快断电后数据丢失 （易失性）你打开的程序、正在编辑的文档都在 RAM 里
💡 类比 ：RAM = 草稿纸，随时写随时擦，下课就被收走了（断电）。GESP 二级常考"RAM 断电丢失"。
📚 三、ROM——只读存储器
ROM（Read-Only Memory） 是电脑的"课本"：
出厂时就写好了内容，只能读取，不能随意修改
断电后数据不丢失 （非易失性）通常用于存放BIOS （开机自检程序）等固件
⚠️ 注意 ：ROM 不是完全不能改——现代有可擦写的 EPROM、EEPROM（如 BIOS 升级），但写入速度慢、次数有限。GESP 二级按"只读"理解即可。
⚡ 四、Cache——高速缓存
Cache（高速缓存） 是电脑的"便利贴"：
位于 CPU 和 RAM 之间，速度比 RAM 还快
存放 CPU 最常访问的数据，减少等待时间
容量很小（KB 到 MB 级别），但速度极快
💡 速度排序 ：Cache > RAM > 硬盘（SSD）> 机械硬盘。Cache 最快也最贵。
📊 五、三者对比总结
对比项 Cache RAM ROM
速度 最快 快 较慢 容量 极小（KB~MB） 几 GB~几十 GB 很小 可写性 可读可写 可读可写 只读（默认） 断电后 丢失 丢失 不丢失 类比 便利贴 草稿纸 课本
📝 六、真题演练 （点击选项作答）
📌 第 1 题 计算机的 RAM 在断电后，存储的数据会（ ）。
A. 永久保存
B. 部分丢失
C. 全部丢失
D. 自动备份到硬盘
📌 第 2 题 以下属于"只读存储器"的是（ ）。
A. RAM
B. Cache
C. ROM
D. 硬盘
📌 第 3 题 关于 Cache 的描述，正确 的是（ ）。
A. 容量比 RAM 大
B. 断电后数据不丢失
C. 速度比 RAM 快
D. 属于外存储器
📌 第 4 题 以下存储设备中，速度最快 的是（ ）。
A. 机械硬盘
B. ROM
C. RAM
D. Cache
📌 第 5 题 关于 ROM 的说法，正确 的是（ ）。
A. 断电后数据丢失
B. 可以随时读写
C. 通常用于存放 BIOS
D. 容量比硬盘大
📌 第 6 题 以下存储器中，断电后不丢失 数据的是（ ）。
A. RAM
B. Cache
C. ROM
D. CPU 寄存器
🌐 第2课：计算机网络
你发一条微信，是怎么"嗖"地飞到朋友手机上的？今天拆解网络通信的奥秘。
📖 故事导入
📱 小明给小红发了一条"你好！"。不到一秒，小红的手机就响了。小明很好奇：这条消息是怎么跑过去的？难道有小人儿在手机里送信？
🌍 一、什么是计算机网络？
计算机网络 就是把多台电脑（设备）连在一起，让它们可以互相通信、共享资源。按覆盖范围分为：局域网（LAN） 和广域网（WAN） 。
🏫 二、局域网 vs 广域网
对比项 局域网 (LAN) 广域网 (WAN)
覆盖范围 小范围：一栋楼、一个校园 大范围：跨城市、跨国家 传输速度 快（低延迟） 相对较慢 管理方式 自己管理 运营商维护 安全性 较高 需加密防护 典型场景 教室电脑、家庭 WiFi 全世界 LAN 连起来 → 互联网
💡 互联网 = 把全世界的局域网连起来 。你家 WiFi 是 LAN，连上运营商就是 WAN 的一部分。
🏠 三、IP 地址——网络世界的"门牌号"
🔵 IPv4
格式： 4 组 0~255 的数字，点分隔，如 192.168.1.1地址总数： 2³² ≈ 43 亿个
🟣 IPv6
格式： 8 组十六进制数，冒号分隔，连续的 0 用 :: 省略地址总数： 2¹²⁸，几乎无穷
💡 v4 是 4 段数字（32位），v6 是 8 段十六进制（128位）。双冒号在一个 IPv6 地址中只能出现一次 。
🏘️ 四、公网 IP 与私有 IP
公网 IP 私有 IP
唯一性 全球唯一 仅局域网内唯一 互联网访问 可直接被访问 需 NAT 转换 分配者 运营商 路由器自动分配 类比 你家真实地址 教室里的学号
⚠️ 私有地址三大范围（GESP 必考）： 10.x.x.x / 172.16-31.x.x / 192.168.x.x。127.0.0.1 是回环地址，永远指向自己。
📦 五、TCP/IP 四层模型
层次 功能 常见协议
应用层 为应用程序提供网络服务 HTTP、DNS 传输层 端到端可靠传输 TCP（可靠）、UDP（快速） 网际层 寻址和路由选择 IP 网络接口层 物理传输 以太网、WiFi
💡 记忆口诀：应、传、网、接 。寻址和路由是网际层 的活儿（GESP 高频考点）。
📝 六、真题演练 （点击选项作答）
📌 第 1 题 以下关于局域网（LAN）和广域网（WAN）的说法，正确的是（ ）。
A. 局域网覆盖范围比广域网大
B. 局域网传输速度通常比广域网快
C. 广域网比局域网更安全
D. 广域网由学校自己管理
📌 第 2 题 IPv4 地址的格式是（ ）。
A. 8组十六进制数，冒号隔开
B. 4组0~255的数字，点隔开
C. 6组数字，短横线隔开
D. 任意长度的数字串
📌 第 3 题 以下属于合法 IPv4 私有地址的是（ ）。
A. 8.8.8.8
B. 192.168.1.100
C. 256.1.1.1
D. 172.32.1.1
📌 第 4 题 IPv6 地址中省略连续零的符号是（ ）。
A. 单冒号 :
B. 双冒号 ::
C. 三个点 ...
D. 星号 *
📌 第 5 题 IP 地址 127.0.0.1 的作用是（ ）。
A. 连接互联网的网关
B. 指向自己的电脑（回环地址）
C. 分配给路由器的地址
D. 一个普通的私有地址
📌 第 6 题 TCP/IP 四层中负责"寻址和路由选择"的是（ ）。
A. 应用层
B. 传输层
C. 网际层
D. 网络接口层
💻 第3课：程序设计语言
人会说话，电脑也有自己的"语言"。从机器码到自然语言，一次看懂编程语言的进化史。
📖 故事导入
🤔 小红问小明："你说中文，我说英文，我们还能用翻译软件沟通。那人和电脑之间，到底是怎么'说话'的？ " 小明说："当然是用程序设计语言 啦！"
🗣️ 一、什么是程序设计语言？
程序设计语言 是人与计算机之间交流的工具。发展历史：机器语言 → 汇编语言 → 高级语言 。
⚙️ 二、语言的三个层次
层次 名称 特点 示例
第一代 机器语言 纯 0/1 二进制，CPU直接执行；难写难读 10110000 01100001第二代 汇编语言 用助记符代替二进制；仍需了解硬件 MOV AL, 61h第三代 高级语言 接近自然语言；不依赖硬件 cout << "Hello";
💡 记忆线索：机→汇→高 ，越来越像人话。机器语言是"天书"，汇编加了"缩写"，高级语言基本就是"人话"。
🚀 三、主流高级语言
语言 类型 特点
C++ 编译型 速度快、底层控制强、信奥首选 Python 解释型 语法简洁、AI/数据科学首选 Java 编译+解释 跨平台（一次编写到处运行） Scratch 可视化 拖拽积木式编程，零门槛
🔨 四、编译型 vs 解释型
对比项 编译型 解释型
工作方式 全部翻译完再执行 一行一行翻译执行 类比 整本书翻完再读 同声传译 速度 运行快 运行慢 代表 C、C++ Python、JavaScript
⚠️ 混合型 ：Java 先编译成字节码，再由 JVM 解释执行——结合两者优点。GESP 二级可能考到这种特殊类型。
🤖 五、编程语言与 AI
人工智能本质上也是用编程语言"教"出来的：Python 用于训练算法，C++ 用于高性能推理引擎。区分编译型（C++） 和解释型（Python） 及其适用场景是 GESP 高频考点。
📝 六、真题演练 （点击选项作答）
📌 第 1 题 以下属于编译型语言的是（ ）。
A. Python
B. Scratch
C. C++
D. JavaScript
📌 第 2 题 计算机能直接识别和执行的语言是（ ）。
A. 汇编语言
B. 机器语言
C. C++
D. Python
📌 第 3 题 关于高级语言的描述，正确的是（ ）。
A. 依赖于具体硬件
B. 无需翻译即可执行
C. 接近自然语言，易学易用
D. 由0和1组成
📌 第 4 题 Python 语言属于（ ）。
A. 机器语言
B. 汇编语言
C. 解释型高级语言
D. 编译型高级语言
📌 第 5 题 关于编译型语言的描述，错误 的是（ ）。
A. 运行速度通常比解释型快
B. 源代码需先编译
C. 可生成独立可执行文件
D. 每执行一行就翻译一行
📌 第 6 题 程序设计语言的发展顺序是（ ）。
A. 高级→汇编→机器
B. 机器→汇编→高级
C. 汇编→高级→机器
D. 高级→机器→汇编
🔁 第4课：流程图
代码像作文，流程图就是"提纲"。学会画流程图，编程思路更清晰！
📖 故事导入
📝 小红要写作文，老师说："先列提纲，再动笔。" 编程也一样——流程图就是程序的"提纲" ，先把步骤画出来，写代码才不会乱。
🔷 一、流程图基本符号（GESP 必记）
形状 名称 用途
圆角矩形 起止框 程序的开始 或结束 矩形 处理框 执行计算、赋值等操作 菱形 判断框 条件判断（是/否），产生分支 平行四边形 输入/输出框 输入数据或输出结果
💡 口诀：圆起方做菱判断，平行四边形输入输出 。
📊 二、三种基本结构
结构 特征 C++ 对应
顺序 从上到下逐条执行 普通语句 分支 根据条件选择路径 if / else循环 反复执行直到满足条件 while / for
🔄 三、循环结构的两种模式
类型 语法 特征
当型 while (条件) { }先判断后执行（可能 0 次） 直到型 do { } while (条件);先执行后判断（至少 1 次）
💡 while="进门先查票"，do-while="先进去再说，出来再查票"。
🧩 四、流程图建模四步法
明确目标 ：程序要解决什么问题？定义变量 ：需要哪些输入输出？拆解步骤 ：把过程分解为基本结构绘制验证 ：画出流程图，模拟执行验证正确性⚠️ GESP 高频考点 ：①菱形=判断框 ②圆角矩形=起止框 ③while先判断 do-while先执行 ④流程图只有一个起点
📝 五、真题演练 （点击选项作答）
📌 第 1 题 流程图中表示"条件判断"的图形是（ ）。
A. 矩形
B. 平行四边形
C. 菱形
D. 圆角矩形
📌 第 2 题 关于 while 循环，正确的是（ ）。
A. 循环体至少执行一次
B. 先判断条件再执行循环体
C. 不需要判断条件
D. 只能执行固定次数
📌 第 3 题 流程图中圆角矩形表示（ ）。
A. 计算操作
B. 输入输出
C. 开始或结束
D. 条件判断
📌 第 4 题 一个流程图中（ ）。
A. 可以有多个起点
B. 只能有一个起点
C. 起点用矩形表示
D. 起点必须是菱形
📌 第 5 题 判断"数字大于10"应使用（ ）。
A. 顺序结构
B. 分支结构
C. 循环结构
D. 递归结构
📌 第 6 题 属于"直到型循环"的是（ ）。
A. for
B. while
C. do-while
D. if-else
🔤 第5课：字母其实是数字！（ASCII 基础）
电脑只认识 0 和 1，那字母 A、B、C 是怎么存进去的？秘密就在 ASCII 码表里！
📖 故事导入
📞 小明问："电脑只懂 0 和 1，那它怎么知道我输入的是字母 A 呢？" 因为电脑给每个字符都编了号码——A 是 65，B 是 66……这就是 ASCII 码！
🧠 一、编码的基本概念
计算机底层只有 0 和 1 。为了让计算机"看懂"文字，每个字符被分配一个唯一的数字编号。标准 ASCII 用 7 位 二进制（0~127），共 128 个 字符。
💡 GESP 二级只要求标准 ASCII（0~127） 中的常用可打印字符。
⭐ 二、常用 ASCII 码（重点背诵）
字符 ASCII 码 记忆口诀
空格 32 可打印字符的起点 0 - 9 48 - 57 0就是48 A - Z 65 - 90 大A65 a - z 97 - 122 小a97，比大写+32
⚠️ GESP 必背 4 个基准值 ：空格=32, 0=48, A=65, a=97。记住这 4 个就能推导所有常用 ASCII 码！
🔍 三、规律推导与大小写转换
B = A + 1 = 66，5 = 0 + 5 = 53 小写→大写 ：减 32（a(97) - 32 = A(65)）大写→小写 ：加 32（A(65) + 32 = a(97)）💡 大小顺序速记 ：空格(32) < 0(48) < A(65) < a(97)。
📊 四、C++ 中的字符操作
char c1 = 'A'; // c1 的 ASCII 值是 65
char c2 = c1 + 1; // c2 = 'B'（ASCII 66）
int n = '5' - '0'; // n = 5（字符数字转整数）
char lower = c1 + 32; // lower = 'a'（大写转小写）
📝 五、真题演练 （点击选项作答）
📌 第 1 题 字符 A 的 ASCII 码是（ ）。
A. 97
B. 65
C. 48
D. 32
📌 第 2 题 已知 D 的 ASCII 码为 68，则 F 为（ ）。
A. 69
B. 70
C. 71
D. 72
📌 第 3 题 ASCII 码值最大 的是（ ）。
A. 空格
B. 0
C. A
D. a
📌 第 4 题 将小写 c 转大写，正确方法是（ ）。
A. c + 32
B. c - 32
C. c + A
D. c - a
📌 第 5 题 0 的 ASCII 码为 48，则 5 为（ ）。
A. 48
B. 52
C. 53
D. 55
📌 第 6 题 关于 ASCII 码，错误 的是（ ）。
A. 标准ASCII用7位
B. 共128个字符
C. A的码大于a
D. 空格可打印
🔄 第6课：数据类型转换
int 和 double 混在一起计算会怎样？理解类型转换，避免计算出错！
📖 故事导入
🍕 小明买披萨，标价 29.5 元。int price = 29.5; 结果变成 29 元！老板不干了："还有 5 毛呢？"——这就是类型转换 的坑！
🔀 一、两种转换方式
转换类型 触发方式 安全性
隐式转换 编译器自动完成 窄→宽安全，宽→窄可能丢数据 显式转换 程序员强制指定 需自行承担风险
📐 二、自动类型提升规则
运算时小类型自动转大类型 ：
char → short → int → long long → float → double
💡 核心规则 ：int + double = double。整数小数混合运算，结果自动升级为小数。
⚠️ 三、整数除法陷阱
int a = 5, b = 2;
cout << a / b; // 输出 2（不是 2.5！）
cout << 5.0 / 2; // 输出 2.5（有一个小数就行）
⚠️ 两个整数相除结果取整 （去尾，不四舍五入）。要小数结果，把其中一个变成 double。
🔧 四、强制类型转换
double pi = 3.14159;
int n = (int)pi; // n = 3（截断，不四舍五入）
int m = int(pi); // 另一种写法
🔢 五、char 与 int 互转
char ch = 'A';
int code = ch; // code = 65（ASCII码）
char next = (char)(code + 1); // next = 'B'
📝 六、真题演练 （点击选项作答）
📌 第 1 题 结果为 2.5 的是（ ）。
A. 5 / 2
B. 5.0 / 2
C. (int)(5.0 / 2)
D. int(5 / 2)
📌 第 2 题 int x = 3.9; x 的值是（ ）。
A. 4
B. 3
C. 3.9
D. 编译出错
📌 第 3 题 3 + 5.0 的类型是（ ）。
A. int
B. float
C. double
D. char
📌 第 4 题 关于类型转换，正确 的是（ ）。
A. double→int安全
B. int→double自动安全
C. 只能显式
D. char不能转int
📌 第 5 题 值为 2 的是（ ）。
A. 5 / 2
B. 5.0 / 2.0
C. (double)5 / 2
D. 5 / 2.0
📌 第 6 题 (int)A 的值是（ ）。
A. A
B. 97
C. 65
D. 0
🌳 第7课：分支嵌套——if 里面套 if
一个条件不满足？那就再套一层！掌握 if 嵌套，处理复杂判断游刃有余。
📖 故事导入
🏪 小明要进游戏厅玩：先看年龄够不够，再看有没有带钱、有没有空位……这就是层层判断 ——if 嵌套！
🧱 一、if 嵌套的语法
if (条件1) {
if (条件2) {
// 两个条件都满足
} else {
// 条件1满足，条件2不满足
}
} else {
// 条件1不满足
}
💡 嵌套就是"if 里面再写 if" ，每一层只管自己的条件。
⚖️ 二、else 匹配原则
就近匹配 ：else 与最近的未配对的 if 匹配。
⚠️ 必须用大括号 { } 明确归属！省略大括号时 else 会匹配错误。GESP 常考这种陷阱题。
📝 三、典型例题：成绩等级
int score = 85;
if (score >= 90) cout << "A";
else if (score >= 80) cout << "B";
else if (score >= 70) cout << "C";
else cout << "D";
if-else if-else 链本质也是嵌套——每个 else 后面套着下一个 if。
🔍 四、嵌套深度与代码风格
每嵌套一层缩进4个空格 。嵌套超过3~4层代码会难以阅读，应考虑提取函数或使用逻辑运算符简化。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 关于 if 嵌套，正确 的是（ ）。
A. if里不能写if
B. if里可以写if
C. 最多嵌套2层
D. 嵌套必须用else
📌 第 2 题 以下代码输出（ ）。int a=5,b=10;
A. X
B. Y
C. XY
D. 无
📌 第 3 题 if-else if-else 链最多执行（ ）个分支。
A. 0
B. 1
C. 多个
D. 全部
📌 第 4 题 else 匹配哪个 if？（ ）
A. 最远的if
B. 最近的未配对if
C. 第一个if
D. 最近的if（不论配对）
📌 第 5 题 以下不是 嵌套的是（ ）。
A. if(){if(){}}
B. if(){}else if(){}
C. if(){}else{if(){}}
D. if(){} if(){}
📌 第 6 题 x=0时 if(x!=0) if(x>0) a=1; else a=2; a为（ ）。
A. 0
B. 1
C. 2
D. 未定义
🔀 第8课：switch 选择结构
多个固定值判断？switch 比 if-else 更优雅！记住 break 别漏了。
📖 故事导入
🎛️ 小明在食堂选菜：1号窗打饭，2号窗打菜，3号窗打汤……switch 就是"按编号去对应窗口" 。没 break 的话，拿完饭还得去拿菜、拿汤……
📐 一、switch 基本语法
switch(表达式) {
case 值1: 语句1; break;
case 值2: 语句2; break;
default: 语句0;
}
💡 表达式必须是整型 （int/char/enum），不能是 float/double 或字符串 。
⛔ 二、break 的重要性
有无 break 效果
有 break 执行完本 case 后跳出 switch 无 break 继续执行下一个 case （穿透）
⚠️ GESP 陷阱题 ：故意漏写 break，让你判断执行了几个 case。别踩坑！
🔢 三、case 值要求
case 值必须是常量表达式 ，不能是变量 多个 case 值不能相同 default 可放任意位置（通常最后），可省略 🎯 四、switch vs if-else
场景 推荐 判断多个固定值 switch 判断范围（x>10） if-else
📝 五、真题演练 （点击选项作答）
📌 第 1 题 switch 表达式可以是（ ）。
A. double
B. string
C. int
D. float
📌 第 2 题 没有 break 时 switch 会（ ）。
A. 编译出错
B. 穿透到下一个case
C. 只执行default
D. 跳出switch
📌 第 3 题 switch(x){case 1:a=1;case 2:a=2;break;}当x=1时a为（ ）。
A. 0
B. 1
C. 2
D. 不确定
📌 第 4 题 case 后面的值要求是（ ）。
A. 变量
B. 常量表达式
C. 任意表达式
D. 函数调用
📌 第 5 题 default 的作用是（ ）。
A. 必须放最前面
B. 所有case都不匹配时执行
C. 必须写
D. 每个case后都执行
📌 第 6 题 关于 switch，错误 的是（ ）。
A. 括号内可以是char
B. case值不能重复
C. 每个case后必须有break
D. default可省略
🔁 第9课：循环基础
重复的事情交给电脑做！掌握 for、while、do-while 三种循环，告别重复劳动。
📖 故事导入
🏃 小明被罚跑操场 10 圈。他不想在心里默默数圈，于是用循环：for(int i=1; i<=10; i++)——跑完 10 圈自动停！
🔢 一、for 循环
for (初始化; 条件; 更新) {
// 循环体
}
for (int i = 1; i <= 10; i++) {
cout << i << " "; // 输出 1 2 3 ... 10
}
三个部分：初始化 （只执行一次）→ 条件判断 （每次循环前）→ 更新 （每次循环后）。
🔂 二、while 循环
while (条件) {
// 循环体
}
💡 while = 先判断再执行 ，条件不满足时可能一次都不执行（0次）。
🔄 三、do-while 循环
do {
// 循环体
} while (条件);
⚠️ do-while = 先执行再判断 ，循环体至少执行一次 。注意末尾有分号！
📊 四、三种循环对比
循环类型 最少次数 适用场景
for 0 次 明确知道循环次数 while 0 次 不确定次数，先判断 do-while 1 次 不确定次数，先执行
⏹️ 五、break 和 continue
关键字 作用 break 立即跳出 整个循环 continue 跳过本次循环剩余部分，进入下一次
📝 六、真题演练 （点击选项作答）
📌 第 1 题 关于 for 循环，正确 的是（ ）。
A. for中三个表达式都可省略
B. 循环体至少执行一次
C. for只能计数递增
D. 初始化每次循环都执行
📌 第 2 题 while(0){...} 的循环体会执行（ ）。
A. 0次
B. 1次
C. 无限次
D. 编译错误
📌 第 3 题 do-while 循环至少执行（ ）次。
A. 0
B. 1
C. 2
D. 不确定
📌 第 4 题 break 的作用是（ ）。
A. 跳过本次循环
B. 跳出整个循环
C. 结束程序
D. 进入下一次循环
📌 第 5 题 以下代码输出（ ）。for(int i=1;i<=3;i++){if(i==2)continue;cout<<i;}
A. 123
B. 13
C. 12
D. 23
📌 第 6 题 循环结束后 i 的值：for(int i=0;i<5;i++){}——i 为（ ）。
A. 4
B. 5
C. 0
D. 不确定
🔁🔁 第10课：循环嵌套
循环里面套循环——就像钟表：秒针转一圈，分针走一格。循环嵌套，威力翻倍！
📖 故事导入
🕐 小明观察钟表：秒针每转 60 圈，分针转 1 圈。这就是循环嵌套 ——外循环控制分针，内循环控制秒针。
🧱 一、循环嵌套的语法
for (int i = 1; i <= 3; i++) { // 外层
for (int j = 1; j <= 2; j++) { // 内层
cout << i << "," << j << " ";
}
}
// 输出：1,1 1,2 2,1 2,2 3,1 3,2 (共 3x2=6 次)
💡 总执行次数 = 外层次数 × 内层次数 。每层循环都可以是 for、while 或 do-while。
⭐ 二、经典案例：打印矩形
// 打印 3 行 5 列的 *
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 5; j++) {
cout << "*";
}
cout << endl; // 每行结束换行
}
// *****
// *****
// *****
🔺 三、经典案例：打印三角形
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= i; j++) {
cout << "*";
}
cout << endl; // 第i行打印i个*
}
// *
// **
// ***
// ****
// *****
⚠️ 内层循环的终止条件可以依赖外层变量 （如 j<=i），这是打印各种图案的关键。
📊 四、九九乘法表
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= i; j++) {
cout << j << "*" << i << "="
<< i*j << " ";
}
cout << endl;
}
📝 五、真题演练 （点击选项作答）
📌 第 1 题 外层循环3次，内层循环4次，循环体共执行（ ）次。
A. 7
B. 12
C. 3
D. 4
📌 第 2 题 以下代码输出几个 *（ ）。for(i=0;i<3;i++)for(j=0;j<2;j++)cout<<"*";
A. 3
B. 5
C. 6
D. 2
📌 第 3 题 打印 M 行 N 列的矩形，内层循环执行（ ）次。
A. M
B. N
C. M×N
D. 不确定
📌 第 4 题 关于嵌套循环，正确的是（ ）。
A. 只能用同类型循环
B. 外层必须是for
C. 可混合for/while
D. 最多嵌套2层
📌 第 5 题 以下代码输出（ ）。for(i=1;i<=2;i++){for(j=1;j<=2;j++)cout<<i+j;}
A. 2334
B. 2345
C. 1111
D. 1234
📌 第 6 题 break 在嵌套循环中会（ ）。
A. 跳出所有循环
B. 只跳出内层循环
C. 结束程序
D. 不执行任何操作
📋 第11课：枚举——给一组值起名字
星期一到星期日、红绿灯颜色……枚举让代码更可读，告别"魔法数字"！
📖 故事导入
🚦 小明写交通灯程序，用 1=红、2=黄、3=绿。一周后回来改代码，看着"1、2、3"一脸懵……如果用枚举 ，写成 RED、YELLOW、GREEN，一眼就懂！
📐 一、枚举的定义
enum Color { RED, GREEN, BLUE }; // 默认 RED=0, GREEN=1, BLUE=2
Color c = RED; // c 的值是 0
💡 枚举本质是整数常量 ，默认从 0 开始递增。枚举名应大写（约定俗成）。
🔢 二、自定义枚举值
enum Week { MON=1, TUE, WED, THU, FRI, SAT, SUN };
// MON=1, TUE=2, WED=3, ... SUN=7
enum Status { OK=200, NOT_FOUND=404, ERROR=500 };
可以指定起始值，后续依次+1。也可以每个各自指定。
⚖️ 三、枚举 vs const 常量
对比项 enum const
自动编号 支持（默认+1） 需手动指定 类型安全 强类型 普通变量 适用场景 一组相关常量 单个常量
⚠️ 枚举 vs 整数 ：C++ 中枚举可隐式转 int，但 int 不能隐式转枚举。GESP 可能考察这种类型转换限制。
🔀 四、枚举与 switch 配合
enum Direction { UP, DOWN, LEFT, RIGHT };
Direction dir = UP;
switch (dir) {
case UP: cout << "向上"; break;
case DOWN: cout << "向下"; break;
// ...
}
枚举 + switch 是经典组合，比 if-else 更清晰。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 enum Color{RED,GREEN,BLUE}; 中 GREEN 的值是（ ）。
A. 0
B. 1
C. 2
D. 不确定
📌 第 2 题 enum Week{MON=5,TUE,WED}; 中 WED 的值是（ ）。
A. 5
B. 6
C. 7
D. 不确定
📌 第 3 题 关于枚举的说法，正确 的是（ ）。
A. 枚举值必须是0开始
B. 枚举本质是整数
C. 枚举值不能自定义
D. 枚举不能用于switch
📌 第 4 题 以下枚举定义正确 的是（ ）。
A. enum A{a=1.5};
B. enum B{b=1,c=2};
C. enum C{c,d,e};
D. enum D{d=1,e=1};
📌 第 5 题 枚举和 const 的主要区别是（ ）。
A. 枚举不能用于赋值
B. const占用内存枚举不占用
C. 枚举可自动编号且类型安全
D. 枚举必须大写
📌 第 6 题 enum Flag{A,B=3,C}; C 的值是（ ）。
A. 2
B. 3
C. 4
D. 5
📐 第12课：cmath 数学函数
开平方、求绝对值、取整……cmath 是 C++ 的数学工具箱，让你轻松搞定各种计算！
📖 故事导入
🧮 小明要算 sqrt(25)、abs(-8)、pow(2,10)……难道要自己写代码？不需要！C++ 内置了 <cmath> 头文件 ，里面装满了数学函数，直接调用就行！
📦 一、使用 cmath
#include <cmath> // 必须引入头文件
double x = sqrt(25); // x = 5.0
💡 使用任何 cmath 函数前必须先写 #include <cmath> ，否则编译报错。
⭐ 二、常用函数速查表
函数 功能 示例
sqrt(x)平方根 √x sqrt(25)=5.0 abs(x)整数绝对值 |x| abs(-8)=8 fabs(x)浮点绝对值 fabs(-3.14)=3.14 pow(a,b)a 的 b 次方 a^b pow(2,10)=1024 ceil(x)向上取整 ceil(3.14)=4.0 floor(x)向下取整 floor(3.14)=3.0 round(x)四舍五入 round(3.5)=4.0 max(a,b)取较大值 max(5,9)=9 min(a,b)取较小值 min(5,9)=5
🔄 三、取整三兄弟对比
函数 含义 3.14 3.8 -3.14
ceil 天花板（向上） 4.0 4.0 -3.0 floor 地板（向下） 3.0 3.0 -4.0 round 四舍五入 3.0 4.0 -3.0
⚠️ ceil 和 floor 对负数要小心！ ceil(-3.14)=-3.0（向数轴右边），floor(-3.14)=-4.0（向数轴左边）。和直觉可能相反！
💡 四、实战技巧
判断完全平方数： int s=sqrt(n); if(s*s==n)保留两位小数： round(x*100)/100.0min/max 不用 cmath： C++11 起在 <algorithm>中，但考试通常不区分
📝 五、真题演练 （点击选项作答）
📌 第 1 题 sqrt(16) 的值是（ ）。
A. 4
B. 4.0
C. 8
D. 256
📌 第 2 题 ceil(3.14) 的值是（ ）。
A. 3.0
B. 3.14
C. 4.0
D. 4
📌 第 3 题 floor(-3.14) 的值是（ ）。
A. -3.0
B. -4.0
C. 3.0
D. 4.0
📌 第 4 题 pow(2, 3) 的值是（ ）。
A. 6
B. 8
C. 8.0
D. 9
📌 第 5 题 使用 sqrt 函数需要包含的头文件是（ ）。
A. <iostream>
B. <cmath>
C. <algorithm>
D. <math>
📌 第 6 题 abs(-10) 的值是（ ）。
A. -10
B. 10
C. 10.0
D. 0
🎲 第13课：随机数
让程序"掷骰子"！rand() 生成随机数，srand() 设置种子，猜数字游戏的核心技术。
📖 故事导入
🎯 小明想写一个猜数字游戏：程序随机出一个 1~100 的数，让玩家来猜。可是，程序怎么能"随便"出一个数呢？答案就是——rand() 函数！
🔢 一、rand() 基本用法
#include <cstdlib> // rand() 和 srand() 在这里
int r = rand(); // 生成 0~RAND_MAX 之间的整数
int dice = rand() % 6 + 1; // 生成 1~6 的骰子点数
💡 取模公式 ：rand() % n → 0~(n-1)；rand() % n + m → m~(n+m-1)。
🌱 二、srand() 设置种子
srand(time(0)); // 用当前时间做种子
int r = rand() % 100 + 1; // 1~100
有无 srand 效果
不加 srand 每次运行生成相同 的随机数序列 srand(time(0)) 每次运行生成不同 的随机数
⚠️ srand 只需调用一次 （通常放在 main 开头）。如果每次都调用 srand(time(0)) 且间隔很短，time(0) 值不变，生成的随机数会完全相同！
📐 三、生成指定范围的随机数
范围 公式
0 ~ n-1 rand() % n1 ~ n rand() % n + 1a ~ b rand() % (b-a+1) + a
🏷️ 四、RAND_MAX 常量
RAND_MAX 是 rand() 能生成的最大随机数（通常为 32767）。随机数范围：0 ~ RAND_MAX 。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 rand() 函数生成随机数的范围是（ ）。
A. 0~99
B. 0~RAND_MAX
C. 1~100
D. 任意整数
📌 第 2 题 生成 1~100 随机数的表达式是（ ）。
A. rand()%100
B. rand()%100+1
C. rand()%101
D. rand()%99+1
📌 第 3 题 srand(time(0)) 的作用是（ ）。
A. 生成随机数
B. 每次运行生成不同随机数
C. 限制随机数范围
D. 输出时间
📌 第 4 题 不加 srand() 直接调用 rand()，会（ ）。
A. 编译出错
B. 每次运行结果相同
C. 每次运行结果不同
D. 随机数2倍大
📌 第 5 题 生成 a~b 范围的随机整数（含 a,b），正确公式是（ ）。
A. rand()%(b-a)+a
B. rand()%(b-a+1)+a
C. rand()%(b-a+1)+a-1
D. rand()%b+a
📌 第 6 题 time(0) 函数所在的头文件是（ ）。
A. <cmath>
B. <cstdlib>
C. <ctime>
D. <iostream>
🔢 第1课：数据编码——原码、反码、补码
计算机里负数怎么存？为什么补码是标准？一次搞懂三种编码方式！
📖 故事导入
⌚ 小明发现家里的钟只有 0~11 点，没有"负"时间。计算机也一样——它用编码 来表示负数，最巧妙的就是补码 ：减法变加法，电路就简单了！
🧠 一、为什么需要编码？
计算机内部只有 0 和 1。表示正数直接用二进制，但负数 怎么表示？人们设计了三种方案：原码→反码→补码 ，逐步优化。
📐 二、原码（Sign-Magnitude）
最高位表示符号 （0=正，1=负），其余位表示数值。
十进制 原码（8位）
+5 00000101-5 10000101+0 00000000-0 10000000
⚠️ 原码的缺陷 ：①有 +0 和 -0 两个零 ②加减法需要分别处理符号位，电路复杂。
🔄 三、反码（Ones' Complement）
正数不变，负数的每一位取反 （0↔1）。
十进制 反码（8位）
+5 00000101-5 11111010（00000101 取反）
💡 反码规则 ：正数的反码=自身；负数的反码=原码除符号位外逐位取反 。但反码仍有"正负零"问题。
✅ 四、补码（Two's Complement）——现代计算机标准
正数的补码=自身；负数的补码=反码+1。
十进制 补码（8位） 计算过程
+5 00000101原码=补码 -5 11111011反码(11111010)+1 0 00000000唯一！
💡 补码三大优点 ：①0 只有一种表示 ②减法变加法（A-B = A+(-B)的补码）③符号位直接参与运算，电路极简。
🔢 五、补码的数值范围（8位）
编码 范围 个数
原码 -127 ~ +127 255（含两个0） 反码 -127 ~ +127 255（含两个0） 补码 -128 ~ +127 256（一个0）
⚠️ 补码多表示一个负数 ：8位补码范围 -128~127，比原码/反码多一个 -128（10000000）。
📝 六、真题演练 （点击选项作答）
📌 第 1 题 8位二进制原码中，+5 表示为（ ）。
A. 10000101
B. 00000101
C. 11111010
D. 11111011
📌 第 2 题 -5 的8位补码是（ ）。
A. 10000101
B. 11111010
C. 11111011
D. 00000101
📌 第 3 题 补码相比原码和反码的最大优点是（ ）。
A. 表示范围更大
B. 只有一种0的表示
C. 能表示更多正数
D. 不需要运算
📌 第 4 题 8位补码能表示的数值范围是（ ）。
A. -127~127
B. -128~127
C. -127~128
D. -128~128
📌 第 5 题 计算机内部广泛使用补码的根本原因是（ ）。
A. 表示范围最大
B. 减法可用加法实现
C. 编程最简单
D. 最容易被人类理解
📌 第 6 题 -5 的8位反码是（ ）。
A. 10000101
B. 11111010
C. 11111011
D. 00000101
🔣 第2课：进制转换
二进制、八进制、十进制、十六进制——四大进制互转，是信息学竞赛的基本功！
📖 故事导入
🧮 小明看到 0xFF 和 0b1010，一脸茫然。老师说："这就是进制 ——1010 在二进制里是 10，在十进制里是一千零一十。进制不同，值就不同！"
🔢 一、四大进制速览
进制 基数 数码 C++ 前缀 示例
二进制 2 0,1 0b 或 0B0b1010=10 八进制 8 0~7 0012=10 十进制 10 0~9 无 10 十六进制 16 0~9,A~F 0x 或 0X0xA=10
💡 C++ 字面量前缀 ：0b=二进制，0=八进制，0x=十六进制。注意八进制只有一个0 ！
🔄 二、任意进制→十进制（按权展开）
二进制 1011₂ → 十进制：
1×2³ + 0×2² + 1×2¹ + 1×2⁰
= 8 + 0 + 2 + 1 = 11
十六进制 2A₁₆ → 十进制：
2×16¹ + 10×16⁰ = 32 + 10 = 42
💡 公式 ：每位数字 × 基数^位权，再求和。位权从右往左，从0开始。
⬇️ 三、十进制→任意进制（除基取余）
十进制 13 → 二进制：
13÷2=6 余 1
6÷2=3 余 0
3÷2=1 余 1
1÷2=0 余 1
结果（从下往上）：1101₂
⚠️ 除基取余的口诀 ：一直除，商为0停。余数从下往上读 就是结果。最容易犯的错是读反方向！
🔀 四、二/八/十六进制互转（快捷法）
转换 关系 方法
二→八 2³=8 3位一组 ，从右分组二→十六 2⁴=16 4位一组 ，从右分组八→二 每位展开为3位二进制 十六→二 每位展开为4位二进制
💡 二进制 10110100 → 八进制：010/110/100 = 264₈ ；→ 十六进制：1011/0100 = B4₁₆ 。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 二进制数 1101 对应的十进制是（ ）。
A. 11
B. 13
C. 14
D. 15
📌 第 2 题 十进制数 25 对应的二进制是（ ）。
A. 11001
B. 11011
C. 11101
D. 10011
📌 第 3 题 十六进制数 1A 对应的十进制是（ ）。
A. 16
B. 26
C. 28
D. 20
📌 第 4 题 C++ 中，以下哪个表示八进制整数？（ ）
A. 0b101
B. 0123
C. 0xFF
D. 123
📌 第 5 题 二进制转十六进制时，应（ ）。
A. 3位一组
B. 4位一组
C. 5位一组
D. 8位一组
📌 第 6 题 八进制数 17 对应的二进制是（ ）。
A. 1111
B. 10111
C. 10001
D. 1101
⚙️ 第3课：位运算
直接操作二进制位——与、或、异或、移位，速度最快的运算方式！
📖 故事导入
💡 小明发现 x*2 和 x<<1 结果一样！老师说："这就是位运算 ——直接操作二进制位，比普通乘除快得多。"
📊 一、六大位运算符
运算符 名称 规则 示例（a=5,b=3）
&按位与 全1才1 5&3=1 (101&011=001) |按位或 有1则1 5|3=7 (101|011=111) ^按位异或 不同为1 5^3=6 (101^011=110) ~按位取反 0↔1 ~5=-6（补码） <<左移 左移n位=×2ⁿ 5<<2=20 >>右移 右移n位=÷2ⁿ 5>>1=2
💡 口诀 ：&=全1才1，|=有1则1，^=不同为1。左移乘2，右移除2。
🔍 二、位与（&）的经典用法
判断奇偶： n & 1（1=奇数，0=偶数）取低k位： n & ((1<<k)-1)清零特定位： n & ~(1<<k)
⚡ 三、移位运算（<< 和 >>）
操作 等价 示例
x << nx × 2ⁿ 3<<2=12 x >> nx ÷ 2ⁿ（整数除） 13>>2=3
⚠️ 移位优先级很低 ：1<<2+1=1<<3=8，不是(1<<2)+1=5！移位要加括号。
🎯 四、异或（^）的特殊性质
自反性： a ^ a = 0，a ^ 0 = a交换两个变量（不用临时变量）： a^=b; b^=a; a^=b;找唯一出现一次的数： 所有数异或，结果就是那个数
📝 五、真题演练 （点击选项作答）
📌 第 1 题 表达式 5 & 3 的结果是（ ）。
A. 7
B. 1
C. 5
D. 3
📌 第 2 题 表达式 5 | 3 的结果是（ ）。
A. 7
B. 1
C. 5
D. 3
📌 第 3 题 3 << 2 的结果是（ ）。
A. 6
B. 8
C. 12
D. 16
📌 第 4 题 判断整数 n 是偶数的表达式是（ ）。
A. n & 1 == 1
B. n & 1 == 0
C. n | 1 == 0
D. n ^ 1 == 1
📌 第 5 题 表达式 1 << 3 的结果是（ ）。
A. 3
B. 6
C. 8
D. 9
📌 第 6 题 关于异或运算，正确的是（ ）。
A. a^a=1
B. a^0=0
C. a^a=0
D. a^b=b^a不成立
📐 第4课：算法的概念与描述
算法就像菜谱——步骤清晰、结果确定。GESP 三级要求理解算法特征与复杂度概念。
📖 故事导入
🍳 小红学做番茄炒蛋：①打蛋 ②切番茄 ③热油 ④炒蛋 ⑤加番茄 ⑥调味。这就是算法 ——解决特定问题的有限步骤序列 。
🧠 一、算法的五大特征
特征 含义
有穷性 必须在有限步内结束，不能无限循环 确定性 每一步含义明确，没有歧义 输入 有零个或多个输入 输出 至少有一个输出（结果） 可行性 每一步都能用基本操作实现
💡 记忆口诀：有穷确定可入出 。算法的每一步都必须是明确的、能在有限时间内完成的。
📊 二、时间复杂度初探
时间复杂度 衡量算法随数据量增长的运行时间趋势 （看最坏情况）。
复杂度 名称 n=1000 时
O(1) 常数 1 O(log n) 对数 ~10 O(n) 线性 1000 O(n²) 平方 1,000,000
⚠️ GESP 三级只要求常识性理解 ：单层循环 O(n)，双层嵌套 O(n²)。不要求精确计算。
🔍 三、算法的描述方式
自然语言 ：用日常语言描述（易读但不精确）流程图 ：图形化表示（直观，适合简单逻辑）伪代码 ：接近编程语言的半正式描述（GESP 常用）程序代码 ：C++ 等可直接编译运行✅ 四、好算法的标准
正确性 ——结果必须对可读性 ——别人能看懂健壮性 ——能处理非法输入效率 ——时间和空间开销小
📝 五、真题演练 （点击选项作答）
📌 第 1 题 算法的基本特征不包括 （ ）。
A. 有穷性
B. 确定性
C. 无限性
D. 可行性
📌 第 2 题 以下关于算法输入输出的说法，正确 的是（ ）。
A. 算法必须有输入
B. 算法可以没有输出
C. 算法可以没有输入
D. 输入输出都必须有
📌 第 3 题 双重循环（外层n次，内层n次）的时间复杂度是（ ）。
A. O(1)
B. O(n)
C. O(n^2)
D. O(log n)
📌 第 4 题 单层循环遍历n个元素，复杂度是（ ）。
A. O(1)
B. O(n)
C. O(n²)
D. O(log n)
📌 第 5 题 关于算法描述方式，错误 的是（ ）。
A. 可用自然语言
B. 可用流程图
C. 只能用C++
D. 可用伪代码
📌 第 6 题 算法的五个特征中包括（ ）。
A. 美观性
B. 有穷性
C. 无限性
D. 复杂性
📚 第5课：C++ 一维数组基本应用
100 个变量太麻烦？数组一次搞定！定义、遍历、查找——数组是竞赛基本功。
📖 故事导入
📊 老师要统计全班 40 人的成绩。小明不想定义 score1~score40 四十个变量，于是拿出数组 ：int score[40]; 一行搞定！
📐 一、数组的定义与初始化
int a[5]; // 定义5个元素的数组（值未定义）
int b[5] = {1,2,3,4,5}; // 定义并初始化
int c[5] = {0}; // 全部初始化为0
int d[] = {1,2,3}; // 自动推断大小为3
💡 下标从 0 开始 ，长度为 n 的数组有效下标是 0~n-1。越界访问不报错但危险 ！
🔁 二、数组的遍历
int a[5] = {10, 20, 30, 40, 50};
for (int i = 0; i < 5; i++) {
cout << a[i] << " "; // 输出 10 20 30 40 50
}
遍历 = for循环 + 下标访问 ，i 从 0 到 n-1。
🔍 三、常见操作
操作 方法
求和 遍历累加 sum += a[i] 求最大值 遍历比较 if(a[i]>mx)mx=a[i] 查找 遍历判断 if(a[i]==target) 逆序输出 从 n-1 到 0 遍历
⚠️ 数组大小必须是常量 ：int n=100; int a[n]; 在某些 C++ 版本中可能报错。GESP 建议用 const int N=100; 或固定大小。
📊 四、数组初始化要点
int a[5] = {}; → 全部为 0int a[5] = {1,2}; → {1,2,0,0,0}，不足补 0局部数组不初始化，值是随机的 全局数组默认全部为 0
📝 五、真题演练 （点击选项作答）
📌 第 1 题 数组 int a[5]; 有效下标范围是（ ）。
A. 1~5
B. 0~5
C. 0~4
D. 1~4
📌 第 2 题 int a[5]={1,2}; 则 a[3] 的值是（ ）。
A. 1
B. 2
C. 0
D. 随机值
📌 第 3 题 求数组最大值的核心逻辑是（ ）。
A. sum+=a[i]
B. if(a[i]>mx)mx=a[i]
C. swap(a[i],a[i+1])
D. a[i]=0
📌 第 4 题 以下关于数组的说法，错误 的是（ ）。
A. 下标从0开始
B. 所有元素类型相同
C. 数组大小必须为常量
D. 数组越界一定报错
📌 第 5 题 逆序遍历长度为 n 的数组，for 循环应写（ ）。
A. for(i=n;i>0;i--)
B. for(i=n-1;i>=0;i--)
C. for(i=n;i>=0;i--)
D. for(i=0;i<n;i++)
📌 第 6 题 int a[5]={0}; 和 int a[5]={}; 的效果（ ）。
A. 完全不同
B. 都全为0
C. 前者全0后者随机
D. 前者随机后者全0
🔤 第6课：字符串及其函数
string 是 C++ 最方便的数据类型之一！拼接、查找、截取——字符串操作全掌握。
📖 故事导入
✉️ 小明要写一个"欢迎 XXX 同学"的程序。用 char 数组太麻烦，用 string 直接用 + 拼接：string s = "欢迎 " + name + " 同学"; ——简单优雅！
📐 一、string 基本操作
#include <string>
string s = "Hello";
string t = "World";
string u = s + " " + t; // "Hello World"
int len = s.length(); // len = 5
char c = s[0]; // c = 'H'
💡 string 用 + 拼接 ，用 .length() 或 .size() 获取长度。下标从 0 开始。
🔧 二、常用成员函数
函数 功能 示例（s="Hello"）
length()获取长度 s.length()=5 substr(pos,len)截取子串 s.substr(1,3)="ell" find(str)查找子串位置 s.find("ll")=2 erase(pos,len)删除子串 s.erase(1,2)→"Ho" insert(pos,str)插入 s.insert(1,"i")→"Hiello"
⚠️ find() 找不到时返回 string::npos （一个很大的数），不是 -1。判断应写 if(s.find(x) != string::npos)。
🔄 三、字符串遍历
string s = "ABC";
for (int i = 0; i < s.length(); i++) {
cout << s[i]; // 输出 A B C
}
// 或使用范围for（C++11）
for (char c : s) cout << c;
📊 四、string vs char 数组
对比 string char[]
长度 动态可变 固定 赋值 s = t; 直接赋值 需 strcpy 比较 s == t; 直接用== 需 strcmp 拼接 s + t; 用+ 需 strcat
📝 五、真题演练 （点击选项作答）
📌 第 1 题 获取字符串 s 长度的正确方法是（ ）。
A. len(s)
B. s.length()
C. s.len()
D. sizeof(s)
📌 第 2 题 string s="Hello"; s.substr(1,2) 的结果是（ ）。
A. "He"
B. "el"
C. "ell"
D. "lo"
📌 第 3 题 s.find("ab") 找不到时，返回（ ）。
A. -1
B. 0
C. string::npos
D. s.length()
📌 第 4 题 string s="AB", t="CD"; s+t 的结果是（ ）。
A. "ABCD"
B. "AB CD"
C. "AB+CD"
D. 编译错误
📌 第 5 题 string s="Hello"; 则 s[1] 的值是（ ）。
A. H
B. e
C. l
D. o
📌 第 6 题 关于 string，错误 的是（ ）。
A. 长度可动态变化
B. 可用==比较
C. 可用+拼接
D. 必须用strcmp比较
🔍 第7课：枚举法
把所有可能都试一遍——枚举法是竞赛中最直观的算法策略！
📖 故事导入
🔑 小明忘了密码锁的两位数字密码。他从 00 试到 99，试了 100 次终于打开了。这就是枚举法（穷举法） ——把答案可能的范围全部试一遍！
🧠 一、什么是枚举法？
枚举法 就是逐一列举所有可能的情况，逐个检验是否满足条件。核心要素：
确定搜索范围 ——上下界不能太大验证条件 ——判断每个候选是否满足要求复杂度 O(N) ——N 为搜索范围大小💡 枚举法三要素 ：范围 + 条件 + 遍历。关键是"范围不能太大"——否则会超时。
⭐ 二、经典例题：水仙花数
水仙花数 = 三位数，各位数字的立方和等于自身。如 153 = 1³+5³+3³。
for (int n = 100; n <= 999; n++) {
int a = n / 100; // 百位
int b = n / 10 % 10; // 十位
int c = n % 10; // 个位
if (a*a*a + b*b*b + c*c*c == n) {
cout << n << endl; // 输出水仙花数
}
}
⚠️ 拆位运算 ：百位=n/100，十位=n/10%10，个位=n%10。这是 GESP 三级高频考点。
🔢 三、经典例题：百钱买百鸡
公鸡 5 元/只，母鸡 3 元/只，小鸡 1 元 3 只。100 元买 100 只鸡，各几只？
for (int g = 0; g <= 20; g++) // 公鸡最多20只
for (int m = 0; m <= 33; m++) // 母鸡最多33只
for (int x = 0; x <= 100; x+=3) // 小鸡必须是3的倍数
if (g+m+x==100 && 5*g+3*m+x/3==100)
cout << g << " " << m << " " << x << endl;
📊 四、枚举法的优化
优化策略 说明
缩小范围 分析问题，尽可能缩小搜索边界 剪枝 提前排除不可能的分支 减少循环层数 最后一层可用计算代替（如小鸡=100-公鸡-母鸡）
📝 五、真题演练 （点击选项作答）
📌 第 1 题 枚举法的核心思想是（ ）。
A. 只找最优解
B. 逐一列举所有可能
C. 使用递归
D. 动态规划
📌 第 2 题 三位水仙花数的枚举范围是（ ）。
A. 0~999
B. 100~999
C. 1~999
D. 100~1000
📌 第 3 题 拆出整数 n 的十位数字，表达式是（ ）。
A. n%10
B. n/10
C. n/10%10
D. n%100
📌 第 4 题 百钱百鸡问题中，公鸡数量枚举上界是（ ）。
A. 100
B. 50
C. 20
D. 10
📌 第 5 题 关于枚举法，正确 的是（ ）。
A. 所有问题都适合枚举
B. 枚举法时间复杂度一定很高
C. 范围小时简单有效
D. 枚举法不需要验证条件
📌 第 6 题 153 是不是水仙花数？（ ）
A. 是，153=1³+5³+3³
B. 不是
C. 要看具体情况
D. 只有3位判断
🎮 第8课：模拟法
按题目描述一步步模拟执行过程——模拟法是信息学竞赛最常用的策略之一！
📖 故事导入
🎲 玩大富翁时你不需要用公式计算——只需要按照规则掷骰子、走格子、执行事件。编程也一样：模拟法 = 照规则一步步执行 ，让程序"走一遍"整个过程。
🧠 一、什么是模拟法？
模拟法 就是根据题目描述的规则，一步一步模拟整个过程的执行 ，最终得到答案。
要点 说明
理解规则 把题目描述的每一步用代码表达 变量设计 用变量记录模拟过程的状态 逐步执行 按照规则逐个步骤推进 输出结果 模拟结束后输出答案
💡 模拟法 vs 枚举法 ：枚举试所有可能 ，模拟走一条路径 。模拟像读剧本演一遍。
⭐ 二、经典例题：角谷猜想
任给正整数 n：若偶数则除2，若奇数则乘3加1，直到 n=1。输出每一步。
int n;
cin >> n;
while (n != 1) {
if (n % 2 == 0) n = n / 2;
else n = n * 3 + 1;
cout << n << " ";
}
🪙 三、经典例题：硬币翻转
n 枚硬币正面朝上，第 i 轮翻所有编号为 i 倍数的硬币。问最终哪些正面朝上？
bool coin[101] = {true}; // true=正面
for (int i = 1; i <= n; i++) // n 轮
for (int j = i; j <= n; j += i) // i 的倍数
coin[j] = !coin[j]; // 翻转
📊 四、模拟法的关键技巧
状态数组 ：用数组记录模拟过程中的状态变化循环推进 ：for/while 按轮次或时间推进条件分支 ：根据当前状态选择不同操作注意边界 ：模拟的起始和终止条件要写对
⚠️ 模拟法不是"简单" ：规则复杂时容易漏细节。建议先在纸上走通小规模例子，再写代码。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 模拟法的核心是（ ）。
A. 使用数学公式直接计算
B. 按规则逐步执行过程
C. 枚举所有可能答案
D. 使用递归分解问题
📌 第 2 题 角谷猜想中，若 n=3，下一步 n 变为（ ）。
A. 1
B. 6
C. 10
D. 5
📌 第 3 题 硬币翻转问题中，第 2 轮会翻转哪些硬币？（ ）
A. 所有硬币
B. 编号为奇数的
C. 编号为2的倍数的
D. 编号为质数的
📌 第 4 题 模拟法中记录状态的常用方式是（ ）。
A. 只用单个变量
B. 用数组
C. 用文件
D. 用指针
📌 第 5 题 关于模拟法，正确 的是（ ）。
A. 只能用于数学问题
B. 不能配合其他算法
C. 适合规则明确的问题
D. 复杂度一定是O(1)
📌 第 6 题 以下问题最适合 用模拟法的是（ ）。
A. 求n的阶乘
B. 按规则玩一局游戏
C. 排序一组数
D. 统计字母频率
📦 第1课：函数的定义与调用
把重复的代码"打包"成函数——一次定义，反复使用。函数是编程的乐高积木！
📖 故事导入
🏭 小明写程序时需要多次算阶乘。每次都重写一遍代码太累了！于是他把阶乘"封装"成一个 函数 ——int fac(int n)，以后只需要一行 fac(5) 就搞定。
📐 一、函数的定义
返回类型 函数名(参数列表) {
// 函数体
return 返回值;
}
int add(int a, int b) { // 定义加法函数
return a + b;
}
四要素 ：返回类型、函数名、参数列表、函数体。有返回值的函数必须写 return。
📞 二、函数的调用
int result = add(3, 5); // result = 8
cout << add(10, 20); // 输出 30
💡 实参 vs 形参 ：定义时的参数叫形参 （int a, int b），调用时传入的值叫实参 （3, 5）。实参的值拷贝 给形参。
⚡ 三、void 函数（无返回值）
void printHello() { // 无参数，无返回值
cout << "Hello!" << endl;
// 没有 return（或写 return;）
}
void 函数只执行操作不返回值，可以省略 return 或写 return;。
✅ 四、函数的优势
优势 说明
代码复用 避免重复写相同逻辑 模块化 把大问题拆成小函数，便于管理 易调试 每个函数可单独测试 可读性 函数名表达意图（如 isPrime）
⚠️ 函数须先声明/定义后调用 。如果把函数写在 main() 后面，需先在前面写函数声明 （原型）：int add(int a, int b);
📝 五、真题演练 （点击选项作答）
📌 第 1 题 C++ 中定义函数时，必须 指定的是（ ）。
A. 函数名和参数名
B. 返回类型和函数名
C. 参数名和返回值
D. 函数名和参数默认值
📌 第 2 题 关于形参和实参，正确的是（ ）。
A. 形参是调用时传入的值
B. 实参是定义时的变量
C. 实参的值拷贝给形参
D. 形参改变会影响实参
📌 第 3 题 void 类型的函数（ ）。
A. 必须有return语句
B. 不能有任何参数
C. 不返回任何值
D. 必须有至少一个参数
📌 第 4 题 int f(int x){return x*x;} 调用 f(3) 的结果是（ ）。
A. 6
B. 9
C. 3
D. 0
📌 第 5 题 以下关于函数说法错误 的是（ ）。
A. 函数可被多次调用
B. 函数名不能与关键字同名
C. main也是函数
D. 函数必须写在main前面
📌 第 6 题 调用函数时，参数传递的方式是（ ）。
A. 引用传递
B. 值传递（拷贝）
C. 指针传递
D. 全局传递
🔄 第2课：函数参数传递
传值、传引用、传指针——三种参数传递方式，各有各的用武之地！
📖 故事导入
📋 小明想写一个 swap 函数交换两个变量的值，写完发现根本没交换！原来传值 只拷贝了副本，改不了原变量。改用传引用 （加 &）才搞定。
📊 一、三种传递方式速览
方式 语法 是否影响实参 开销
传值 void f(int x)否 （拷贝）拷贝开销 传引用 void f(int &x)是 （别名）无拷贝 传指针 void f(int *x)是 （通过地址）无拷贝
📦 二、传值（Pass by Value）
void addOne(int x) { x = x + 1; }
int a = 5;
addOne(a);
cout << a; // 输出 5（a 没变！）
💡 传值时形参是实参的拷贝 。函数内修改形参不影响实参 。适合只需要"读"不需要"改"的场景。
🔗 三、传引用（Pass by Reference）
void swap(int &a, int &b) { int t=a; a=b; b=t; }
int x=3, y=5;
swap(x, y); // x=5, y=3（成功交换！）
⚠️ 传引用的形参就是实参的别名 ，函数内修改直接影响原变量。swap 必须用引用！
👉 四、传指针（Pass by Pointer）
void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }
int x=3, y=5;
swap(&x, &y); // 传地址，效果同上
传指针本质也是地址拷贝，但通过解引用 * 可以修改原变量。调用时需要 & 取地址。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 C++ 默认的参数传递方式是（ ）。
A. 传引用
B. 传值
C. 传指针
D. 传数组
📌 第 2 题 void f(int &x){x=10;} int a=5; f(a); 后 a 的值是（ ）。
A. 5
B. 10
C. 0
D. 不确定
📌 第 3 题 swap 函数交换两个整数，参数应使用（ ）。
A. 传值
B. 传引用或传指针
C. 只用return
D. 全局变量
📌 第 4 题 传引用的主要优势是（ ）。
A. 比传值速度慢
B. 避免拷贝大对象
C. 必须用&取地址
D. 无法修改原变量
📌 第 5 题 void f(int x){x=100;} int a=5; f(a); 后 a 的值是（ ）。
A. 100
B. 5
C. 0
D. 不确定
📌 第 6 题 以下关于传值说法正确 的是（ ）。
A. 函数内修改会影响实参
B. 形参和实参共用内存
C. 形参是实参的副本
D. 传值比传引用快
👉 第3课：C++ 指针基础
指针是C++的灵魂——它存储的是"地址"而不是值。理解指针，才算真正入门C++！
📖 故事导入
🏠 小明家的地址是"阳光路 5 号"。你不需要把整个房子搬过来——知道地址 就能找到它。指针就是变量的"地址卡" ，通过地址间接访问数据。
📐 一、指针的定义
int a = 10;
int *p = &a; // p 指向 a 的地址
// *用于声明指针，&用于取地址
符号 名称 含义
&取地址运算符 获取变量的内存地址 *解引用运算符 获取指针指向的值
🔍 二、指针的核心操作
int a = 10;
int *p = &a; // p 存 a 的地址
cout << *p; // 输出 10（访问 a）
*p = 20; // 修改 a 为 20（通过指针）
cout << a; // 输出 20
💡 *p 的双重含义 ：声明时 int *p 表示"p是指针"；使用时 *p 表示"p指向的值"。
⚠️ 三、常见陷阱
陷阱 说明
野指针 未初始化的指针指向随机地址，访问崩溃 空指针 指向 NULL/nullptr，解引用崩溃 内存泄漏 new 出的内存未 delete
⚠️ 指针三不 ：不初始化不用、不判空不解引用、不配对(new/delete)不写。GESP 四级重点考察指针安全。
🔄 四、指针与数组
int arr[5] = {1,2,3,4,5};
int *p = arr; // arr 本身就是首地址
cout << *p; // 输出 1
cout << *(p+2); // 输出 3（等价于 arr[2]）
数组名可以当作指向首元素的常量指针 使用。指针+整数 = 向后偏移。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 int a=10; int *p=&a; 则 *p 的值是（ ）。
A. a的地址
B. 10
C. 指针p的地址
D. 0
📌 第 2 题 取变量 a 地址的运算符是（ ）。
A. *
B. &
C. #
D. @
📌 第 3 题 int *p; cout<<*p; 可能发生（ ）。
A. 输出0
B. 输出随机值或崩溃
C. 输出p的地址
D. 编译错误
📌 第 4 题 int arr[5]; int *p=arr; 则 *(p+2) 等价于（ ）。
A. arr[1]
B. arr[2]
C. arr[3]
D. p[2]
📌 第 5 题 判断指针 p 是否为空的正确写法是（ ）。
A. if(p==0)
B. if(p==NULL)
C. if(!p)
D. 以上都可以
📌 第 6 题 关于指针说法错误 的是（ ）。
A. 指针存的是地址
B. 指针有自己的地址
C. 指针类型必须与指向变量类型一致
D. 指针不能指向另一个指针
🏗️ 第4课：C++ 结构体
把姓名、年龄、成绩打包成一个"学生"——struct 让你自定义复合数据类型！
📖 故事导入
📋 小明要管理全班学生的姓名、年龄、成绩。三个数组各管各的容易乱。老师说："用 struct 把它们打包成一个'学生'类型，一个数组就能装下所有信息！"
📐 一、结构体的定义
struct Student {
string name;
int age;
double score;
}; // 注意分号！
Student s1; // 创建结构体变量
struct 把多个不同类型 的数据组合成一个新类型。每个变量叫成员 （member）。
🔍 二、成员的访问
Student s;
s.name = "小明"; // 用 . 访问成员
s.age = 12;
s.score = 95.5;
Student *p = &s;
p->name = "小红"; // 指针用 -> 访问
💡 . vs -> ：普通变量用点 (.) ，指针用箭头 (->) 。p->name 等价于 (*p).name。
📊 三、结构体数组
Student stu[100];
for (int i = 0; i < n; i++) {
cin >> stu[i].name >> stu[i].age >> stu[i].score;
}
// 查找最高分
int maxIdx = 0;
for (int i = 1; i < n; i++)
if (stu[i].score > stu[maxIdx].score)
maxIdx = i;
🎯 四、结构体与排序
// 按成绩从高到低排序
sort(stu, stu + n, [](Student a, Student b) {
return a.score > b.score;
});
⚠️ 结构体不能直接用 > 比较 ，需要自定义比较规则（写比较函数或 lambda）。GESP 四级常考。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 定义结构体时，结尾需要（ ）。
A. 逗号
B. 分号
C. 冒号
D. 什么都不需要
📌 第 2 题 访问结构体变量的成员使用（ ）。
A. ->
B. .
C. ::
D. ,
📌 第 3 题 Student *p; 访问 name 成员用（ ）。
A. p.name
B. p->name
C. *p.name
D. &p.name
📌 第 4 题 结构体的主要作用是（ ）。
A. 代替数组
B. 组合不同类型数据
C. 存储大量数据
D. 代替函数
📌 第 5 题 struct 中的成员默认访问权限是（ ）。
A. private
B. protected
C. public
D. 没有默认
📌 第 6 题 关于结构体数组说法正确 的是（ ）。
A. 结构体数组每个元素是独立的变量
B. 结构体不能组成数组
C. 结构体数组不能排序
D. 结构体数组只能用指针访问
📊 第5课：二维数组与多维数组
一维数组是一条线，二维数组是一个面——矩阵运算、棋盘游戏，二维数组来搞定！
📖 故事导入
♟️ 小明要写一个五子棋程序。棋盘 15×15 的格子，用一维数组太别扭了。用二维数组 ：int board[15][15];——行、列一目了然！
📐 一、二维数组的定义与初始化
int a[3][4]; // 3行4列
int b[3][4] = { // 逐行初始化
{1,2,3,4},
{5,6,7,8},
{9,10,11,12}
};
int c[3][4] = {0}; // 全部初始化为0
💡 二维数组按行优先 存储。a[i][j] 表示第 i 行第 j 列（都从0开始）。
🔁 二、二维数组的遍历
for (int i = 0; i < 3; i++) { // 外层循环-行
for (int j = 0; j < 4; j++) { // 内层循环-列
cout << a[i][j] << " ";
}
cout << endl; // 每行结束换行
}
双层 for 遍历 ，外层走行，内层走列。
🔢 三、常见操作
操作 方法
矩阵加法 c[i][j]=a[i][j]+b[i][j]矩阵转置 b[j][i]=a[i][j]对角线 i==j（主对角线），i+j==n-1（副对角线） 边界判断 i==0||i==n-1||j==0||j==n-1
⚠️ 越界访问 ：二维数组同样不检查越界。访问 a[3][0]（第4行）在 int a[3][4] 中是越界的。
📝 五、真题演练 （点击选项作答）
📌 第 1 题 int a[3][4]; 共有（ ）个元素。
A. 7
B. 12
C. 3
D. 4
📌 第 2 题 int a[2][3]={1,2,3,4,5,6}; a[1][2] 的值是（ ）。
A. 3
B. 5
C. 6
D. 4
📌 第 3 题 遍历 3 行 4 列的二维数组，内层循环范围是（ ）。
A. i<3
B. i<4
C. j<3
D. j<4
📌 第 4 题 矩阵转置的核心操作是（ ）。
A. a[i][j]=b[i][j]
B. b[j][i]=a[i][j]
C. a[i][j]=a[j][i]
D. b[i][j]=b[j][i]
📌 第 5 题 二维数组在内存中的存储顺序是（ ）。
A. 列优先
B. 行优先
C. 随机存储
D. 按对角线
📌 第 6 题 int a[3][4]={0}; 的作用是（ ）。
A. a[0][0]=0其余随机
B. 全部元素为0
C. 编译错误
D. 只初始化第一行
🔗 第6课：递推算法
从已知推到未知——递推是竞赛最常用的算法思想之一，斐波那契数列就是经典例子！
📖 故事导入
🐰 一对兔子每月生一对小兔子，小兔子两个月后也会生兔子。第 n 个月有几对？这个月 = 上个月 + 上上个月 ——这就是斐波那契递推！
🧠 一、递推的核心思想
递推 = 从已知推未知 。三要素：初始条件 + 递推公式 + 循环推进 。
🐰 二、斐波那契数列
int fib[50];
fib[1] = fib[2] = 1; // 初始值
for (int i = 3; i <= n; i++)
fib[i] = fib[i-1] + fib[i-2]; // 递推公式
⬆️ 三、经典题：走楼梯
一次走 1 级或 2 级，n 级台阶有几种走法？
dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
💡 走到第 n 级 = 从 n-1 走 1 步 + 从 n-2 走 2 步。所以 dp[n]=dp[n-1]+dp[n-2]。
📊 四、递推 vs 递归
递推 递归
方向 从小到大（循环） 从大到小（自调用） 效率 O(n)，快 O(2ⁿ)，慢（无记忆化） GESP推荐 递推优先 慎用
⚠️ 递推用循环+数组 ，递归用函数自调用。GESP 四级推荐递推，效率高无重复计算。
📝 五、真题演练 （点击选项作答）
📌 第1题 斐波那契数列第4项是（ ）。
A. 1
B. 2
C. 3
D. 5
📌 第2题 递推算法的核心是（ ）。
A. 猜测答案
B. 从已知值推导未知值
C. 随机尝试
D. 排序数组
📌 第3题 上n级台阶（每次1或2级），走法数满足（ ）。
A. dp[n]=dp[n-1]*dp[n-2]
B. dp[n]=dp[n-1]+dp[n-2]
C. dp[n]=n
D. dp[n]=2^n
📌 第4题 递推一般使用（ ）实现。
A. 函数自调用
B. 循环
C. 随机数
D. 文件操作
📌 第5题 递推相比递归的优势是（ ）。
A. 代码更短
B. 效率更高避免重复计算
C. 总能得到正确答案
D. 不需要初始条件
📌 第6题 fib[1]=1,fib[2]=1,fib[i]=fib[i-1]+fib[i-2]; fib[5]=（ ）。
A. 3
B. 5
C. 8
D. 13
📋 第7课：排序概念与稳定性
把一堆数从小到大排好——排序是最基础也最重要的算法操作。稳定性和时间复杂度是关键！
📖 故事导入
📚 图书馆按编号把书从小到大排列。如果两本书编号相同，原来在前面的还应该在前面 ——这就是稳定排序 。
🧠 一、排序的基本概念
升序 ：从小到大（默认）降序 ：从大到小关键字 ：用来比较的依据（如成绩、年龄）⚖️ 二、稳定性
类型 含义 示例
稳定排序 相等元素的相对顺序不变 冒泡、插入、归并 不稳定排序 相等元素相对顺序可能改变 选择、快速、堆
💡 稳定 ≠ 正确 。稳定是一种特性，不影响排序结果正确性，但在多关键字排序时很重要。
📊 三、常见排序算法一览
算法 平均复杂度 稳定性
冒泡排序 O(n²) 稳定 选择排序 O(n²) 不稳定 插入排序 O(n²) 稳定 快速排序 O(n log n) 不稳定
⚠️ GESP 常考 ：①冒泡/插入=稳定 ②选择=不稳定 ③复杂度 O(n²) vs O(n log n)。
📝 五、真题演练 （点击选项作答）
📌 第1题 以下属于稳定排序算法的是（ ）。
A. 选择排序
B. 冒泡排序
C. 快速排序
D. 堆排序
📌 第2题 排序算法的"稳定性"指的是（ ）。
A. 代码不会崩溃
B. 相等元素相对顺序不变
C. 结果永远相同
D. 速度保持恒定
📌 第3题 以下排序算法不稳定 的是（ ）。
A. 冒泡排序
B. 插入排序
C. 选择排序
D. 归并排序
📌 第4题 冒泡排序的平均时间复杂度是（ ）。
A. O(n)
B. O(n log n)
C. O(n²)
D. O(2ⁿ)
📌 第5题 升序排序表示（ ）。
A. 从大到小排列
B. 从小到大排列
C. 随机排列
D. 只排一部分
📌 第6题 关于排序说法正确 的是（ ）。
A. 不稳定排序结果不正确
B. O(n²)一定比O(n log n)慢
C. 稳定排序在多关键字排序时有用
D. 选择排序是稳定的
🔢 第8课：基础排序算法
冒泡、选择、插入——三大基础排序算法，GESP 四级必须能手写代码！
🫧 一、冒泡排序（Bubble Sort）
思想 ：相邻元素两两比较，大的往后"冒"。每轮把最大值推到末尾。
for (int i = 0; i < n-1; i++) // n-1 轮
for (int j = 0; j < n-1-i; j++) // 每轮比较范围缩小
if (a[j] > a[j+1])
swap(a[j], a[j+1]);
💡 冒泡特征 ：稳定、O(n²)。优化：如果某轮没有交换，说明已排好可提前结束。
👆 二、选择排序（Selection Sort）
思想 ：每轮找最小值（或最大值），放到该轮最前面。
for (int i = 0; i < n-1; i++) {
int minIdx = i;
for (int j = i+1; j < n; j++)
if (a[j] < a[minIdx]) minIdx = j;
swap(a[i], a[minIdx]);
}
⚠️ 选择排序不稳定 ：跨元素交换可能打乱相等元素的顺序。复杂度 O(n²)。
📥 三、插入排序（Insertion Sort）
思想 ：像打扑克牌理牌，把新元素插入已排序部分的正确位置。
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;
}
💡 插入排序稳定 。对基本有序 的数据效率接近 O(n)。GESP 四级三种排序都要能手写。
📝 五、真题演练 （点击选项作答）
📌 第1题 冒泡排序每一轮把（ ）放到末尾。
A. 最小值
B. 最大值
C. 中间值
D. 随机值
📌 第2题 选择排序的核心操作是（ ）。
A. 相邻交换
B. 找最小值并交换
C. 插入到合适位置
D. 二分查找
📌 第3题 以下不稳定 的排序算法是（ ）。
A. 冒泡排序
B. 插入排序
C. 选择排序
D. 以上都稳定
📌 第4题 三种基础排序中，对基本有序数据效率最高的是（ ）。
A. 冒泡排序
B. 选择排序
C. 插入排序
D. 都一样
📌 第5题 选择排序比较次数和交换次数分别是（ ）。
A. 都是O(n²)
B. 比较O(n²)交换O(n)
C. 比较O(n)交换O(n²)
D. 都是O(n)
📌 第6题 n=1000时，O(n²)约执行（ ）次基本操作。
A. 1000
B. 10000
C. 1000000
D. 1000000000
⏱️ 第9课：算法时间复杂度与空间复杂度
用 O() 衡量算法效率——同样的结果，不同的算法执行速度可能差成千上万倍！
📖 故事导入
⚡ n=10 时 O(n²) 执行 100 次，O(n) 执行 10 次——差 10 倍。n=10000 时 O(n²) 执行 1 亿次，O(n log n) 才 13 万次——差 770 倍 ！复杂度决定生死。
📐 一、时间复杂度 O(n)
大 O 表示法 ：描述算法执行次数随数据规模增长的趋势。忽略常数和低阶项 。
复杂度 名称 n=1000 时 实例
O(1) 常数 1 数组下标访问 O(log n) 对数 ~10 二分查找 O(n) 线性 1000 遍历数组 O(n log n) 线性对数 ~10000 快速/归并排序 O(n²) 平方 1000000 冒泡/选择/插入
🔍 二、如何计算时间复杂度
// O(n): 一层循环
for(int i=0;i<n;i++) sum+=a[i];
// O(n²): 两层嵌套循环
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) cnt++;
// O(log n): 每次减半
while(n>1) n/=2;
💡 经验法则 ：一层循环→O(n)，两层嵌套→O(n²)，二分→O(log n)，循环内二分→O(n log n)。
💾 三、空间复杂度
算法使用的额外内存空间 。通常关注数组等额外存储。如冒泡排序只用几个临时变量，空间复杂度 O(1) （原地排序）。
⚠️ GESP 四级常考 ：给一段代码判断时间复杂度。重点区分 O(n) / O(n²) / O(log n) / O(n log n)。
📝 五、真题演练 （点击选项作答）
📌 第1题 以下时间复杂度最高的是（ ）。
A. O(1)
B. O(n)
C. O(n log n)
D. O(n²)
📌 第2题 for(i=0;i<n;i++) sum++; 的时间复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
📌 第3题 两层嵌套循环各执行n次，复杂度是（ ）。
A. O(n)
B. O(2n)
C. O(n²)
D. O(n log n)
📌 第4题 while(n>1){n/=2;} 的时间复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
📌 第5题 冒泡排序的空间复杂度是（ ）。
A. O(1)
B. O(n)
C. O(n²)
D. O(n log n)
📌 第6题 n=10⁶时，O(n²)约执行（ ）次。
A. 10⁶
B. 10⁹
C. 10¹²
D. 10³
📁 第10课：文件重定向与输入输出流
freopen 把输入输出从键盘/屏幕重定向到文件——竞赛评测的底层机制，必须掌握！
📖 故事导入
🏆 GESP 考试时，OJ 评测系统不会用键盘给你输入数据——它从文件读，把输出写到文件比对。freopen 就是让程序从文件读写！
📐 一、freopen 重定向
#include <cstdio>
int main() {
// 将标准输入重定向到文件
freopen("input.txt", "r", stdin);
// 将标准输出重定向到文件
freopen("output.txt", "w", stdout);
int n; cin >> n; // 从 input.txt 读
cout << n * 2 << endl; // 写到 output.txt
return 0;
}
参数 含义
第一个 文件名（"input.txt"） 第二个 模式："r"读 / "w"写 第三个 流：stdin / stdout / stderr
💡 freopen 之后 cin 自动从文件读，cout 自动写到文件。无需修改其他代码 。
🔄 二、输入输出流基础
#include <iostream>
using namespace std;
// cin >> 读取（空格/换行分隔）
int a, b; cin >> a >> b;
// getline 读取整行（含空格）
string line; getline(cin, line);
// cout << 输出
cout << a << " " << b << endl;
⚠️ 注意 ：使用 freopen 需要 #include <cstdio>。GESP 四级考场上如果题目要求文件读写，必须先 freopen。
📝 五、真题演练 （点击选项作答）
📌 第1题 freopen 的头文件是（ ）。
A. <iostream>
B. <cstdio>
C. <fstream>
D. <string>
📌 第2题 freopen("in.txt","r",stdin) 中第二个参数表示（ ）。
A. 文件名
B. 读模式
C. 写模式
D. 追加模式
📌 第3题 freopen 后 cin >> n 从（ ）读取。
A. 键盘
B. 文件
C. 内存
D. 网络
📌 第4题 getline 的作用是（ ）。
A. 读取一个整数
B. 读取一整行含空格
C. 输出一行
D. 关闭文件
📌 第5题 cout << endl 的作用是（ ）。
A. 换行
B. 换行并刷新缓冲区
C. 清屏
D. 结束程序
📌 第6题 使用 freopen 后想恢复键盘输入应（ ）。
A. 不用恢复
B. fclose
C. 重新 freopen 到 CON
D. 无法恢复
🛡️ 第11课：异常处理基础
try...catch 让程序优雅地处理错误，而不是直接崩溃——写出健壮C++程序的必修课！
📖 故事导入
💥 除法时除数为 0，程序直接崩溃。能不能"捕获"这个错误，提示用户重新输入？try...catch 就是来拯救程序的！
🎯 一、try...catch 基本语法
try {
// 可能出错的代码
int a, b; cin >> a >> b;
if (b == 0) throw "除数不能为0！";
cout << a / b;
} catch (const char* msg) {
// 捕获异常并处理
cout << "错误：" << msg;
}
关键字 作用
try 包裹可能出错的代码块 throw 抛出异常（可以是任意类型） catch 捕获并处理异常
🔢 二、常见异常类型
// 捕获整数异常
try { if (n < 0) throw -1; }
catch (int e) { cout << "错误码:" << e; }
// 捕获字符串异常
try { throw "出错了"; }
catch (const char* s) { cout << s; }
// 捕获标准异常
#include <stdexcept>
try { throw runtime_error("错误"); }
catch (exception& e) { cout << e.what(); }
⚙️ 三、异常处理的执行流程
程序进入 try 块 执行
遇到 throw → 立即跳出 try 块，不再执行后续代码
进入匹配的 catch 块 处理
catch 块执行完毕 → 继续执行 catch 后面的代码
⚠️ throw 后 try 块剩余代码被跳过 。用异常处理替代 if-else 的层层判断，代码更清晰。
🛠️ 四、实战：安全的除法
int safe_divide(int a, int b) {
if (b == 0) throw "除数为零！";
return a / b;
}
int main() {
try {
cout << safe_divide(10, 0);
} catch (const char* e) {
cerr << "错误: " << e << endl;
}
}
💡 GESP 四级了解 try-throw-catch 基本用法即可，重点是try 块包裹 + throw 抛出 + catch 捕获 的三步模式。
📝 五、真题演练 （点击选项作答）
📌 第1题 try 块的作用是（ ）。
A. 定义变量
B. 包裹可能出错的代码
C. 捕获异常
D. 抛出异常
📌 第2题 throw 关键字的作用是（ ）。
A. 定义变量
B. 包裹代码
C. 抛出异常
D. 捕获异常
📌 第3题 catch 块在什么情况下执行？（ ）
A. 总是执行
B. try块中抛出匹配异常时
C. try块正常结束时
D. 程序启动时
📌 第4题 throw 执行后 try 块中后续代码（ ）。
A. 继续执行
B. 被跳过
C. 重新执行
D. 由catch决定
📌 第5题 throw "错误"; catch 应使用（ ）捕获。
A. catch(int e)
B. catch(const char* e)
C. catch(double e)
D. catch(bool e)
📌 第6题 关于异常处理说法正确 的是（ ）。
A. 异常处理让程序永不崩溃
B. throw后try块剩余代码被跳过
C. catch必须捕获所有异常
D. 一个try只能有一个catch
🔢 第1课：初等数论基础
辗转相除法、素数筛法、唯一分解定理——数论是算法竞赛的"必修课"，五级必须掌握。
📖 故事导入
🤔 小明想知道 123456 和 789012 的最大公约数，从 1 一个个试太慢了。老师教他辗转相除法 ——两千年前欧几里得就发明的算法，至今仍是最优解！
🔄 一、辗转相除法（欧几里得算法）
核心原理 ：gcd(a, b) = gcd(b, a % b)，反复取余直到余数为 0。
// 递归版（简洁优雅）
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 迭代版（防爆栈）
int gcd(int a, int b) {
while (b) {
int t = a % b;
a = b; b = t;
}
return a;
}
时间复杂度 ：O(log min(a, b))——非常快！
💡 最小公倍数 ：lcm(a, b) = a / gcd(a, b) × b（先除后乘防溢出）。lcm(a,b) × gcd(a,b) = a × b。
🧹 二、素数筛法
2.1 埃氏筛法（Eratosthenes）
从小到大枚举，把每个素数的倍数全部标记为合数。
// 求 1~n 中所有素数
bool isPrime[MAXN];
void eratosthenes(int n) {
for (int i = 2 ; i <= n; i++)
isPrime[i] = true ;
for (int i = 2 ; i * i <= n; i++)
if (isPrime[i])
for (int j = i * i; j <= n; j += i)
isPrime[j] = false ;
}
复杂度：O(n log log n) ，n=10⁶ 毫无压力。
2.2 线性筛法（欧拉筛）
每个合数只被最小质因子 筛掉一次，复杂度 O(n) 。
int primes[MAXN], cnt = 0 ;
bool isComp[MAXN];
void linearSieve(int n) {
for (int i = 2 ; i <= n; i++) {
if (!isComp[i]) primes[cnt++] = i;
for (int j = 0 ; j < cnt && i * primes[j] <= n; j++) {
isComp[i * primes[j]] = true ;
if (i % primes[j] == 0 ) break ;
}
}
}
算法 复杂度 适用场景
埃氏筛 O(n log log n) n ≤ 10⁷，日常够用 线性筛 O(n) 极限压榨，可顺便求最小质因子
📐 三、唯一分解定理
每个大于 1 的自然数都可以唯一 分解为素数的乘积：
n = p₁a₁ × p₂a₂ × ... × pₖaₖ
// 分解 n 的质因数
void factorize(int n) {
for (int i = 2 ; i * i <= n; i++) {
while (n % i == 0 ) {
cout << i << " " ;
n /= i;
}
}
if (n > 1 ) cout << n; // 剩余的大质因子
}
⚠️ 关键推论 ：若 n = ∏pᵢᵃⁱ，则 n 的约数个数 = ∏(aᵢ+1)，约数之和 = ∏(pᵢᵃⁱ⁺¹−1)/(pᵢ−1)。GESP 五级常考。
🔢 四、模运算基础
// 模意义下的四则运算
(a + b) % m = ((a % m) + (b % m)) % m
(a - b) % m = ((a % m) - (b % m) + m) % m // +m 防负数
(a × b) % m = ((a % m) × (b % m)) % m
// 除法不能直接取模！需要求逆元（L5后续内容）
模运算适用于结果很大需要取模 的场景，GESP 竞赛中常要求对 10⁹+7 取模输出。
📝 五、真题演练 （点击选项作答）
📌 第1题 gcd(12, 18) 的值是（ ）。
A. 2
B. 3
C. 6
D. 12
📌 第2题 埃氏筛法的时间复杂度是（ ）。
A. O(n)
B. O(n log n)
C. O(n log log n)
D. O(n²)
📌 第3题 36 分解质因数的结果是（ ）。
A. 2²×3²
B. 2²×3³
C. 2×3²
D. 2³×3
📌 第4题 lcm(12, 18) 的值是（ ）。
A. 6
B. 18
C. 36
D. 72
📌 第5题 线性筛能 O(n) 的核心原因是（ ）。
A. 用数组存储
B. 每个合数只被最小质因子筛一次
C. 使用双向循环
D. 跳过了偶数
📌 第6题 n = 100，1~n 中共有（ ）个素数。
A. 20
B. 25
C. 30
D. 10
🧮 第2课：高精度计算
当数字大到 long long 都装不下时——用数组模拟加减乘除，大数运算不再溢出！
📖 故事导入
🧒 小明想算 100!（100 的阶乘），用 long long 直接溢出了！老师说："int 和 long long 都有上限，超出就要用高精度 ——用一个数组，每一位存一个数字。"
📦 一、高精度的存储方式
倒序存储 ：个位存在数组 [0]，十位在 [1]，依此类推。
// 用字符串读入大数
string s; cin >> s;
int a[1000 ], len = s.length();
for (int i = 0 ; i < len; i++)
a[i] = s[len-1 -i] - '0' ; // 倒序存
原始数字 字符串 数组存储 1234 "1234" a[0]=4, a[1]=3, a[2]=2, a[3]=1
💡 为什么倒序存？ 加法从低位（个位）开始，进位向高位。倒序后下标递增=位权递增，代码自然。
➕ 二、高精度加法
// a + b = c，返回 c 的长度
int add(int a[], int b[], int c[], int len) {
int carry = 0 ;
for (int i = 0 ; i < len; i++) {
c[i] = a[i] + b[i] + carry;
carry = c[i] / 10 ;
c[i] %= 10 ;
}
if (carry) c[len++] = carry; // 最高位进位
return len;
}
➖ 三、高精度减法
前提：a ≥ b （大减小）。逐位相减，不够借位。
int sub(int a[], int b[], int c[], int len) {
int borrow = 0 ;
for (int i = 0 ; i < len; i++) {
c[i] = a[i] - b[i] - borrow;
if (c[i] < 0 ) {
c[i] += 10 ;
borrow = 1 ;
} else borrow = 0 ;
}
while (len > 1 && c[len-1 ] == 0 ) len--; // 去前导零
return len;
}
⚠️ 关键 ：减法前先比较大小确保 a≥b；结束后去前导零（如 1000-999=1，不能输出 0001）。
✖️ 四、高精度乘法
// 高精度 × 单精度（大数 × 普通 int）
int mul(int a[], int b, int c[], int len) {
int carry = 0 ;
for (int i = 0 ; i < len; i++) {
c[i] = a[i] * b + carry;
carry = c[i] / 10 ;
c[i] %= 10 ;
}
while (carry) {
c[len++] = carry % 10 ;
carry /= 10 ;
}
return len;
}
高精度×高精度 = 双重循环逐位乘，复杂度 O(n²)。GESP 五级考高精×单精为主。
📝 五、真题演练 （点击选项作答）
📌 第1题 高精度存储数字时，数组[0]通常存放（ ）。
A. 最高位
B. 个位
C. 千位
D. 随机位
📌 第2题 高精度加法中，进位 carry 的最大值是（ ）。
A. 9
B. 1
C. 取决于位数
D. 0
📌 第3题 高精度减法前必须确保（ ）。
A. a 和 b 长度相同
B. a ≥ b（大减小）
C. b 的位数更多
D. 不需要条件
📌 第4题 高精度乘法（大数 × 单精度）的核心是（ ）。
A. 逐位乘并处理进位
B. 把大数存成 double
C. 直接使用 * 运算符
D. 使用 pow 函数
📌 第5题 高精度运算中去前导零的作用是（ ）。
A. 加快运算速度
B. 避免输出 00012 这样的结果
C. 节省内存
D. 防止溢出
📌 第6题 n 位高精度加法的时间复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
🔗 第3课：线性表——链表
数组插入删除要挪一堆元素——链表用指针串起数据，插入删除 O(1) 搞定！
📖 故事导入
🚂 数组像一列火车，要在中间加一节车厢，后面的都得挪。链表每节车厢自带"下一节在哪"的指针，插中间只需改两个指针 ——像是重新挂接车厢！
📐 一、链表 vs 数组
操作 数组 链表
随机访问 O(1) 快 O(n) 慢 插入/删除 O(n) 慢 O(1) 快 内存 连续 不连续，额外存指针
🏗️ 二、链表的结构定义
struct Node {
int data; // 数据域
Node* next; // 指针域——指向下一个节点
};
Node* head = NULL ; // 头指针，指向第一个节点
💡 节点=数据+指针 。head 指向第一个节点，最后一个节点的 next = NULL。
🔌 三、基本操作
3.1 创建节点
Node* p = new Node;
p->data = x;
p->next = NULL ;
3.2 头插法（逆序）
p->next = head;
head = p;
3.3 遍历链表
for (Node* p = head; p != NULL ; p = p->next)
cout << p->data << " " ;
3.4 查找值为 x 的节点
for (Node* p = head; p != NULL ; p = p->next)
if (p->data == x) return p;
⚠️ 不要忘记 delete ：new 出的节点在用完后必须 delete 释放，避免内存泄漏。GESP 五级考查基本链表操作。
📝 五、真题演练 （点击选项作答）
📌 第1题 链表节点包含（ ）个部分。
A. 1（只有数据）
B. 2（数据+指针）
C. 3
D. 不确定
📌 第2题 链表中每个节点占用内存的特点是（ ）。
A. 连续存储
B. 不连续，通过指针连接
C. 全部在栈上
D. 使用常量存储
📌 第3题 头插法建立的链表，节点顺序与原输入顺序（ ）。
A. 相同
B. 相反
C. 随机
D. 按大小排序
📌 第4题 链表相对于数组的主要优势是（ ）。
A. 随机访问更快
B. 插入删除效率高
C. 内存占用更少
D. 支持二分查找
📌 第5题 遍历链表的时间复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
📌 第6题 链表最后一个节点的 next 指针指向（ ）。
A. head
B. 自身
C. NULL
D. 第一个节点
🌀 第4课：递归
函数调用自己——递归把复杂问题分解成相同的小问题，是算法设计的核心思维。
📖 故事导入
🪆 俄罗斯套娃——打开一个，里面还有一个更小的，直到最小的那个。递归就是"函数自己调用自己 "，一层层深入，直到遇到终止条件 （最小的娃娃打不开）。
🧠 一、递归三要素
要素 说明 示例（阶乘）
1. 终止条件 不再递归的简单情况 n==0 → return 1 2. 递推公式 大问题→小问题的关系 n! = n × (n-1)! 3. 返回值 将子问题的解合成原问题的解 return n × f(n-1)
📐 二、经典递归示例
// 阶乘 n! = n × (n-1)!
int fact(int n) {
if (n == 0 ) return 1 ; // 终止条件
return n * fact(n - 1 ); // 递推+返回
}
// 斐波那契 fib(n)=fib(n-1)+fib(n-2)
int fib(int n) {
if (n <= 2 ) return 1 ; // 终止条件
return fib(n-1 ) + fib(n-2 ); // 递推
}
// 汉诺塔：把 n 个盘子从 A 移到 C（B 辅助）
void hanoi(int n, char A, char B, char C) {
if (n == 1 ) { cout << A << "->" << C << endl; return ; }
hanoi(n-1 , A, C, B); // 上面 n-1 个移到 B
cout << A << "->" << C << endl;
hanoi(n-1 , B, A, C); // B 上 n-1 个移到 C
}
⚠️ 三、递归的注意事项
⚠️ 三大陷阱 ：必须要有终止条件 ，否则无限递归导致栈溢出。栈空间限制 （通常几十万层），超深用递推。记忆化搜索 或递推优化。
🔄 四、递归 vs 递推
递归 递推
方向 自顶向下（大→小） 自底向上（小→大） 实现 函数自调用 循环+数组 优势 代码简洁、符合数学定义 无栈溢出风险、效率高
📝 五、真题演练 （点击选项作答）
📌 第1题 递归函数必须包含（ ）。
A. 循环语句
B. 终止条件
C. 数组
D. 指针
📌 第2题 fact(4) 的返回过程是（ ）。
A. 4×3×2×1
B. 4+3+2+1
C. 4×4×4×4
D. 4×3
📌 第3题 汉诺塔 n 个盘子的最少移动次数是（ ）。
A. n
B. 2ⁿ
C. 2ⁿ-1
D. n²
📌 第4题 纯递归求 fib(40) 很慢是因为（ ）。
A. 函数调用开销
B. 大量重复计算
C. 数组太大
D. 编译器限制
📌 第5题 递归相比递推的主要缺点是（ ）。
A. 代码更长
B. 可能有栈溢出风险
C. 不能处理数学问题
D. 结果不准确
📌 第6题 递归函数的执行过程中用到了（ ）数据结构。
A. 队列
B. 栈
C. 堆
D. 数组
🔍 第5课：二分查找与二分答案
从100万个数中找目标值，暴力搜索100万次→二分只需20次！O(log n) 的威力超乎想象。
📖 故事导入
📖 查字典翻到中间："目标字在前面还是后面？"每次排除一半——1000页的字典最多翻 10 次 （2¹⁰=1024）。二分是"世界的分割线 "！
🎯 一、二分查找（Binary Search）
// 在有序数组 a[0..n-1] 中查找 x
int binarySearch(int a[], int n, int x) {
int lo = 0 , hi = n - 1 ;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2 ; // 防溢出
if (a[mid] == x) return mid; // 找到了
if (a[mid] < x) lo = mid + 1 ; // 在右边
else hi = mid - 1 ; // 在左边
}
return -1 ; // 没找到
}
💡 mid = lo + (hi-lo)/2 而非 (lo+hi)/2——后者 lo+hi 可能溢出 int！时间复杂度 O(log n) 。
📊 二、二分答案（Binary Answer）
思想 ：答案有单调性时，二分枚举答案，判断是否可行。
// 典型框架：求"最大的可行值"
while (lo <= hi) {
int mid = (lo + hi) / 2 ;
if (check(mid)) { // mid 能满足条件
ans = mid;
lo = mid + 1 ; // 尝试更大的
} else {
hi = mid - 1 ;
}
}
cout << ans; // 最大可行答案
场景 二分目标 check 内容
分木头 最大可能的长度 总段数 ≥ 要求 最小化最大值 最小的上限 在上限下能否完成 最大化最小值 最大的下限 在下限下能否满足
⚠️ 二分答案的前提 ：答案必须有单调性 （更大的答案要么都能满足、要么都不能）。如"分木头的最大长度"就满足单调性。
🔢 三、lower_bound / upper_bound
// 二分查找的两种变体
// lower_bound: 第一个 ≥ x 的位置
int lo = 0 , hi = n;
while (lo < hi) {
int mid = (lo + hi) / 2 ;
if (a[mid] >= x) hi = mid;
else lo = mid + 1 ;
}
// 也可直接用 STL：
int pos = lower_bound(a, a+n, x) - a;
📝 五、真题演练 （点击选项作答）
📌 第1题 二分查找要求数组（ ）。
A. 无序
B. 有序
C. 长度固定
D. 都是正数
📌 第2题 在长度为 10⁶ 的有序数组中二分查找，最多比较（ ）次。
A. 10
B. 20
C. 1000
D. 10⁶
📌 第3题 二分答案算法的前提是答案具有（ ）。
A. 随机性
B. 单调性
C. 对称性
D. 周期性
📌 第4题 lower_bound 返回（ ）的位置。
A. 第一个大于x
B. 第一个大于等于x
C. 最后一个等于x
D. 最后一个小于x
📌 第5题 二分查找的时间复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
📌 第6题 二分答案的 check 函数通常复杂度为（ ）。
A. 至少O(log n)
B. 通常O(n)
C. 必须是O(1)
D. 不定，取决于问题
🔀 第6课：分治算法
把大问题拆成小问题分别解决再合并——归并排序、快速幂都是分治的杰作！
📖 故事导入
🏗️ 盖一栋大楼：先打好每层的地基，再逐层施工——分而治之 。算法中，把大问题拆成若干相同的小问题，分别解决后合并结果——这就是分治。
📐 一、分治三步法
步骤 名称 含义
1 分解（Divide） 将原问题分成若干规模较小的相同子问题 2 解决（Conquer） 递归解决每个子问题（足够小时直接求解） 3 合并（Combine） 将子问题的解合并成原问题的解
🔄 二、归并排序（Merge Sort）
分治典型 ：把数组对半分，分别排序，再合并两个有序数组。
void mergeSort(
int a[],
int lo,
int hi) {
if (lo >= hi)
return ;
// 终止：1个元素
int mid = (lo + hi) /
2 ;
mergeSort(a, lo, mid);
// 左半排序
mergeSort(a, mid+
1 , hi);
// 右半排序
// 合并两个有序数组
int tmp[hi-lo+
1 ], i=lo, j=mid+
1 , k=
0 ;
while (i<=mid && j<=hi)
tmp[k++] = a[i]<a[j] ? a[i++] : a[j++];
while (i<=mid) tmp[k++] = a[i++];
while (j<=hi) tmp[k++] = a[j++];
for (i=
0 ; i<k; i++) a[lo+i] = tmp[i];
}
特性 值
时间复杂度 O(n log n) 稳定 稳定性 稳定 空间复杂度 O(n)（需临时数组）
⚡ 三、快速幂（分治优化）
// 计算 a^n mod m，O(log n)
long long qpow(long long a, long long n, long long m) {
long long res = 1 ;
while (n) {
if (n & 1 ) res = res * a % m; // n是奇数时乘一次
a = a * a % m; // a = a²
n >>= 1 ; // n = n/2
}
return res;
}
💡 思想 ：a¹³ = a⁸ × a⁴ × a¹（13=1101₂），每次指数折半。复杂度从 O(n) 降到 O(log n) 。
📝 五、真题演练 （点击选项作答）
📌 第1题 分治算法的第一步通常是（ ）。
A. 合并
B. 分解
C. 排序
D. 查找
📌 第2题 归并排序的时间复杂度是（ ）。
A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)
📌 第3题 归并排序的空间复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
📌 第4题 快速幂 a¹⁰ 需要几次乘法（最坏）？（ ）
A. 10
B. 5
C. 4
D. 3
📌 第5题 归并排序的合并操作复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
📌 第6题 分治与递归的关系是（ ）。
A. 完全相同
B. 分治常用递归实现
C. 完全无关
D. 分治必须用循环
🎯 第7课：贪心算法
每一步都选当前看起来最好的——贪心不总是最优，但很多经典问题贪心就是正解！
📖 故事导入
💵 找零钱：要凑 63 元，最少的纸币张数？每次选面额最大的：50+10+1+1+1=5张。贪心 ——每一步都做"眼前最优"的选择。但换一套面额（如1,3,4），贪心就翻车了！
🎯 一、贪心算法核心思想
贪心 = 局部最优 → 全局最优 。每步做当前最好的选择，不回溯。
⚠️ 重要 ：贪心不是万能 的。必须证明贪心策略对当前问题有效（如"最优子结构"+"贪心选择性质"）。GESP 五级考查经典贪心问题。
📦 二、经典例题：部分背包问题
物品可以分割 （取一部分）时，按"单位价值"排序，优先选单位价值最高的。
struct Item { double w, v, ratio; }; // 重量、价值、单位价值
// 按 ratio (v/w) 从大到小排序
sort(items, items+n, [](Item a, Item b) {
return a.ratio > b.ratio;
});
double ans = 0 ;
for (int i = 0 ; i < n && capacity > 0 ; i++) {
double take = min(items[i].w, capacity);
ans += take * items[i].ratio;
capacity -= take;
}
💡 关键区别 ：部分背包贪心正确（物品可分割）。0-1背包 不能贪心（物品不可分割），需动态规划。
🏟️ 三、经典例题：活动选择问题
选最多的不重叠活动——按结束时间排序 ，每次选最早结束的。
// 按结束时间升序排序
sort(act, act+n, [](Act a, Act b) {
return a.end < b.end;
});
int cnt = 1 , lastEnd = act[0 ].end;
for (int i = 1 ; i < n; i++)
if (act[i].start >= lastEnd) {
cnt++;
lastEnd = act[i].end;
}
📋 四、贪心常见题型总结
问题 贪心策略 是否正确
找零钱（标准面额） 每次选最大面额 ✅ 部分背包 单位价值最高优先 ✅ 活动选择 最早结束优先 ✅ 0-1背包 单位价值最高优先 ❌ 错误！
📝 五、真题演练 （点击选项作答）
📌 第1题 贪心算法的核心思想是（ ）。
A. 枚举所有可能
B. 每步选当前最优
C. 随机选择
D. 倒推
📌 第2题 部分背包问题贪心正确的关键原因是（ ）。
A. 物品重量不同
B. 物品可分割
C. 背包容量大
D. 价值是整数
📌 第3题 活动选择问题按（ ）排序是最优策略。
A. 开始时间
B. 活动时长
C. 结束时间
D. 重要性
📌 第4题 贪心算法的缺点 是（ ）。
A. 总是得到最优解
B. 不总是得到最优解
C. 时间复杂度高
D. 代码复杂
📌 第5题 以下不能 用贪心求解的是（ ）。
A. 部分背包
B. 找零钱(标准面额)
C. 0-1背包
D. 活动选择
📌 第6题 为了验证贪心策略正确，通常需要（ ）。
A. 运行多次测试
B. 数学证明
C. 询问他人
D. 不需要验证
⏱️ 第8课：算法复杂度进阶
从 O(n²) 到 O(2ⁿ)——掌握各类复杂度的本质，心中有杆秤，算法设计不翻车。
📖 故事导入
⏰ O(n²) 的算法 n=10⁵ 时要跑 10¹⁰ 次——超时！O(n log n) 只要 1.7×10⁶ 次。选对复杂度 = 选对算法 ，这就是为什么我们要懂复杂度分析。
📊 一、复杂度速查表
复杂度 n=10³ n=10⁵ n=10⁷ 典型算法
O(1) 1 1 1 下标访问 O(log n) 10 17 23 二分查找 O(n) 10³ 10⁵ 10⁷ 遍历、线性筛 O(n log n) 10⁴ 1.7×10⁶ 2.3×10⁸ 归并排序 O(n²) 10⁶ 10¹⁰ ❌ 10¹⁴ ❌ 冒泡排序 O(2ⁿ) 10³⁰¹ ❌ — ❌ — ❌ 暴力子集
📐 二、时间复杂度实战估算
C++ 约 10⁸ 次/秒 基本操作。已知时间限制（通常 1s），反推可用算法：
n 的范围 可用复杂度 常用算法
n ≤ 10 O(n!), O(2ⁿ) 暴力枚举、DFS n ≤ 20 O(2ⁿ) 状态压缩DP n ≤ 500 O(n²) DP、最短路 n ≤ 10⁵ O(n log n) 排序、二分 n ≤ 10⁷ O(n) 线性筛、扫描
💡 竞赛铁律 ：n≤10⁵ → O(n log n) 安全；n≤10⁶ → O(n) 才能过。看到数据范围心里就要有谱！
📐 三、主定理（Master Theorem）简介
递归分治算法的时间复杂度可通过主定理 快速判定：
T(n) = a·T(n/b) + O(nᵈ)，则 T(n) = O(nᵈ log n)（当 a=bᵈ）
例如归并排序：a=2, b=2, d=1 → a=bᵈ → O(n log n) 。
💾 四、空间复杂度实战
O(1) ：原地操作（swap、递推），最省内存O(n) ：开一个长度为 n 的数组，256MB 能存约 6.4×10⁷ 个 intO(n²) ：二维数组 n=10⁴ 就占 400MB，极易 MLE
⚠️ GESP 五级重点 ：根据 n 的范围判断哪种复杂度的算法能过。n≤10⁵→O(n log n)，n≤10³→O(n²)，n≤20→O(2ⁿ)。
📝 五、真题演练 （点击选项作答）
📌 第1题 n=10⁵ 时，以下能通过 1s 限制的复杂度是（ ）。
A. O(n²)
B. O(n log n)
C. O(2ⁿ)
D. O(n!)
📌 第2题 归并排序 T(n)=2T(n/2)+O(n)，用主定理得（ ）。
A. O(n)
B. O(n log n)
C. O(n²)
D. O(log n)
📌 第3题 n≤500 时，以下可用的是（ ）。
A. 仅O(n)
B. O(n²)
C. O(2ⁿ)
D. 必须O(log n)
📌 第4题 256MB 大约能存多少个 int？（ ）
A. 10³
B. 10⁶
C. 6.4×10⁷
D. 10⁹
📌 第5题 空间复杂度 O(1) 表示（ ）。
A. 不使用任何内存
B. 所需额外空间与输入规模无关
C. 只用一个变量
D. 使用1MB内存
📌 第6题 n=20 时，O(2ⁿ) 约（ ）次操作。
A. 400
B. 10⁴
C. 10⁶
D. 10⁹
🌳 第1课：树的定义、构造与遍历 从线性到层次——树是计算机科学中最基础的非线性数据结构。
📖 故事导入
📂 打开你的电脑文件夹——C盘下有"Program Files"、"Users"、"Windows"，每个文件夹里又有子文件夹。这种层次结构 就是一棵树！根是 C 盘，每个文件夹是一个节点。
📐 一、树的基本概念
术语 定义 示例
根节点 树的最顶层节点（没有父节点） C盘 父节点 / 子节点 上层直接相连的是父，下层是子 Users 是 Admin 的父 叶子节点 没有子节点的节点 某个空文件夹 深度 从根到该节点的路径长度 根深度为 0 高度 树中节点的最大深度
🏗️ 二、树的存储（孩子表示法）
const int MAXN = 100005 ;
vector <int > tree[MAXN]; // tree[u] 存储节点 u 的所有孩子
// 建树：读入 n-1 条边
for (int i = 0 ; i < n - 1 ; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u); // 无向树
}
🔄 三、树的遍历
3.1 深度优先遍历（DFS）
void dfs(int u, int parent) {
cout << u << " " ; // 先序：访问根
for (int v : tree[u]) {
if (v != parent) dfs(v, u);
}
// cout << u << " "; // 后序：访问根（放这里）
}
3.2 广度优先遍历（BFS）
void bfs(int root) {
queue <int > q;
q.push(root);
bool vis[MAXN] = {false };
vis[root] = true ;
while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << " " ;
for (int v : tree[u]) {
if (!vis[v]) { vis[v] = true ; q.push(v); }
}
}
}
💡 DFS = 一条路走到黑（栈/递归）；BFS = 一层一层展开（队列）。
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"树的定义、存储与遍历"核心知识点。
📌 第 1 题 下列关于树 的说法，正确 的是（ ）。
A. 树中每个节点都必须有至少一个子节点
B. 树的根节点没有父节点
C. 树中所有节点的深度都相同
D. 树中任意两个节点之间一定直接相连
📌 第 2 题 叶子节点的特征是（ ）。
A. 既有父节点又有子节点
B. 有父节点但没有子节点
C. 有父节点，但没有子节点（除根外）
D. 没有父节点且没有子节点
📌 第 3 题 以下代码中，tree[u].push_back(v); tree[v].push_back(u); 的作用是（ ）。
for (int i = 0 ; i < n - 1 ; i++) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
A. 建立从 u 到 v 的单向边
B. 在 u 和 v 之间建立无向边（相互连接）
C. 将 v 设为 u 的父节点
D. 删除 u 和 v 之间的边
📌 第 4 题 树的深度优先遍历（DFS） 使用的数据结构是（ ）。
A. 队列
B. 栈（或系统递归栈）
C. 优先队列
D. 链表
📌 第 5 题 以下关于BFS（广度优先遍历） 的描述，正确 的是（ ）。
A. BFS 使用递归实现
B. BFS 先访问离根最近的节点
C. BFS 的核心数据结构是栈
D. 以上 B 正确，BFS 按层展开，用队列实现
📌 第 6 题 下图是一棵有 5 个节点的树（1 为根，边为 1-2, 1-3, 2-4, 2-5）。从节点 1 出发进行DFS 先序遍历 （孩子按编号从小到大访问），输出序列是（ ）。
A. 1 2 4 5 3
B. 1 2 3 4 5
C. 4 5 2 3 1
D. 1 3 2 5 4
📊 真题考点统计 ：GESP 六级树的考点主要包括 ① 树的定义与基本术语（根、叶子、深度、高度） ② 孩子表示法建图（vector 邻接表）③ DFS 原理与递归/栈实现 ④ BFS 原理与队列实现 ⑤ 遍历序列推导。通常以概念判断和读代码题出现。
🌲 第2课：二叉树与二叉排序树 每个节点最多两个子节点——二叉树是最重要、最常用的树结构。
📖 故事导入
📋 猜数字游戏：想一个 1~100 的数，每次猜中间值——"大了"就往左，"小了"就往右。这其实就是一棵二叉搜索树 ！
🌲 一、完全二叉树
定义 ：除最后一层外，每层都满；最后一层节点从左到右连续排列。
性质 （数组存储）：
节点 i 的左孩子：2i
节点 i 的右孩子：2i + 1
节点 i 的父节点：i / 2
// 完全二叉树数组存储
int tree[MAXN];
int leftChild = i * 2 ;
int rightChild = i * 2 + 1 ;
int parent = i / 2 ;
🔍 二、二叉排序树（BST）
性质 ：左子树所有值 < 根 < 右子树所有值。
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr ), right(nullptr ) {}
};
// 插入
TreeNode* insert(TreeNode* root, int x) {
if (!root) return new TreeNode(x);
if (x < root->val) root->left = insert(root->left, x);
else root->right = insert(root->right, x);
return root;
}
// 查找
bool search(TreeNode* root, int x) {
if (!root) return false ;
if (root->val == x) return true ;
return x < root->val ? search(root->left, x)
: search(root->right, x);
}
平均查找 O(log n)，最坏 O(n)（退化成链）。
🔄 三、二叉树的三种遍历
// 先序：根 → 左 → 右
void preorder(TreeNode* root) {
if (!root) return ;
cout << root->val << " " ;
preorder(root->left);
preorder(root->right);
}
// 中序：左 → 根 → 右（BST中序 = 升序序列）
void inorder(TreeNode* root) {
if (!root) return ;
inorder(root->left);
cout << root->val << " " ;
inorder(root->right);
}
// 后序：左 → 右 → 根
void postorder(TreeNode* root) {
if (!root) return ;
postorder(root->left);
postorder(root->right);
cout << root->val << " " ;
}
💡 记住：先/中/后 指的是根的位置 。BST 的中序遍历 = 升序输出！
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"二叉树、完全二叉树与二叉排序树"核心知识点。
📌 第 1 题 在完全二叉树 的数组存储中，节点 i 的左孩子下标是（ ）。
A. i + 1
B. 2 × i
C. 2 × i + 1
D. i / 2
📌 第 2 题 二叉排序树（BST） 的核心性质是（ ）。
A. 左子树所有值 > 根 > 右子树所有值
B. 左子树所有值 < 根 < 右子树所有值
C. 节点值可以任意排列，没有顺序要求
D. 每个节点最多有两个子节点
📌 第 3 题 向 BST 依次插入 8, 3, 10, 1, 6，则节点 6 的父节点 是（ ）。
A. 1
B. 3
C. 8
D. 10
📌 第 4 题 二叉树的中序遍历 顺序是（ ）。
A. 根 → 左 → 右（先序）
B. 左 → 根 → 右（中序）
C. 左 → 右 → 根（后序）
D. 右 → 左 → 根
📌 第 5 题 对一棵二叉排序树 进行中序遍历，得到的序列是（ ）。
A. 降序序列
B. 升序序列
C. 与先序遍历相同的序列
D. 随机顺序
📌 第 6 题 依次插入 5, 3, 7, 2, 4, 6, 8 构建 BST。以下不是叶子节点 的是（ ）。
A. 3
B. 2
C. 6
D. 8
📊 真题考点统计 ：GESP 六级二叉树考点包括 ① 完全二叉树数组下标关系（左2i/右2i+1/父i/2）② BST 性质与构建 ③ 三种遍历序（先/中/后）④ BST 中序=升序 ⑤ BST 查找时间复杂度。常出概念判断、读代码推断和手动模拟题。
📦 第3课：哈夫曼树与哈夫曼编码 让出现频率高的字符用短编码，频率低的用长编码——这是最优前缀编码。
📖 故事导入
📧 发送电报时，字母 E 出现最多，如果给 E 用最短的编码（如"01"），给 Z 用长编码（如"110101"），就能大大缩短电报长度。这就是哈夫曼编码 的核心思想。
🌳 一、哈夫曼树的构建
每次取权值最小 的两个节点，合并为新节点（权值 = 两者之和），重复直到只剩一个节点。
// 哈夫曼树构建（优先队列）
priority_queue <int , vector <int >, greater<int >> pq;
for (int i = 0 ; i < n; i++) {
int w;
cin >> w;
pq.push(w);
}
int total = 0 ; // WPL（带权路径长度）
while (pq.size() > 1 ) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
int sum = a + b;
total += sum;
pq.push(sum);
}
cout << total << endl;
📝 二、哈夫曼编码
从根出发：左分支 = 0，右分支 = 1 。每个字符的编码 = 从根到该字符叶子的路径。
字符 频率 哈夫曼编码
A 45% 0 B 25% 10 C 20% 110 D 10% 111
性质 ：哈夫曼编码是前缀编码 ——没有任何一个编码是另一个编码的前缀（不会产生歧义）。
📏 三、带权路径长度（WPL）
WPL = Σ(权值 × 深度)
WPL 最小的二叉树就是最优二叉树 （哈夫曼树）。
💡 哈夫曼树 = 最优二叉树。用优先队列（小根堆）构建，每次取最小的两个合并。
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"哈夫曼树构建、哈夫曼编码与 WPL"核心知识点。
📌 第 1 题 构建哈夫曼树 时，每次从候选节点中选出（ ）。
A. 权值最小的两个节点
B. 权值最大的两个节点
C. 任意两个节点
D. 权值最接近的两个节点
📌 第 2 题 哈夫曼编码是前缀编码 ，这意味着（ ）。
A. 所有字符的编码长度相同
B. 没有任何一个编码是另一个编码的前缀
C. 所有编码都以 0 开头
D. 所有编码都以 1 结尾
📌 第 3 题 给定权值 {2, 3, 4, 5}，构建哈夫曼树的WPL（带权路径长度） 是（ ）。
A. 14
B. 20
C. 28
D. 56
📌 第 4 题 在哈夫曼树中，从根出发：左分支编码为 0 ，右分支编码为 1 。若某叶子路径为 左→左→右，其编码是（ ）。
A. 001
B. 110
C. 010
D. 100
📌 第 5 题 有 n 个叶子节点的哈夫曼树，构建过程中需要合并 （ ）次。
A. n 次
B. n - 1 次
C. n / 2 次
D. 2n - 1 次
📌 第 6 题 以下代码中 priority_queue<int, vector<int>, greater<int>> pq; 创建的是（ ）。
A. 大根堆（最大优先队列）
B. 小根堆（最小优先队列）
C. 普通队列（FIFO）
D. 双端队列
📊 真题考点统计 ：GESP 六级哈夫曼树考点包括 ① 贪心构建过程（每次取最小两个）② 前缀编码性质（无歧义）③ WPL 公式与计算 ④ 编码规则（左0右1）⑤ 优先队列 priority_queue 的使用。常出概念判断和手动模拟计算题。
🔢 第4课：格雷编码 相邻两个数只有一位二进制不同——这种编码在数字电路和竞赛中都很常见。
📖 故事导入
🔢 普通二进制从 3（011）变到 4（100）时，三位同时翻转——在电路中有可能产生毛刺。而格雷码 相邻数只变一位，优雅地解决了这个问题。
📐 一、格雷码的定义
n 位格雷码序列：满足相邻两个数（包括首尾）的二进制表示仅有一位不同 。
十进制 二进制 格雷码
0 000 000 1 001 001 2 010 011 3 011 010 4 100 110 5 101 111 6 110 101 7 111 100
🔄 二、二进制 ↔ 格雷码 转换
// 二进制 → 格雷码：G = B ^ (B >> 1)
int bin2Gray(int b) {
return b ^ (b >> 1 );
}
// 格雷码 → 二进制：逐位还原
int gray2Bin(int g) {
int b = 0 ;
while (g) {
b ^= g;
g >>= 1 ;
}
return b;
}
🔨 三、生成 n 位格雷码序列
// 反射法生成 n 位格雷码
vector <int > grayCode(int n) {
vector <int > res;
for (int i = 0 ; i < (1 << n); i++)
res.push_back(i ^ (i >> 1 ));
return res;
}
公式法：第 i 个格雷码 = i ^ (i >> 1)，极其简洁！
💡 核心公式：G(i) = i ^ (i >> 1) 。格雷码保证相邻数只差一位，常用于状态压缩 DP 的合法转移判断。
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"格雷码性质、转换公式与生成方法"核心知识点。
📌 第 1 题 格雷码 （Gray Code）的核心特征是（ ）。
A. 相邻两个编码只有一位二进制不同
B. 编码值从小到大排列
C. 编码长度递增
D. 每位都是 1
📌 第 2 题 将二进制数转换为格雷码 的公式是（ ）。
A. G = B & (B >> 1)
B. G = B ^ (B >> 1)
C. G = B | (B >> 1)
D. G = ~B
📌 第 3 题 二进制数 6 （即 1102 ）对应的格雷码是（ ）。
A. 101
B. 011
C. 110
D. 111
📌 第 4 题 3 位格雷码序列共有（ ）个数。
A. 6
B. 7
C. 8
D. 9
📌 第 5 题 在标准 n 位格雷码序列中，第一个和最后一个编码（ ）。
A. 也只相差一位（构成循环）
B. 可能相差多位
C. 完全相同
D. 没有规律
📌 第 6 题 生成 n 位格雷码的公式法 是（ ）。
A. i + (i >> 1)
B. i ^ (i >> 1)
C. i & (i >> 1)
D. i | (i >> 1)
📊 真题考点统计 ：GESP 六级格雷码考点包括 ① 定义（相邻差一位）② 转换公式 G = B ^ (B>>1) ③ n位格雷码共 2^n 个 ④ 首尾循环性质 ⑤ 反射法/公式法生成。常出概念判断和手动转换计算题。
🔍 第5课：深度优先搜索（DFS） 不撞南墙不回头——DFS 用递归深入探索，是回溯、记忆化搜索的基础。
📖 故事导入
🧗 走迷宫时，你沿着一条路一直走到死胡同，然后退回来换一条路——这就是深度优先搜索 ：一条路走到底，不行就回溯，换条路再试。
🧱 一、DFS 基本框架
void dfs(状态) {
if (终止条件) {
// 处理结果
return ;
}
for (每种可能的选择) {
if (选择合法) {
做选择;
dfs(新状态);
撤销选择; // 回溯！
}
}
}
🔢 二、经典例题：全排列
int n, a[20 ];
bool used[20 ];
void dfs(int k) { // 正在填第 k 个位置
if (k > n) {
for (int i = 1 ; i <= n; i++)
cout << a[i] << " " ;
cout << endl;
return ;
}
for (int i = 1 ; i <= n; i++) {
if (!used[i]) {
a[k] = i;
used[i] = true ; // 做选择
dfs(k + 1 );
used[i] = false ; // 撤销（回溯）
}
}
}
🏝️ 三、经典例题：连通块计数（Flood Fill）
int n, m, grid[MAXN][MAXN];
int dx[] = {-1 , 1 , 0 , 0 };
int dy[] = {0 , 0 , -1 , 1 };
void dfs(int x, int y) {
grid[x][y] = 0 ; // 标记已访问
for (int d = 0 ; d < 4 ; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny])
dfs(nx, ny);
}
}
💡 DFS 三要素：① 终止条件 ② 合法选择 ③ 回溯撤销。DFS 天然适合"枚举所有方案"类问题。
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"DFS 框架、全排列回溯与 Flood Fill"核心知识点。
📌 第 1 题 DFS（深度优先搜索）的核心数据结构是（ ）。
A. 队列
B. 栈（递归调用栈）
C. 优先队列
D. 链表
📌 第 2 题 在全排列 DFS 代码中，used[i] = false; 这一行的作用是（ ）。
A. 标记数字已使用
B. 回溯撤销，让该数字可被后续排列使用
C. 终止递归
D. 初始化数组
📌 第 3 题 以下不属于 DFS 三要素的是（ ）。
A. 终止条件
B. 合法选择
C. 回溯撤销
D. 排序
📌 第 4 题 用 DFS 生成 n=3 的全排列 ，共输出（ ）个结果。
A. 3
B. 6
C. 9
D. 27
📌 第 5 题 在 Flood Fill（连通块）DFS 中，dx[] 和 dy[] 数组的作用是（ ）。
A. 记录坐标
B. 表示上、下、左、右四个方向的偏移量
C. 标记已访问的格子
D. 计算连通块面积
📌 第 6 题 在 DFS 框架中，遇到终止条件后执行 return; 的作用是（ ）。
A. 结束整个程序
B. 结束当前分支，回溯到上一层继续搜索
C. 跳过当前循环的剩余迭代
D. 重新开始搜索
📊 真题考点统计 ：GESP 六级 DFS 考点包括 ① DFS 原理与栈/递归关系 ② 三要素（终止条件、选择、回溯）③ 全排列/组合枚举 ④ Flood Fill 方向数组 ⑤ 回溯的撤销操作。常出概念判断、读代码和手工模拟题。
🌊 第6课：广度优先搜索（BFS） 层层推进——BFS 用队列保证最先找到的就是最优解。
📖 故事导入
💧 一滴水滴在纸中央，水渍一圈一圈向外扩散——先湿润的是离中心最近的地方。BFS 就是这样：先访问离起点近的，再访问远的 。所以 BFS 天然适合求最短路径 。
🧱 一、BFS 基本框架
queue <状态> q;
bool vis[...] = {false };
q.push(初始状态);
vis[初始状态] = true ;
while (!q.empty()) {
状态 cur = q.front(); q.pop();
for (每种扩展方向) {
if (合法 && 未访问) {
q.push(新状态);
vis[新状态] = true ;
}
}
}
🏃 二、经典：迷宫最短路径
struct Node { int x, y, step; };
int bfs(int sx, int sy, int tx, int ty) {
queue <Node> q;
bool vis[MAXN][MAXN] = {false };
q.push({sx, sy, 0 });
vis[sx][sy] = true ;
int dx[] = {-1 , 1 , 0 , 0 };
int dy[] = {0 , 0 , -1 , 1 };
while (!q.empty()) {
Node cur = q.front(); q.pop();
if (cur.x == tx && cur.y == ty)
return cur.step; // 最早到达 = 最短距离！
for (int d = 0 ; d < 4 ; d++) {
int nx = cur.x + dx[d], ny = cur.y + dy[d];
if (合法 && !vis[nx][ny]) {
q.push({nx, ny, cur.step + 1 });
vis[nx][ny] = true ;
}
}
}
return -1 ; // 不可达
}
📊 三、DFS vs BFS
维度 DFS BFS
数据结构 栈（递归） 队列 最短路径 ❌ 不能保证 ✅ 天然保证 空间 O(深度) O(宽度) 适用场景 枚举所有方案、回溯 最短路、层序遍历
💡 DFS = 栈（递归）；BFS = 队列。求最短步数 用 BFS，枚举所有可能 用 DFS。
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"BFS 框架、队列、最短路径与 DFS/BFS 对比"核心知识点。
📌 第 1 题 BFS（广度优先搜索）的核心数据结构是（ ）。
A. 栈
B. 队列（queue）
C. 堆
D. 链表
📌 第 2 题 BFS 能保证找到最短路径 的前提是（ ）。
A. 每条边的代价相等（如每步代价为 1）
B. 使用递归
C. 用二维数组存储
D. 任意情况都保证最短
📌 第 3 题 在 BFS 框架中，入队前 立刻标记 vis[x]=true 的根本目的是（ ）。
A. 加速搜索
B. 防止同一节点被重复入队
C. 排序队列
D. 统计节点数量
📌 第 4 题 迷宫 BFS 中，Node 结构体存储 step 的含义是（ ）。
A. x 坐标
B. 从起点走到当前节点的步数
C. 当前移动方向
D. 标记是否已访问
📌 第 5 题 在边权为 1 的迷宫中，BFS 第一次 遇到终点时直接返回步数（ ）。
A. 就是最短步数
B. 不一定是最短，需要继续搜索
C. 可能是死路
D. 只在树中有效
📌 第 6 题 在以下场景中，更适合用 BFS 而非 DFS 的是（ ）。
A. 迷宫中求起点到终点的最短步数
B. 枚举 3 个数的全排列
C. 判断图是否连通
D. 计算二叉树的高度
📊 真题考点统计 ：GESP 六级 BFS 考点包括 ① 队列数据结构 ② 迷宫最短路径（边权相等）③ vis 数组防重复入队 ④ DFS vs BFS 适用场景区分 ⑤ 首次抵达即最优。常与 DFS 对比考概念选择，或读 BFS 代码判断输出/时间复杂度。
🔎 第7课：二叉树的搜索算法 在二叉树中高效查找——结合 DFS/BFS 与二叉树特性的搜索技巧。
📖 故事导入
🔍 查找一个数是否在二叉树中——如果是二叉搜索树（BST），可以根据大小关系剪枝；如果是普通二叉树，就只能遍历所有节点。不同的树结构决定了搜索策略！
🌲 一、BST 中的搜索
利用 BST 的左小右大 性质，每次排除一半子树：
// BST 查找（迭代版）
TreeNode* searchBST(TreeNode* root, int val) {
while (root) {
if (root->val == val) return root;
root = (val < root->val) ? root->left : root->right;
}
return nullptr ;
}
时间复杂度 O(h)，h 为树高（平衡时 O(log n)）。
✨ 二、普通二叉树的搜索
普通二叉树无法剪枝，需遍历所有节点。DFS 和 BFS 都适用：
// DFS 搜索普通二叉树
bool dfsFind(TreeNode* root, int target) {
if (!root) return false ;
if (root->val == target) return true ;
return dfsFind(root->left, target) ||
dfsFind(root->right, target);
}
🎯 三、常见搜索问题
3.1 求二叉树的最大/最小深度
int maxDepth(TreeNode* root) {
if (!root) return 0 ;
return max(maxDepth(root->left), maxDepth(root->right)) + 1 ;
}
3.2 判断是否对称
bool isSymmetric(TreeNode* r1, TreeNode* r2) {
if (!r1 && !r2) return true ;
if (!r1 || !r2) return false ;
return r1->val == r2->val &&
isSymmetric(r1->left, r2->right) &&
isSymmetric(r1->right, r2->left);
}
💡 BST 搜索 = 二分思想在树上的应用。普通二叉树搜索 = DFS/BFS 遍历。
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"BST 搜索剪枝、普通二叉树遍历、递归求深度与对称判断"核心知识点。
📌 第 1 题 在平衡 的 BST 中查找一个值，时间复杂度为（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n²)
📌 第 2 题 BST 查找时，如果目标值 > 当前节点值，下一步应该去（ ）。
A. 左子树
B. 右子树（BST 左小右大）
C. 直接返回
D. 左右都要检查
📌 第 3 题 递归求二叉树最大深度 的正确公式是（ ）。
A. max(左深, 右深)
B. max(左深, 右深) + 1
C. 左深 + 右深
D. min(左深, 右深) + 1
📌 第 4 题 判断二叉树是否对称 ，递归比较的是（ ）。
A. r1左 = r2左 且 r1右 = r2右
B. r1左 = r2右 且 r1右 = r2左（镜像比较）
C. 只比较值，不比较结构
D. 只比较结构，不比较值
📌 第 5 题 在普通二叉树（非 BST）中查找值，必须（ ）。
A. 遍历所有节点直到找到（无法剪枝）
B. 只需沿着一条路径查找
C. O(log n) 一定能找到
D. 使用二分查找
📌 第 6 题 关于 BST（二叉搜索树），以下错误的是 （ ）。
A. 可以利用"左小右大"剪枝
B. 查找时间复杂度一定是 O(log n)
C. 最坏情况（退化成链表）查找是 O(n)
D. 中序遍历 BST 得到升序序列
📊 真题考点统计 ：GESP 六级二叉树搜索考点包括 ① BST 剪枝思想与 O(h) 复杂度 ② BST 退化场景（链表 O(n)）③ 普通二叉树的 DFS/BFS 查找 ④ 最大深度递归公式 ⑤ 对称判断的镜像比较。常出概念判断和读代码题。
📋 第8课：简单动态规划 记住过去，避免重复——DP 是递推的升级版，竞赛中最核心的算法思想。
📖 故事导入
🐰 还记得斐波那契的递归版本吗？fib(50) 要算几十亿次。但如果把算过的结果记下来，每个只算一次——这就是动态规划 （DP）的核心：记忆化，避免重复计算 。
🧱 一、DP 三要素
状态定义 ：dp[i] 表示什么？状态转移方程 ：dp[i] 如何从之前的状态推出来？初始条件 + 边界
🪜 二、一维 DP 经典题
2.1 爬楼梯（每次 1 或 2 级）
dp[1 ] = 1 ; dp[2 ] = 2 ;
for (int i = 3 ; i <= n; i++)
dp[i] = dp[i-1 ] + dp[i-2 ];
2.2 最大子段和
给定数组 a[1..n]，求最大连续子数组和。
int maxSubArray(int a[], int n) {
int cur = a[1 ], ans = a[1 ];
for (int i = 2 ; i <= n; i++) {
cur = max(a[i], cur + a[i]); // 要么单开，要么接上
ans = max(ans, cur);
}
return ans;
}
2.3 最长上升子序列（LIS）
for (int i = 1 ; i <= n; i++) {
dp[i] = 1 ;
for (int j = 1 ; j < i; j++)
if (a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1 );
}
🎒 三、0/1 背包问题
n 个物品，重量 w[i]，价值 v[i]，背包容量 W。每个物品要么选（1）、要么不选（0），求最大价值。
int dp[MAXW] = {0 }; // dp[j] = 容量j时的最大价值
for (int i = 1 ; i <= n; i++) {
for (int j = W; j >= w[i]; j--) { // 倒序！
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[W] << endl;
⚠️ 背包必须倒序 枚举容量，否则变成完全背包（每个物品可用无限次）！
💡 DP 解题步骤：① 定状态 ② 推方程 ③ 初始化 ④ 循环顺序。背包问题 0/1 倒序、完全正序 。
📝 五、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"DP 核心思想、状态转移、LIS 与 0/1 背包"核心知识点。
📌 第 1 题 动态规划（DP）的核心思想是（ ）。
A. 记忆化——保存子问题结果，避免重复计算
B. 分治——把大问题拆成独立子问题
C. 贪心——每一步选最优
D. 排序优化
📌 第 2 题 爬楼梯问题 dp[i] = dp[i-1] + dp[i-2] 的初始条件 是（ ）。
A. dp[0] = 0
B. dp[1] = 1, dp[2] = 2
C. dp[n] = 0
D. 不需要初始条件
📌 第 3 题 最大子段和 问题的正确转移方程是（ ）。
A. cur = a[i]
B. cur = max(a[i], cur + a[i])
C. cur = cur + a[i]
D. cur = a[i] + a[i-1]
📌 第 4 题 以下不属于 DP 三要素的是（ ）。
A. 状态定义
B. 状态转移方程
C. 初始条件
D. 排序
📌 第 5 题 0/1 背包中倒序枚举容量 的根本原因是（ ）。
A. 防止同一个物品被重复使用（每物最多选一次）
B. 为了排序
C. 方便调试
D. 正序/倒序无区别
📌 第 6 题 最长上升子序列（LIS），如果 a[j] < a[i]，则 dp[i] =（ ）。
A. max(dp[i], dp[j] + 1)
B. dp[j] + 1
C. dp[i] + 1
D. dp[i] - 1
📊 真题考点统计 ：GESP 六级 DP 考点包括 ① 记忆化思想（避免重复计算）② 三要素（状态、方程、初始条件）③ 爬楼梯/最大子段和/背包的基本转移 ④ 0/1 背包倒序枚举原因 ⑤ LIS O(n²) 写法。常出概念选择、填转移方程和读代码题。
🏛️ 第9课：面向对象与类的创建 从"图纸"到"实物"——用类和对象来组织代码，让程序像搭积木一样清晰。
📖 故事导入
🏭 玩具工厂有一张"小汽车设计图"——图上画了颜色、速度、编号。按照这张图纸，工厂可以造出红色的1号车、蓝色的2号车……图纸就是类（class） ，造出来的每一辆车就是对象（object） 。一张图纸 → 无数辆车，这就是面向对象的核心思想！
🧩 一、什么是"类"和"对象"？
用最简单的话说：
概念 类比 代码中
类（class） 设计图纸 / 模板 定义一种"新数据类型" 对象（object） 按图纸造出的实物 用这个类型创建的"变量"
你已经学过 int a = 5;——int 是一个类型，a 是一个变量。类就是让你自己定义新类型 ！比如定义一个 Student 类型，然后创建 Student xiaoming;。
👶 二、最简单的类：一个学生
我们先从最最简单的例子开始——定义一个"学生"，只有名字和年龄两个属性：
#include <iostream>
#include <string>
using namespace std;
// 定义一个"学生"类
class Student {
public : // 公开的，外面可以访问
string name; // 属性1：名字
int age; // 属性2：年龄
// 行为：自我介绍
void introduce() {
cout << "我叫" << name << "，今年" << age << "岁。" << endl;
}
};
int main() {
// 创建一个学生对象（就像 int a; 创建一个整数变量）
Student xiaoming;
// 给属性赋值
xiaoming.name = "小明" ;
xiaoming.age = 12 ;
// 调用行为
xiaoming.introduce(); // 输出：我叫小明，今年12岁。
return 0 ;
}
🎉 恭喜！你已经写出了第一个类！xiaoming.name 就是用 对象名.属性名 来访问。
🏗️ 三、类的结构拆解
一个类由两样东西组成：
组成部分 叫什么 是什么 例子
① 数据 成员变量 / 属性 描述这个事物"有什么" name、age ② 函数 成员函数 / 方法 描述这个事物"能做什么" introduce()
记忆口诀 ：属性 = 名词（名字、年龄），方法 = 动词（自我介绍、跑步）。
class 类名 {
public : // ← 公开区域（外面能用的都放这里）
成员变量; // 属性：有什么
成员函数; // 方法：能做什么
}; // ← ⚠️ 别忘了这个分号！
🏭 四、一个类可以创建多个对象
这才是类的真正威力——一张图纸，造出无数对象 ，每个对象都有自己的属性值，互不干扰。
int main() {
Student s1, s2, s3; // 用一张图纸，造三个学生！
s1.name = "小红" ; s1.age = 11 ;
s2.name = "小刚" ; s2.age = 12 ;
s3.name = "小丽" ; s3.age = 13 ;
s1.introduce(); // 我叫小红，今年11岁。
s2.introduce(); // 我叫小刚，今年12岁。
s3.introduce(); // 我叫小丽，今年13岁。
return 0 ;
}
💡 就像 int a=1, b=2, c=3; 三个变量互不影响一样，s1.name 和 s2.name 也是独立的。
🔐 五、public 和 private——谁可以碰？
不是所有东西都应该让外面随便改！就像ATM 取款机 ：
🔘 public（公开的） ：屏幕、键盘——你能碰的部分
🔒 private（私有的） ：钱箱、内部电路——你不能直接碰，只能通过公开的操作来间接使用
class BankAccount {
private : // 私密区域——外面不能直接碰
double balance; // 余额（不能让人随便改！）
public : // 公开区域——外面可以用的
void deposit(double amount) { // 存钱
if (amount > 0 ) balance += amount;
}
double getBalance() { // 查看余额
return balance;
}
};
int main() {
BankAccount myAccount;
myAccount.deposit(100 ); // ✅ 通过公开的"存钱"操作
cout << myAccount.getBalance(); // ✅ 通过公开的"查看"方法
// myAccount.balance = 99999; // ❌ 编译错误！balance 是私有的
return 0 ;
}
为什么要这样做？ 防止"不小心"改错数据。比如余额不能是负数，通过 deposit() 方法可以在里面加判断。
🏗️ 六、构造函数——"出生"时自动执行
每个对象被创建时，能不能自动给它设好初始值？用构造函数（constructor） ！
class Student {
private :
string name;
int age;
public :
// 构造函数：名字和类名相同，没有返回值类型
Student(string n, int a) {
name = n;
age = a;
}
void introduce() {
cout << name << ", " << age << "岁" << endl;
}
};
int main() {
Student s1("小明" , 12 ); // 创建时直接给名字和年龄！
Student s2("小红" , 11 ); // 每个对象出生就有自己的值
s1.introduce(); // 小明, 12岁
s2.introduce(); // 小红, 11岁
return 0 ;
}
构造函数三特征 ：
① 函数名 = 类名（一模一样）
② 没有返回值类型（连 void 都不写）
③ 创建对象时自动调用
💡 如果不写构造函数，C++ 会自动生成一个"空"的默认构造函数（什么也不做）。
📋 七、三大访问权限总结
关键字 谁能访问？ 通俗理解
public 任何地方都能访问 🏠 客厅——谁来都能用 private 只有类自己的函数能访问 🔐 卧室——只有自己能进 protected 自己 + 子类能访问 👨👩👧 家庭区——自己和孩子能用
新手建议 ：属性设为 private，方法设为 public。这就是封装 ——把数据保护起来，只通过安全的方式操作。
⚽ 八、练一练：定义一个"足球运动员"
试着定义一个 Player 类，要求：
属性（private）：姓名 name、号码 number、进球数 goals
方法（public）：构造函数（设初始值）、进球 score()、显示信息 show()
class Player {
private :
string name;
int number;
int goals;
public :
// 构造函数
Player(string n, int num) {
name = n;
number = num;
goals = 0 ; // 新球员进球数从0开始
}
// 进球！
void score() {
goals++;
cout << name << " 进球了！总进球：" << goals << endl;
}
// 显示球员信息
void show() {
cout << number << "号 " << name
<< "，进球 " << goals << " 个" << endl;
}
};
int main() {
Player messi("梅西" , 10 );
Player ronaldo("C罗" , 7 );
messi.score(); // 梅西 进球了！总进球：1
messi.score(); // 梅西 进球了！总进球：2
ronaldo.score(); // C罗 进球了！总进球：1
messi.show(); // 10号 梅西，进球 2 个
ronaldo.show(); // 7号 C罗，进球 1 个
return 0 ;
}
🔄 九、class 和 struct 有什么区别？
你在四级学过 struct，它和 class 几乎一模一样！只有一个区别：
struct class
默认访问权限 public （公开）private （私有）
struct Point { int x, y; }; // x, y 默认 public
class Point { int x, y; }; // x, y 默认 private
除此之外完全一样！struct 也可以有函数、构造函数、public/private。习惯上：纯数据用 struct，有行为用 class 。
🧠 十、核心要点回顾
类 = 图纸
对象 = 实物
属性 = 有什么
方法 = 做什么
public = 公开
private = 私有
构造函数 = 出生时执行
问题 答案
类是什么？ 自定义的数据类型，把属性和行为打包在一起 对象是什么？ 用类创建出来的"变量"，每个对象有自己的属性值 为什么用 private？ 保护数据不被随意修改（封装） 构造函数的作用？ 创建对象时自动初始化属性 class 和 struct 区别？ 仅默认权限不同：class 默认 private，struct 默认 public
💡 面向对象三句话：① 用类把数据和操作打包 ② 用 private 保护数据 ③ 通过 public 方法安全操作。记住这三点，你就入门了！
📝 十一、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写。点击你认为正确的选项，系统会自动判断对错并显示解析。
📌 第 1 题 以下关于类和对象的说法，正确 的是（ ）。
A. 一个类只能创建一个对象
B. 类中定义的函数不能访问类中的变量
C. 类是对象的模板，对象是类的实例
D. 类中不能包含多个同名的函数
📌 第 2 题 阅读以下代码，输出结果是（ ）。
class Dog {
public :
string name;
Dog(string n) { name = n; }
void bark() { cout << name << ": 汪汪！" << endl; }
};
int main() {
Dog d1("旺财" );
Dog d2("来福" );
d1.bark();
d2.bark();
return 0 ;
}
A. 两行都输出"旺财: 汪汪！"
B. 两行都输出"来福: 汪汪！"
C. 第一行"旺财"，第二行"来福"
D. 编译错误
📌 第 3 题 以下代码的编译运行结果 是（ ）。
class Test {
private :
int x;
public :
Test() { x = 10 ; }
int getX() { return x; }
};
int main() {
Test t;
cout << t.x;
return 0 ;
}
A. 输出 10
B. 输出 0
C. 编译错误
D. 运行时崩溃
📌 第 4 题 以下关于构造函数 的说法，错误 的是（ ）。
A. 构造函数的名字必须和类名相同
B. 构造函数没有返回值类型（连 void 都不能写）
C. 构造函数在创建对象时自动调用
D. 一个类只能有一个构造函数
📌 第 5 题 阅读以下代码，输出结果是（ ）。
class Counter {
private :
int cnt;
public :
Counter() { cnt = 0 ; }
void add() { cnt++; }
int get() { return cnt; }
};
int main() {
Counter a, b;
a.add();
a.add();
b.add();
cout << a.get() << " " << b.get();
return 0 ;
}
A. 2 1
B. 3 3
C. 1 2
D. 2 2
📌 第 6 题 以下代码中，s1.name 的值是（ ）。
class Student {
public :
string name;
int age;
};
int main() {
Student s1;
Student s2;
s2.name = "小华" ;
s1 = s2;
s2.name = "小龙" ;
cout << s1.name;
return 0 ;
}
A. 小华
B. 小龙
C. （空字符串）
D. 编译错误
📊 真题考点统计 ：GESP 六级面向对象主要考察 ① 类与对象的概念区分 ② public/private 访问控制（高频！） ③ 构造函数特征与调用 ④ 多对象独立性 ⑤ 成员变量和成员函数的访问方式。题目通常以"读代码选输出"或"概念判断题"形式出现，每题 2 分。
📚 第10课：栈、队列与循环队列 两种最基础、最重要的线性数据结构——先入后出 vs 先入先出。
📖 故事导入
📚 栈像一摞盘子——后放上去的先拿（LIFO）。队列像排队买奶茶——先来的先买到（FIFO）。这两个简单的结构，是无数复杂算法的基础。
📚 一、栈（Stack）
LIFO ：Last In, First Out（后进先出）。
#include <stack>
stack <int > stk;
stk.push(1 ); // 入栈
stk.push(2 );
stk.push(3 );
cout << stk.top(); // 输出 3（栈顶）
stk.pop(); // 弹出栈顶
cout << stk.size(); // 输出 2
cout << stk.empty(); // 输出 0（false）
经典应用
括号匹配 ：遇左括号入栈，遇右括号弹栈检查表达式求值 ：中缀转后缀、后缀计算DFS 非递归实现
// 括号匹配
bool isValid(string s) {
stack <char > stk;
for (char c : s) {
if (c == '(' ) stk.push(')' );
else if (c == '[' ) stk.push(']' );
else if (c == '{' ) stk.push('}' );
else if (stk.empty() || stk.top() != c) return false ;
else stk.pop();
}
return stk.empty();
}
🚶 二、队列（Queue）
FIFO ：First In, First Out（先进先出）。
#include <queue>
queue <int > q;
q.push(1 ); // 入队
q.push(2 );
q.push(3 );
cout << q.front(); // 输出 1（队首）
cout << q.back(); // 输出 3（队尾）
q.pop(); // 弹出队首
cout << q.front(); // 输出 2
经典应用 ：BFS、任务调度、消息队列。
🔄 三、循环队列
用数组模拟队列，当 tail 到数组末尾时回到开头 ，充分利用空间。
const int MAXQ = 100 ;
int q[MAXQ], head = 0 , tail = 0 ;
// 入队
void enqueue(int x) {
q[tail] = x;
tail = (tail + 1 ) % MAXQ; // 循环！
}
// 出队
int dequeue() {
int x = q[head];
head = (head + 1 ) % MAXQ;
return x;
}
// 判空/判满
bool empty() { return head == tail; }
bool full() { return (tail + 1 ) % MAXQ == head; }
⚠️ 循环队列通常牺牲一个位置 来区分空和满。
💡 栈 = LIFO（递归/括号匹配）；队列 = FIFO（BFS/缓冲）。STL 中 stack 和 queue 默认用 deque 实现。
📝 四、真题演练 （点击选项作答）
以下题目参考 GESP 六级 C++ 历年真题风格编写，考察"栈的 LIFO、队列的 FIFO、括号匹配与循环队列"核心知识点。
📌 第 1 题 栈（Stack）的数据存取特征是（ ）。
A. 先进先出（FIFO）
B. 后进先出（LIFO）
C. 随机存取
D. 按大小存取
📌 第 2 题 队列（Queue）的数据存取特征是（ ）。
A. 先进先出（FIFO）
B. 后进先出（LIFO）
C. 随机存取
D. 按优先级存取
📌 第 3 题 用栈实现括号匹配 ，遇到左括号时应（ ）。
A. 弹出栈顶并检查
B. 入栈（等待右括号来匹配）
C. 忽略跳过
D. 直接返回 false
📌 第 4 题 循环队列的判空 条件是（ ）。
A. (tail + 1) % MAXQ == head
B. head == tail
C. tail == MAXQ
D. head == 0
📌 第 5 题 循环队列（牺牲一个位置）的判满 条件是（ ）。
A. (tail + 1) % MAXQ == head
B. head == tail
C. tail == MAXQ - 1
D. head == tail - 1
📌 第 6 题 关于 STL 的 stack 和 queue，以下正确的是 （ ）。
A. stack 取栈顶用 top()，queue 取队首用 front()
B. 两者存取规则完全相同
C. 两者都支持随机访问任意位置
D. 都可以用 front() 取元素
📊 真题考点统计 ：GESP 六级栈/队列考点包括 ① stack(LIFO)/queue(FIFO) 存取规则 ② 括号匹配算法流程 ③ 循环队列的 head/tail 取模操作 ④ 判空(head==tail)与判满((tail+1)%MAXQ==head) ⑤ STL 常用方法(top/front/push/pop)。常出概念对比和读代码题。
📐 第1课：数学库常用函数
<cmath> 是竞赛利器——sqrt、pow、abs、floor、round……掌握它们事半功倍！
📖 故事导入
📏 判断一个数是不是完全平方数？手写二分查找太麻烦。double t = sqrt(n); return t == floor(t); ——cmath 库一行搞定！
🧮 一、cmath 核心函数速查
函数 功能 示例 头文件
sqrt(x) 平方根 √x sqrt(16)=4.0 <cmath> pow(a,b) a 的 b 次幂 aᵇ pow(2,3)=8.0 <cmath> abs(x) 绝对值 |x| abs(-5)=5 <cstdlib> fabs(x) 浮点绝对值 fabs(-3.14)=3.14 <cmath> floor(x) 向下取整 ⌊x⌋ floor(3.7)=3.0 <cmath> ceil(x) 向上取整 ⌈x⌉ ceil(3.2)=4.0 <cmath> round(x) 四舍五入 round(3.5)=4.0 <cmath> log(x) 自然对数 ln(x) log(e)=1.0 <cmath> log10(x) 常用对数 lg(x) log10(100)=2.0 <cmath>
⚠️ 二、浮点数精度陷阱
double x = 0.1 + 0.2 ;
// x 可能等于 0.30000000000000004，不是精确的 0.3！
if (fabs(x - 0.3 ) < 1e-9 ) // 用容差判断
cout << "相等" ;
⚠️ 浮点比较用 fabs(a-b) < 1e-9 ，不要用 ==。sqrt 返回值也是浮点，需要 floor/round 处理。
🔢 三、实战技巧
// 判断是否完全平方数
bool isSquare(int n) {
int t = sqrt(n);
return t * t == n; // 转回 int 比较，避免浮点误差
}
// 交换两个变量（不用临时变量）
void swap(int & a, int & b) {
a ^= b ^= a ^= b; // 异或法（不推荐，可读性差）
}
// 最大值 / 最小值
int mx = max(a, max(b, c)); // #include <algorithm>
📋 四、algorithm 常用函数
函数 作用 复杂度
sort(a, a+n) 升序排序 O(n log n) reverse(a, a+n) 反转数组 O(n) min(a, b) / max(a, b) 最小/最大值 O(1) lower_bound(a, a+n, x) 第一个 ≥x 的位置 O(log n) next_permutation 全排列下一个 O(n) __gcd(a, b) 最大公约数(GNU) O(log n)
📝 五、真题演练 （点击选项作答）
📌 第1题 sqrt(x) 返回值的类型是（ ）。
A. int
B. float
C. double
D. 取决于x
📌 第2题 floor(3.7) 的值是（ ）。
A. 3
B. 3.0
C. 4
D. 4.0
📌 第3题 判断浮点数相等应使用（ ）。
A. a == b
B. fabs(a-b) < 1e-9
C. a != b
D. round(a)==round(b)
📌 第4题 ceil(3.2) 的值是（ ）。
A. 3
B. 3.0
C. 4
D. 4.0
📌 第5题 round(3.5) 的值是（ ）。
A. 3.0
B. 4.0
C. 3
D. 4
📌 第6题 判断 n 是否为完全平方数应（ ）。
A. sqrt(n)*sqrt(n)==n
B. int t=sqrt(n); return t*t==n
C. pow(n,0.5)为整数
D. n%sqrt(n)==0
📊 第2课：复杂动态规划
从一维到二维，01背包、最长公共子序列——DP 是七级竞赛的核心大题。
📖 故事导入
🎒 一个小偷背着容量有限的包，面前有 n 件物品，每件有价值有重量。每件只能选一次——怎么装价值最大？动态规划 （DP）来解这道经典的 0-1 背包！
🧠 一、DP 核心思想
动态规划 = 记忆化递推 。把大问题分解为重叠子问题，用数组记录中间结果避免重复计算。
要素 说明
状态定义 dp[i] 或 dp[i][j] 表示什么（最关键） 状态转移方程 dp[新] = f(dp[旧])（递推公式） 初始化 dp[0] 等基础值 遍历顺序 正向/逆向，影响正确性
🎒 二、0-1 背包问题
n 件物品，第 i 件重量 w[i]，价值 v[i]，背包容量 C。每件最多选一次，求最大总价值。
// dp[j] = 容量为 j 时的最大价值（一维优化）
int dp[C+1 ] = {0 };
for (int i = 1 ; i <= n; i++) // 枚举物品
for (int j = C; j >= w[i]; j--) // 逆序遍历容量！
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[C]; // 最大价值
⚠️ 关键：容量逆向遍历 ！j 从 C 到 w[i] 降序，保证每件物品只用一次。正向遍历会变成完全背包（物品无限用）。
📝 三、最长公共子序列（LCS）
求两字符串最长公共子序列（不要求连续）。
// dp[i][j] = s1前i个 与 s2前j个 的LCS长度
for (int i = 1 ; i <= n; i++)
for (int j = 1 ; j <= m; j++)
if (s1[i-1 ] == s2[j-1 ])
dp[i][j] = dp[i-1 ][j-1 ] + 1 ; // 匹配
else
dp[i][j] = max(dp[i-1 ][j], dp[i][j-1 ]); // 跳过
复杂度 O(nm)，n,m 为两串长度。
🏔️ 四、数字三角形（基础路径DP）
// 自底向上：dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1])
for (int j = 1 ; j <= n; j++) dp[n][j] = a[n][j]; // 底层初始化
for (int i = n-1 ; i >= 1 ; i--)
for (int j = 1 ; j <= i; j++)
dp[i][j] = a[i][j] + max(dp[i+1 ][j], dp[i+1 ][j+1 ]);
cout << dp[1 ][1 ]; // 最大路径和
💡 自底向上 避免边界判断，比自顶向下更简洁。最终答案在 dp[1][1]。
📝 五、真题演练 （点击选项作答）
📌 第1题 0-1背包一维优化中，容量循环方向是（ ）。
A. 正向（小到大）
B. 逆向（大到小）
C. 任意方向
D. 不需要循环
📌 第2题 动态规划的核心要素不包括（ ）。
A. 状态定义
B. 状态转移方程
C. 暴力枚举
D. 初始化
📌 第3题 LCS 算法 dp[i][j] 表示（ ）。
A. 最长连续子串
B. 前i前j的LCS长度
C. 编辑距离
D. 子串数量
📌 第4题 数字三角形从底向上DP，最终答案在（ ）。
A. dp[n][1]
B. dp[1][1]
C. dp[n][n]
D. 需要遍历底行
📌 第5题 0-1背包和完全背包的本质区别是（ ）。
A. 价值不同
B. 每件物品可选次数不同
C. 重量不同
D. 时间复杂度不同
📌 第6题 DP 相比纯递归的优势是（ ）。
A. 代码更短
B. 避免重复计算
C. 总是更快
D. 不需要数组
🕸️ 第3课：图的定义、存储与遍历
节点+边=图——邻接矩阵、邻接表、DFS、BFS，图论从这里起航。
📖 故事导入
🗺️ 城市是节点，公路是边——地图就是一张图 。想知道能不能从 A 走到 B？DFS 或 BFS 遍历一遍就知道了！
📐 一、图的基本概念
概念 含义
顶点 V 图中的节点，编号 1~n 边 E 连接两个顶点的关系 有向/无向 边有方向 vs 双向通行 权值 边的"代价"（距离、时间等） 连通图 任意两顶点间有路径 度 与顶点相连的边数（入度+出度）
💾 二、图的存储方式
2.1 邻接矩阵
int G[101 ][101 ]; // G[i][j]=1 表示 i→j 有边
// 加边
G[u][v] = 1 ; // 有向图
G[u][v] = G[v][u] = 1 ; // 无向图
优点：O(1) 查边。缺点：O(n²) 空间 ，稀疏图浪费。
2.2 邻接表
vector <int > G[100001 ]; // 推荐！
// 加边
G[u].push_back(v); // 有向图
// 无向图加两条
G[u].push_back(v); G[v].push_back(u);
优点：O(V+E) 空间 。竞赛首选。
💡 n≤1000 用邻接矩阵；n>1000 用邻接表。GESP 七级掌握两种方式。
🔍 三、图的遍历
3.1 DFS（深度优先搜索）
bool vis[100001 ];
void dfs(int u) {
vis[u] = true ; // 标记已访问
cout << u << " " ;
for (int v : G[u]) // 遍历邻接点
if (!vis[v]) dfs(v);
}
3.2 BFS（广度优先搜索）
queue <int > q;
vis[start] = true ; q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : G[u])
if (!vis[v]) {
vis[v] = true ;
q.push(v);
}
}
DFS BFS
结构 递归（栈） 队列 用途 连通性、拓扑 最短路径（无权） 复杂度 O(V+E) O(V+E)
📝 五、真题演练 （点击选项作答）
📌 第1题 以下图存储方式中空间效率最高的是（ ）。
A. 邻接矩阵
B. 邻接表
C. 直接存边
D. 都一样
📌 第2题 DFS 遍历图使用的数据结构是（ ）。
A. 队列
B. 栈（递归）
C. 堆
D. 集合
📌 第3题 BFS 遍历图可以求（ ）。
A. 无向图的最长路径
B. 无权图的最短路径
C. 图的连通分量数
D. 所有路径
📌 第4题 邻接矩阵的缺点是（ ）。
A. 无法表示图
B. 空间O(n²)浪费
C. 不能查边
D. 编码复杂
📌 第5题 有向图加一条 u→v 的边，邻接表代码是（ ）。
A. G[v].push_back(u)
B. G[u].push_back(v)
C. G[u][v]=1
D. push_back(u,v)
📌 第6题 DFS 和 BFS 的时间复杂度均为（ ）。
A. O(V)
B. O(E)
C. O(V+E)
D. O(V×E)
🌊 第4课：图论基本算法
Dijkstra 最短路径、Floyd 全源最短路、Prim/Kruskal 最小生成树——图论三件套。
📖 故事导入
🚗 导航软件怎么找最短路径？Dijkstra 算法像水波扩散——从起点开始，每次选最近的未访问节点扩展，直到到达终点。
🛤️ 一、Dijkstra 最短路径
适用 ：非负权图，求单源最短路径。
// 邻接表+优先队列 O((V+E)log V)
int dist[MAXN];
bool done[MAXN];
priority_queue<pair<
int ,
int >> pq;
// {距离,顶点}
fill(dist, dist+n+
1 , INF);
dist[start] =
0 ; pq.push({
0 , start});
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (done[u])
continue ;
done[u] =
true ;
for (
auto [v, w] : G[u])
// 邻接点{v,边权}
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
// 负值实现小根堆
}
}
⚠️ 不能处理负权边 ！有负权用 Bellman-Ford 或 SPFA。Dijkstra 复杂度 O((V+E)log V)。
🌐 二、Floyd 全源最短路径
求任意两点间 的最短路径。简洁优雅，但 O(n³)。
// O(n³)，n≤500 可用
for (int k = 1 ; k <= n; k++) // 中转点
for (int i = 1 ; i <= n; i++)
for (int j = 1 ; j <= n; j++)
if (d[i][k]+d[k][j] < d[i][j])
d[i][j] = d[i][k] + d[k][j];
初始化：d[i][j] = 边权（无边=INF），d[i][i] = 0。
🌲 三、最小生成树（MST）
Kruskal（贪心+并查集）
// 按边权排序，用并查集避免成环
sort(edges, edges+m); // 边按权值升序
for (auto [w, u, v] : edges)
if (find(u) != find(v)) {
merge(u, v); ans += w;
}
算法 复杂度 适用
Kruskal O(E log E) 稀疏图首选 Prim O((V+E)log V) 稠密图
📝 五、真题演练 （点击选项作答）
📌 第1题 Dijkstra 算法不能 处理（ ）。
A. 有向图
B. 无向图
C. 负权边
D. 稀疏图
📌 第2题 Floyd 算法的时间复杂度是（ ）。
A. O(n)
B. O(n log n)
C. O(n²)
D. O(n³)
📌 第3题 Kruskal 算法求最小生成树用到（ ）数据结构。
A. 栈
B. 队列
C. 并查集
D. 二叉树
📌 第4题 Dijkstra 优先队列优化后复杂度为（ ）。
A. O(V²)
B. O((V+E)log V)
C. O(VE)
D. O(E log E)
📌 第5题 最小生成树包含（ ）条边（n个顶点）。
A. n
B. n-1
C. n+1
D. 不确定
📌 第6题 Floyd 算法中 k 循环在（ ）。
A. 最内层
B. 最外层
C. 中间层
D. 都可以
🔑 第5课：哈希表
O(1) 查数据！unordered_map 就是 C++ 的哈希表——空间换时间的极致。
📖 故事导入
📕 查数组要 O(n)。如果给每个值算一个"门牌号"（哈希值），直接对号入座——O(1) 就能找到 。这就是哈希表！
🔢 一、哈希函数
哈希函数 h(key) ：把任意类型的关键字映射到固定范围的整数。
// 常见哈希函数
int h(int key) { return key % MOD; } // 除留余数法
// 字符串哈希
int h(string s) {
int hash = 0 ;
for (char c : s)
hash = (hash * 131 + c) % MOD; // 常用BKDR哈希
return hash;
}
💡 MOD 通常取质数 （如 1000003、1000000007），减少哈希冲突。
⚔️ 二、哈希冲突解决
方法 原理 特点
链地址法 同位置用链表串起来 C++ unordered_map 的实现 开放地址法 冲突时找下一个空位 线性探测/二次探测 双哈希 用第二个哈希函数跳转 减少聚集
🛠️ 三、C++ 哈希容器
#include <unordered_map>
#include <unordered_set>
unordered_map<string , int > mp;
mp["apple" ] = 3 ;
mp.insert({"banana" , 5 });
if (mp.count("apple" )) // 是否存在
cout << mp["apple" ]; // 查询 O(1)
mp.erase("banana" ); // 删除 O(1)
unordered_set<int > st; // 只存键，不存值
st.insert(5 );
if (st.count(5 )) cout << "存在" ; // 去重利器
操作 unordered_map map
插入/查询/删除 O(1) 平均 O(log n) 有序性 无序 按键排序 实现 哈希表 红黑树
⚠️ 去重+计数场景首选 unordered_map 。如需有序遍历用 map。O(1) vs O(log n) 在大数据量下差异巨大。
📝 五、真题演练 （点击选项作答）
📌 第1题 unordered_map 的查找操作平均复杂度是（ ）。
A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)
📌 第2题 map 和 unordered_map 的主要区别是（ ）。
A. map更快
B. map有序、unordered_map无序
C. 没有区别
D. unordered_map用红黑树
📌 第3题 哈希冲突是指（ ）。
A. 函数运行错误
B. 不同key映射到相同位置
C. 哈希表满了
D. key不存在
📌 第4题 以下不是 解决哈希冲突的方法的是（ ）。
A. 链地址法
B. 开放地址法
C. 双哈希
D. 二分查找
📌 第5题 unordered_map 使用 count() 判断键是否存在，返回值是（ ）。
A. 键的值
B. 0 或 1
C. true/false
D. 键的哈希值
📌 第6题 unordered_set 最适合（ ）场景。
A. 排序
B. 去重
C. 二分查找
D. 前缀和
🎲 第1课：排列组合与计数原理
加法原理、乘法原理、排列、组合——计数是八级竞赛的数学基础。
📖 故事导入
👕 小明有 3 件上衣、4 条裤子，一共有几种穿搭？3×4=12 种——这就是乘法原理。如果再加 2 双鞋：12×2=24 种。层层递进，轻松计数！
🧮 一、两大计数原理
原理 描述 示例
加法原理 分类完成，方案相加 从A到B：火车3种+飞机2种=5种 乘法原理 分步完成，方案相乘 上衣3×裤子4=12种搭配
💡 "或"用加法、"且"用乘法 。分类互斥用加法，分步连续用乘法。
📐 二、排列（Permutation）
从 n 个元素中选 r 个有序排列 ：
P(n,r) = n! / (n-r)! = n×(n-1)×...×(n-r+1)
// 计算 P(n, r)
long long P(int n, int r) {
long long ans = 1 ;
for (int i = 0 ; i < r; i++)
ans *= (n - i);
return ans;
}
🔢 三、组合（Combination）
从 n 个元素中选 r 个无序组合 ：
C(n,r) = n! / (r!×(n-r)!)
// 递推求组合数 C(n,r) = C(n-1,r-1) + C(n-1,r)
long long C[50 ][50 ];
for (int i = 0 ; i <= n; i++) {
C[i][0 ] = C[i][i] = 1 ;
for (int j = 1 ; j < i; j++)
C[i][j] = C[i-1 ][j-1 ] + C[i-1 ][j];
}
⚠️ 爆炸增长 ：C(50,25) ≈ 1.26×10¹⁴，远超 int。竞赛常用组合数取模 （逆元+Lucas定理）。
📋 四、常用组合恒等式
公式 含义
C(n,r) = C(n, n-r) 对称性 C(n,0)+C(n,1)+...+C(n,n) = 2ⁿ 子集总数 C(n,r)=C(n-1,r-1)+C(n-1,r) 递推（杨辉三角）
📝 五、真题演练 （点击选项作答）
📌 第1题 从 5 人中选 3 人排成一排，有（ ）种排法。
A. C(5,3)=10
B. P(5,3)=60
C. 5³=125
D. 3⁵=243
📌 第2题 C(5,2) 的值是（ ）。
A. 5
B. 10
C. 20
D. 25
📌 第3题 乘法原理适用于（ ）的情况。
A. 分类互斥
B. 分步连续
C. 两者都适用
D. 都不适用
📌 第4题 C(n,0) 的值是（ ）。
A. 0
B. 1
C. n
D. n!
📌 第5题 以下错误 的是（ ）。
A. P(n,n)=n!
B. C(n,1)=n
C. C(n,r)=P(n,r)/r!
D. P(n,r)=C(n,r)×n!
📌 第6题 子集个数公式 2ⁿ 来自（ ）。
A. 排列
B. 加法原理
C. 二项式定理
D. 乘法原理
🔺 第2课：杨辉三角与组合数
递推求组合数、Lucas 定理、卡特兰数——杨辉三角是组合数学的基石。
📖 故事导入
🔺 中国古代数学家杨辉发现了这个神奇的三角形：每个数=上方两数之和。第 n 行第 r 个数恰好就是 C(n, r) ——组合数与杨辉三角一一对应！
🔺 一、杨辉三角与组合数
// 打印前 n 行杨辉三角
for (int i = 0 ; i < n; i++) {
C[i][0 ] = C[i][i] = 1 ;
for (int j = 1 ; j < i; j++)
C[i][j] = C[i-1 ][j-1 ] + C[i-1 ][j];
}
// 前5行：
// 1
// 1 1
// 1 2 1
// 1 3 3 1
// 1 4 6 4 1
第 i 行第 j 个数 = C(i, j) 。递推复杂度 O(n²)，n≤2000 适用。
⚡ 二、组合数取模与 Lucas 定理
当 n 很大（n≤10¹⁸）且模数 p 是质数时：
// Lucas 定理：C(n, r) mod p
long long Lucas(long long n, long long r, long long p) {
if (r == 0 ) return 1 ;
return C(n % p, r % p) * Lucas(n / p, r / p, p) % p;
}
// C(n, r) 用阶乘+逆元计算 O(log p)
💡 Lucas 定理 ：C(n,r) ≡ ∏C(nᵢ, rᵢ) (mod p)，其中 nᵢ, rᵢ 是 n, r 在 p 进制下的每一位。
📊 三、常见组合数递推
问题 递推公式
组合数 C(n,r)=C(n-1,r-1)+C(n-1,r) 卡特兰数 h(n)=∑h(i)·h(n-1-i), h(0)=1 斯特林数(第一类) s(n,k)=s(n-1,k-1)+(n-1)s(n-1,k)
⚠️ 卡特兰数 ：h(n)=C(2n,n)/(n+1)。应用：合法括号序列、出栈序列数、二叉搜索树形态数。
📝 五、真题演练 （点击选项作答）
📌 第1题 杨辉三角第4行第2个数（从0行0列开始）是（ ）。
A. 4
B. 6
C. 3
D. 2
📌 第2题 C(10,3) 的值是（ ）。
A. 30
B. 60
C. 120
D. 720
📌 第3题 卡特兰数 h(3) 的值是（ ）。
A. 3
B. 5
C. 14
D. 42
📌 第4题 Lucas 定理适用于模数 p 为（ ）的情况。
A. 任意数
B. 质数
C. 合数
D. 2的幂
📌 第5题 C(n,0)+C(n,1)+...+C(n,n) 等于（ ）。
A. n
B. 2ⁿ
C. n!
D. n²
📌 第6题 杨辉三角递推求组合数的时间复杂度是（ ）。
A. O(n)
B. O(n log n)
C. O(n²)
D. O(2ⁿ)
⚡ 第3课：倍增法
每次跳 2ᵏ 步——LCA、RMQ、快速幂都是倍增的经典应用，O(log n) 的神器。
📖 故事导入
🏃 百米冲刺一次一步太慢。如果先跳 64m、再 32m、16m、8m……用二进制拆分步长——任何距离都能用 O(log n) 次跳跃覆盖 ！这就是倍增思想。
🧠 一、倍增核心思想
预处理出每个位置跳 2ᵏ 步后到达的位置 ，查询时用二进制拆分大步跳跃。
// up[u][k] = 节点 u 向上跳 2^k 步到达的祖先
for (int k = 1 ; k <= LOG; k++)
for (int u = 1 ; u <= n; u++)
up[u][k] = up[ up[u][k-1 ] ][k-1 ];
// 跳 2^k = 先跳 2^(k-1) 再跳 2^(k-1)
🌳 二、LCA（最近公共祖先）
// 倍增法求 LCA，O(log n) 每次
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
// 把 u 跳到与 v 同一深度
int diff = depth[u] - depth[v];
for (int k = 0 ; diff; k++, diff >>= 1 )
if (diff & 1 ) u = up[u][k];
if (u == v) return u;
// 一起向上跳到 LCA 的下一层
for (int k = LOG; k >= 0 ; k--)
if (up[u][k] != up[v][k])
u = up[u][k], v = up[v][k];
return up[u][0 ];
}
💡 预处理 O(n log n)，查询 O(log n) 。LCA 是树上问题的基础（树上距离=dep[u]+dep[v]-2×dep[lca]）。
📊 三、ST 表（RMQ）
// st[k][i] = 从 i 开始长度 2^k 区间的最值
for (int i = 1 ; i <= n; i++) st[0 ][i] = a[i];
for (int k = 1 ; k <= LOG; k++)
for (int i = 1 ; i + (1 <<k) - 1 <= n; i++)
st[k][i] = max(st[k-1 ][i], st[k-1 ][i+(1 <<(k-1 ))]);
// 查询 [L,R] 的最大值，O(1)
int k = log2(R - L + 1 );
return max(st[k][L], st[k][R-(1 <<k)+1 ]);
关键：两段能重叠 的区间覆盖（max 运算重叠不影响结果）。
📝 五、真题演练 （点击选项作答）
📌 第1题 倍增法的核心是预处理（ ）步长。
A. 1,2,3...
B. 2的幂次
C. 斐波那契数列
D. 任意步长
📌 第2题 倍增法求 LCA 的查询复杂度是（ ）。
A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
📌 第3题 ST 表查询 RMQ 的复杂度是（ ）。
A. O(log n)
B. O(1)
C. O(n)
D. O(n log n)
📌 第4题 LCA 的预处理需要 up[u][k] 数组，k 的范围到（ ）。
A. n
B. log₂n
C. 1
D. n/2
📌 第5题 ST 表适用于（ ）运算。
A. 任何
B. 可重复贡献（max/min/gcd）
C. 只能求和
D. 只能排序
📌 第6题 树上两点距离公式（已知LCA）是（ ）。
A. dep[u]+dep[v]
B. dep[u]+dep[v]-dep[lca]
C. dep[u]+dep[v]-2×dep[lca]
D. dep[u]×dep[v]
📐 第4课：代数与平面几何
向量、叉积、点到直线距离——数学库用得好，几何题变简单。
📖 故事导入
📏 判断三个点是否共线？用斜率怕除零。向量叉积 ：AB×AC=0 则共线——没有除法，整数运算，精确无误！
📐 一、向量与点
struct Point {
double x, y;
Point operator +(Point b) { return {x+b.x, y+b.y}; }
Point operator -(Point b) { return {x-b.x, y-b.y}; }
};
// 向量 A→B = B - A
Point vec = B - A;
✖️ 二、叉积（Cross Product）
a × b = a.x × b.y - a.y × b.x
double cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
// 叉积应用
// cross > 0: b在a的逆时针方向
// cross < 0: b在a的顺时针方向
// cross = 0: a与b共线
应用 公式
三点共线 cross(B-A, C-A) == 0 三角形有向面积 cross(B-A, C-A) / 2 点在直线哪侧 根据 cross 正负判断 凸包 Graham 扫描基于叉积
📏 三、常用几何公式
问题 公式
两点距离 sqrt((x₁-x₂)²+(y₁-y₂)²) 点到直线距离 |cross(P-A, B-A)| / dist(A,B) 线段相交 跨立实验（叉积异号） 多边形面积 ∑cross(Pᵢ, Pᵢ₊₁)/2（顶点逆时针）
⚠️ 浮点精度 ：几何计算中判断 ==0 用 fabs(x) < 1e-9 。能用叉积就别用除法（除零风险）。
📝 五、真题演练 （点击选项作答）
📌 第1题 叉积 cross(a,b) = 0 表示（ ）。
A. a < b
B. a 与 b 垂直
C. a 与 b 共线
D. a > b
📌 第2题 三点共线的判断公式是（ ）。
A. cross(B-A, C-A) == 0
B. dot(B-A, C-A) == 0
C. dist(A,B) == dist(B,C)
D. (B-A)+(C-A)==0
📌 第3题 三角形 ABC 有向面积公式是（ ）。
A. cross(A,B)/2
B. cross(B-A, C-A)/2
C. abs(A.x*B.y)/2
D. dist(A,B)*dist(B,C)/2
📌 第4题 平面上两点距离公式使用（ ）。
A. 叉积
B. 点积
C. 勾股定理
D. 余弦定理
📌 第5题 点在直线哪一侧通过（ ）判断。
A. 点积正负
B. 叉积正负
C. 距离大小
D. 角度大小
📌 第6题 多边形面积计算要求顶点（ ）。
A. 任意顺序
B. 顺/逆时针排列
C. 随机
D. 按x坐标排序
🌉 第5课：最小生成树
Kruskal + Prim——用最少代价连通所有节点，图论经典问题。
📖 故事导入
🔌 n 个村庄要全部通电。架电线越短越省钱——怎样用总长度最短 的线路连通所有村庄？这就是最小生成树（MST） 问题。
🧩 一、MST 定义与性质
最小生成树 ：连通图中，边权之和最小的树（包含所有顶点，无环）。
性质 说明
边数 n 个顶点→恰好 n-1 条边 唯一性 边权全不同时 MST 唯一 割性质 任意割中最小边必在 MST 中
🦅 二、Kruskal（边贪心+并查集）
struct Edge { int u, v, w; };
bool operator <(Edge a, Edge b) { return a.w < b.w; }
int parent[MAXN];
int find(int x) { return x==parent[x] ? x : parent[x]=find(parent[x]); }
void join(int a, int b) { parent[find(a)] = find(b); }
int kruskal(vector <Edge>& e, int n) {
sort(e.begin(), e.end());
for (int i=1 ;i<=n;i++) parent[i]=i;
int ans=0 , cnt=0 ;
for (auto [u,v,w] : e)
if (find(u)!=find(v))
join(u,v), ans+=w, cnt++;
return cnt==n-1 ? ans : -1 ; // -1表示不连通
}
复杂度 O(E log E) ，稀疏图首选。
🔥 三、Prim（点贪心+优先队列）
int prim(
vector <pair<
int ,
int >> G[],
int n) {
bool vis[MAXN]={
false };
priority_queue<pair<
int ,
int >> pq;
// {负权, 顶点}
pq.push({
0 ,
1 });
// 从1号点开始
int ans=
0 , cnt=
0 ;
while (!pq.empty() && cnt<n) {
auto [w,u] = pq.top(); pq.pop();
if (vis[u])
continue ;
vis[u]=
true ; ans+=-w; cnt++;
for (
auto [v,w2] : G[u])
if (!vis[v]) pq.push({-w2, v});
}
return cnt==n ? ans : -
1 ;
}
Kruskal Prim
策略 选最小边 选最近点 数据结构 并查集 优先队列 适用 稀疏图 稠密图
📝 五、真题演练 （点击选项作答）
📌 第1题 Kruskal 算法用到的数据结构是（ ）。
A. 栈
B. 队列
C. 并查集
D. 哈希表
📌 第2题 MST 中 n 个顶点的边数是（ ）。
A. n
B. n-1
C. n+1
D. 2n
📌 第3题 Kruskal 的时间复杂度是（ ）。
A. O(E)
B. O(E log E)
C. O(V²)
D. O(V+E)
📌 第4题 Prim 算法适合（ ）。
A. 稀疏图
B. 稠密图
C. 有向图
D. 无权图
📌 第5题 Kruskal 中判断两点连通用（ ）。
A. DFS
B. BFS
C. find(x)
D. 距离比较
📌 第6题 MST 边权全部不同时，MST（ ）。
A. 不唯一
B. 唯一
C. 不存在
D. 有多个
🛤️ 第6课：单源最短路
Dijkstra + SPFA + 负环检测——从起点到所有点的最短路径，图论核心算法。
📖 故事导入
🚀 导航不仅要找到路，还要找最短 的路！Dijkstra 像水波扩散——从起点一层层扩展到最近的点。但要小心负权边 这个"陷阱"！
⚡ 一、Dijkstra（非负权）
// 邻接表+优先队列 O((V+E)log V)
int dist[MAXN];
bool done[MAXN];
priority_queue<pair<
int ,
int >> pq;
// {负距离, 顶点}
fill(dist, dist+n+
1 , INF);
dist[s]=
0 ; pq.push({
0 , s});
while (!pq.empty()) {
int u = pq.top().second; pq.pop();
if (done[u])
continue ;
done[u] =
true ;
for (
auto [v, w] : G[u])
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
⚠️ Dijkstra 不能处理负权边 （被 done 标记后不再更新）。负权用 SPFA 或 Bellman-Ford。
🌀 二、SPFA（队列优化 Bellman-Ford）
int dist[MAXN], cnt[MAXN]; bool inq[MAXN];
queue<int > q;
fill(dist, dist+n+1 , INF);
dist[s]=0 ; q.push(s); inq[s]=true ;
while (!q.empty()) {
int u = q.front(); q.pop(); inq[u]=false ;
for (auto [v, w] : G[u])
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!inq[v]) {
q.push(v); inq[v]=true ;
if (++cnt[v] > n) return false ; // 负环!
}
}
}
SPFA 最坏 O(VE) 可能被卡，竞赛中用 cnt[v]≥n 检测负环。
📊 三、算法对比
算法 复杂度 负权 负环检测
Dijkstra O((V+E)log V) ❌ ❌ SPFA O(kE)~O(VE) ✅ ✅ Floyd O(V³) ✅ ✅
📝 五、真题演练 （点击选项作答）
📌 第1题 Dijkstra 不能处理（ ）。
A. 无向图
B. 稀疏图
C. 负权边
D. 有向图
📌 第2题 Dijkstra 优先队列优化的复杂度是（ ）。
A. O(V²)
B. O((V+E)log V)
C. O(VE)
D. O(E log E)
📌 第3题 SPFA 相比 Bellman-Ford 的优势是（ ）。
A. 总是O(VE)
B. 队列优化减少无效松弛
C. 不能检测负环
D. 更快找到最长路
📌 第4题 SPFA 检测负环通过（ ）。
A. 比较边数
B. 判断 cnt[v] ≥ n
C. 比较优先级
D. 判断 dist 是否为 INF
📌 第5题 无负权边时最短路首选（ ）。
A. SPFA
B. Dijkstra
C. Floyd
D. Kruskal
📌 第6题 Floyd 算法求全源最短路，复杂度是（ ）。
A. O(V²)
B. O(V³)
C. O(VE)
D. O(V log V)
⏱️ 第7课：算法时空效率分析与优化
时间复杂度、空间复杂度、常数优化、I/O优化——最后一课，让算法从"能跑"到"飞起来"！
📖 故事导入
🏎️ 同样的算法，有人写 O(n log n) 100ms 跑完，有人写 5 秒超时。差距在哪？常数优化 和输入输出优化 ——八级竞赛的"隐形分数"！
📊 一、复杂度→数据范围速判
数据 n 可接受复杂度 典型算法
n ≤ 10 O(n!), O(2ⁿ) 全排列、子集枚举 n ≤ 20 O(2ⁿ), O(n²·2ⁿ) 状态压缩 DP n ≤ 100 O(n³) Floyd、区间 DP n ≤ 500 O(n³) 一般 DP n ≤ 10³ O(n²) 基础 DP n ≤ 10⁵ O(n log n) 排序、Dijkstra n ≤ 10⁶ O(n) 线性筛、贪心、BFS n ≤ 10⁷ O(n) 常数小 桶排序、简单遍历
⚡ 二、常数优化技巧
// 1. 位运算代替乘除2
x << 1 ; // 代替 x*2
x >> 1 ; // 代替 x/2
x & 1 ; // 代替 x%2
// 2. 减少函数调用开销
inline int max(int a,int b) {return a>b?a:b;}
// 3. 寄存器变量（O2自动优化）
for (register int i=0 ; i<n; i++) ...
📥 三、输入输出优化
// 关闭同步流（最常用）
ios::sync_with_stdio(false );
cin.tie(0 ); cout.tie(0 );
// 快读模板（百万级数据必备）
inline int read() {
int x=0 ,f=1 ;char c=getchar();
while (c<'0' ||c>'9' ){if (c=='-' )f=-1 ;c=getchar();}
while (c>='0' &&c<='9' ){x=x*10 +c-'0' ;c=getchar();}
return x*f;
}
// 用
替代 endl（endl 会刷新缓冲区）
cout << ans << '
' ;
💡 cout << endl ≈ cout << '
' << flush 。竞赛中大量输出用
，endl 慢 10 倍以上。
📋 四、优化优先级
算法优化（降复杂度） > 常数优化 > I/O 优化
n 差 10 倍 → 复杂度必须降一档。先分析瓶颈再优化，避免"局部最优、全局无用"。
📝 五、真题演练 （点击选项作答）
📌 第1题 n=10⁶ 时，必须使用的复杂度是（ ）。
A. O(n log n)
B. O(n)
C. O(n²)
D. O(2ⁿ)
📌 第2题 以下不能 减少 I/O 时间的是（ ）。
A. ios::sync_with_stdio(false)
B. 用 \n 代替 endl
C. 使用快读
D. 多用 cin/cout
📌 第3题 cout << endl 慢的原因是（ ）。
A. 输出字数多
B. 会刷新缓冲区
C. 用了函数调用
D. 换行符慢
📌 第4题 算法优化中优先级最高的是（ ）。
A. I/O优化
B. 常数优化
C. 降低时间复杂度
D. 位运算
📌 第5题 位运算 x>>1 等价于（ ）。
A. x*2
B. x/2
C. x%2
D. x&1
📌 第6题 关闭 cin/cout 同步后（ ）。
A. 不能用 printf
B. 不能混用 scanf/printf 和 cin/cout
C. 程序变慢
D. 不能用 cin
>