四级考纲
- 指针
- 函数与结构体
- 二维及多维数组
- 递推算法
- 排序算法
- 文件操作
- 异常处理
- 简单算法复杂度的估算
知识点解析
一.指针
主要内容：指针类型，指针类型定义变量，指针类型变量赋值、解引用
指针类型
指针，用来描述内存地址，并通过指针操作来实现与内存相关的程序功能。
数据类型* ——表示指向该数据类型变量的指针
指针类型定义变量
数据类型 变量名; // int p;表示指向整型变量的指针p
指针类型变量的赋值
int *p,*q,*fp; int x; p=&x;//p指向x的地址,p的类型是int*,&x的类型也是int* q=p;//将指针p内的地址赋值给指针q fp=new int;//申请一个int类型空间并将地址赋值给指针fp&是取地址符
解引用
我们可以通过"*指针变量"来访问指针指向的内存空间，成为解引用
int a; int *p=&a; *p=3;//相当于a=3;注意：解引用一定要保证，指针所指向的内存空间是可以访问的。
数组名指针，它存放了第一个元素的地址(首地址)
指针大小
指针大小取决于编译环境，不能用数据类型去计算指针的大小。int char double*等指针的大小其实都是4/8字节。
- 32 位系统(x86)：指针大小为 4 字节
- 64 位系统(x64)：指针大小为 8 字节
真题举例
1.执行下述代码后，变量 a 的值为（ ）。
int a = 10;
int* p = &a;
*p = 20;
A. 10 B. 20 C. 随机值 D. 编译错误
2. 指针的大小与其所指向的变量的数据类型的大小相同。
正确 错误
3.假设整数数组 arr[4]= {0, 1, 2, 3}; 的第一个元素在内存中的地址为 0x7ffee4065820 , 经过 int* p
= arr; p += 1; 后，指针 p 的值是1。
正确 错误
4.在 C++ 中，下面代码可以正确定义指针和初始化指针。
int* ptr;
*ptr = 10;
正确 错误
5.运行下面代码，屏幕上输出是（ ）。
int arr[3] = {24, 9, 7};
int* p = arr;
p++;
cout << *p << endl;
A. 24 B. 9 C. 7 D. 不确定
6.运行下面代码片段的结果是（ ）。
int x = 20;
int y = 24;
int* p = &x;
int* q = &y;
p = q;
A. 将x赋值为24 B. 将y赋值为20
C. 将q指向x的地址 D. 将p指向y的地址
二. 函数与结构体
函数的定义、调用、声明
函数的定义
返回类型 函数名(形参){ 函数体 return 返回值; }返回类型：返回值的类型。如果没有返回值为 void 类型
形式参数简称形参，可以为空，是函数定义时的参数；实际参数简称实参，是函数调用时传递的参数；形参与实参必须一致
函数的调用
格式：函数名(实参)
函数有返回值时，函数调用得到的返回值可以给变量变量赋值或参与运算
函数的声明：返回类型 函数名(形参)；
如果函数的定义是在调用函数的下面，则需要在调用之前声明函数的定义，否则不需要事先声明。
#include<bits/stdc++.h> using namespace std; int mymax(int a,int b); //函数声明 int main() { int a,b; cin>>a>>b; cout<<mymax(a,b)<<endl;//函数调用，a,b是实参 return 0; } //函数定义，x,y为形参 int mymax(int x,int y){ int ans=x; if(y>x) ans=y; return ans; }
形参、实参
形式参数：在函数定义阶段括号内声明的参数就叫形式参数，简称“形参”，形参本质就是一个变量名，用来接收外部传来的值。
实际参数：在函数调用阶段括号内传入的值，就叫实际参数，简称“实参”，值可以是常量、变量。
形参和实参的关系：形参相当于变量名，实参相当于变量值
全局作用域、局部作用域
int x,y;
void f(int c){
double d;
....
}
int main(){
int a,b;
...;
}
| 变量 | 全局与局部 | 作用域 |
|---|---|---|
| x,y | 全局 | f函数、main函数 |
| c、d | 局部 | f函数 |
| a、b | 局部 | main函数 |
变量按其在程序中作用的范围，分为全局变量和局部变量。全局变量是指在程序代码开始执行前初始化并分配存储空间的变量，它在程序的整个运行过程中都起作用，在静态数据区存储，在整个程序执行结束后释放存储空间。
局部变量是指在程序函数内部定义的变量，它只在函数内部起作用，在动态数据区存储，在函数调用时动态初始化，函数调用完毕后释放存储空间。函数的形参是局部变量。同一个函数同一个形参在两次不同调用过程中其存储空间往往是不相同的。
::是 C++ 中优先级最高的运算符，用于明确标识符（变量、函数、类等）的作用域归属，解决命名冲突问题。作用：访问被遮蔽的全局变量int x = 5; // 全局变量 void func() { int x = 10; ::x = 20; // 修改全局变量x cout<<::x; }
值传递、地址传递、引用传递
- 值传递：将a,b的值传给x,y,交换x,y，a,b的值不变。
- 引用传递：将a,b变量传给x,y,x,y相当于a,b的别名，交换x,y就会交换a,b.
- 地址传递：将a,b的地址传给指针变量x,y，解引用交换指针x,y指向的内存单元的内容，即交换a,b的值
//值传递
void swap1(int x, int y) { /* 定义中的x,y变量被称为swap1函数的形式参数 */
int tmp;
tmp = x;
x = y;
y = tmp;
printf("x = %d, y = %d \n", x, y);
}
//引用传递
void swap2(int &x, int &y) /* 定义的形式参数的格式与值传递不同 */
{
int tmp = x;
x = y;
y = tmp;
printf("x = %d, y = %d \n", x, y);
}
//地址传递
void swap3(int *x, int *y)
{
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
printf("x = %d, y = %d \n", *x, *y);
}
int main() {
int a = 4,b = 6;
swap1(a, b); /*a,b 变量为 swap1 函数的实际参数。*/
swap2(a, b); /*注意：这里调用方式与值传递一样*/
swap3(&a, &b);//地址传递
printf("a = %d, b = %d \n", a, b);
return 0;
}
数组参数
void work(int a[100],int n) //数组长度可以省略 void work(int a[],int n)
void work(int a[3] [5],int n,int m);//数组是按行来存储，二维数组可以省略第1维，
void work(int a[] [5],int n,int m);
结构体:用户自定义的允许存储不同类型数据项的数据结构。( 数组允许存储相同类型数据项的变量)。
struct 结构体名{
数据类型1 成员名1;
数据类型2 成员名2;
.....
};
初始化赋值
struct student{ string name;//姓名 int age;//年龄 }; Student xiaoming = {"小明",10};//统一赋值：使用 { } Student xiaoming; //分别赋值：变量名.属性名 xiaoming.name = "小明"; xiaoming.age = 10;
真题举例
1.执行下述代码将输出（ ）。
int x = 10;
void func() { int x = 20; std::cout << x; }
int main() {
func();
std::cout << x;
return 0;
}
A. 2020 B. 2010 B. 1010 D. 编译错误
2.一个函数必须在调用之前既声明又定义。
正确 错误
3.在C++中，形参与实参的关系描述正确的是（ ）。
A. 形参在函数调用时指定，实参在函数定义时传递
B. 形参在函数定义时指定，实参在函数调用时传递
C. 形参和实参可以互换
D. 形参和实参必须是完全相同的类型，不能有任何差异。
4.运行以下代码，屏幕上将输出（ ）。
#include <iostream>
using namespace std;
int var = 100;
void function() {
int var = 200;
cout << var << " ";
cout << ::var << " ";
}
int main() {
cout << var << " ";
function();
var += 100;
cout << var << " ";
return 0;
}
A. 100 200 100 200 B. 100 200 100 300
C. 100 200 200 200 D. 100 200 200 300
三. 二维及多维数组
二维及多维数组的定义
二维数组的定义：类型标识符 数组名[size11] [size2]
例如： int a[5] [3]
多维数组定义：类型标识符 数组名[size1] [size2]....[sizen]
例如：int[3] [4] [5]
二维及多维数组的引用：用下标来访问数组中的元素
如：二维数组引用a[2] [3]
注意：数组下标是从0到size-1,数组下标应该在有效范围内
二维数组初始化
int a[2] [3]={1,2,3,4,5,6};//按元素初始化
int a[2] [3]={{1,2,3},{4,5,6}};//按行初始化
其它常见考点
- 数组空间计算：size1*size2* ...* sizen * sizeof(数据类型).
- 二维及多维数组在内存中存储本质上是一个一维数组；二维数组是按行存储的。
真题举例
1.假设 int arr[2][3] = {{1,2,3},{4,5,6}}; ，则 arr[1][2] 的值是（ ）。
A.2 B.3 C.5 D.6
2.二维数组作为函数参数时，必须显式指定所有维度的大小。
正确 错误
3.下面（ ）正确定义二维数组。
A. int a[3][];
B. int a[][];
C. int a[][4];
D. int a[][2] = {{1,2},{1,2},{3,4}};
4.一个二维数组定义为 int arr[3][4]; （假设一个int变量占4个字节），则 int arr[0] 占用（ ）个字节
的内存。
A. 3 B. 4 C. 12 D. 16
5.二维数组的行的大小的必须在定义时确定，列的大小可以动态变化。
正确 错误
四.递推算法
基本思想
从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。
递推则是由“边界”往“结果”一步步求解。
真题举例
1.小杨正在爬楼梯，需要爬 阶才能到达楼顶。如果每次可以爬 个或 个台阶，下面代码采用递推算法来计算
一共有多少种不同的方法可以爬到楼顶，则横线上应填写（ ）。
int f(int n) {
if (n == 1 || n == 2)
return n;
int f1 = 1;
int f2 = 2;
int res = 0;
for (int i = 3; i <= n; i++) {
________________________________ // 在此处填入代码
}
return res;
}
A. B. C. D.
res += f1 + f2; res = f1 + f2; res += f1 + f2; res = f1 + f2;
f1 = f2; f1 = f2; f2 = res; f2 = res;
f2 = res; f2 = res; f1 = f2; f1 = f2;
五.排序算法
从小到大排序 3 2 4 5 1
| 排序算法 | 冒泡排序 | 选择排序 | 插入排序 |
|---|---|---|---|
| 算法思想 | 从前往后两两比较相邻元素的值，若为逆序,则交换它们，直到序列比较完，成为第一趟冒泡，结果是最大的元素交换到最后一个位置,最大的元素如气泡一样逐渐向上“漂浮”。最终一个一个排好了位置。 | 每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后从剩余未排序元素中继续寻找最小的元素，然后放到已排序序列的末尾，以此类推，直到全部待排序的数据元素排完。 | 开始时，第一个元素是有序的，将第2个元素插入到已经排好序的序列中(从后往前扫描已经排序的数列，大于元素则往后移动位置),再将第三个元素插入......直到最后一个元素插入，排序完成。 |
| 算法实现 | |||
| 时间复杂度 | |||
| 空间复杂度 | |||
| 稳定性 | 稳定 | 不稳定 | 稳定 |
稳定性：相等的元素经过排序之后相对顺序是否发生了改变
- 稳定：如果排序前a在b的前面，且a==b,排序之后a仍然在b前面，称该算法稳定
- 不稳定：如果排序前a在b前面，且a==b,排序之后a可能在b后面,称该算法不稳定
计数排序：是一种特殊的桶排序。桶的个数是可能出现的数据种类数。
计数数组：数组下标是桶的编号，通常为数据值，数组的值表示数据个数。
适用条件：待排序数据为整数，数据范围有限。
sort排序
sort(begin,end,[cmp])
//begin:开始的地址 end:结束的地址
//cmp:比较的方式，如果不写的话默认调用<
比较函数：传入两个数组中元素类型的参数，返回第一个参数排在前面的条件。
若不写比较函数cmp，默认为升序排序。
真题举例
1.下面关于排序稳定性的描述，正确的是（ ）。
A. 稳定性指算法的时间复杂度恒定
B. 稳定排序保证相同元素的相对顺序不变
C. 选择排序是稳定排序
D. 插入排序不是稳定排序
2.对数组 arr[]={5, 3, 8, 1} 进行升序排序，执行第一轮冒泡排序后数组 arr 中的内容为（ ）。
A. 3, 5, 1, 8 B. 3, 1, 5, 8
C. 3, 5, 8, 1 D. 5, 3, 8, 1
3.下面关于排序算法（冒泡排序、插入排序和选择排序）的描述中，不正确的是（ ）。
A. 冒泡排序基于元素交换实现，需借助临时变量，共涉及 个单元操作；而插入排序基于元素赋值实现，仅需 1个单元操作。因此冒泡排序的计算开销通常比插入排序更高。 B. 选择排序在任何情况下的时间复杂度都为 。 C. 冒泡排序在任何情况下的时间复杂度都为 。 D. 如果给定数据部分有序，插入排序通常比选择排序效率更高。
4.插入排序的时间复杂度总是比冒泡排序低。
正确 错误
六.文件操作
freopen,文件重定向，读操作、写操作、读写操作（C）
- 在默认情况下，cin只能接收从键盘输入的数据，cout也只能将数据输出到屏幕上。但通过重定向，cin可以将指定文件作为输入源，即接收文件中早已准备好的数据，同样cout可以将原本要输出到屏幕上的数据转而写到指定文件中。
- freopen实现,freopen()定义在
头文件中，是C语言标准库中的函数，专门用于重定向输入流（scanf()、gets()等）和输出流(printf()、puts()等)，该函数也可以对C++中的cin和cout进行重定向。
#include<bits/stdc++.h>
using namespace std;
int main() {
//定义输入文件 r:只读 stdin:标准输入
freopen("输入文件名","r",stdin);
//定义输出文件 w:可写 stdout:标准输出
freopen("输出文件名","w",stdout);
//代码
//关闭输入输出文件
fclose(stdin);
fclose(stdout);
return 0;
}
fstream 方式（C++）
ifstream:专用于文件读取操作
ofstream:专用于文件写入操作
fstream:支持读写操作
#include<bits/stdc++.h>
using namespace std;
int main() {
ofstream outfile("data.txt");//创建并打卡输出文件
outfile<<"Hello GESP"<<endl;//写入数据
outfile.close(); //关闭文件
ifstream fin("data.txt");//打开输入文件
string s;
getline(fin,s);
fin.close();
cout<<s<<endl;
return 0;
}
rdbuf() 获取或设置流的缓冲区
获取缓冲：无参调用时返回当前流关联的 streambuf* 指针，允许直接操作底层数据缓冲区
设置缓冲：传入 streambuf* 参数可将流的输出目标重定向至文件、内存或其他设备
#include<bits/stdc++.h>
using namespace std;
int main() {
//一个文件的内容输出到显示器上
ifstream infile("log.txt");
cout<<infile.rdbuf();
// 获取当前缓冲区指针
streambuf* original_buf = cout.rdbuf();
ofstream log_file("log.txt");
// 设置新缓冲区（如文件流）
cout.rdbuf(log_file.rdbuf()); // 重定向 cout 到文件
cout<<"hello gesp";
cout.rdbuf(original_buf); // 恢复原始的标准输出缓冲区
return 0;
}
真题举例
1.小杨用文件重定向实现在 log.txt 文件中输出日志，则下面横线上应填写（ ）。
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main() {
ofstream log_file("log.txt");
streambuf* original_cout = cout.rdbuf();
cout.rdbuf(log_file.rdbuf());
___________________________________ // 在此处填入代码
cout.rdbuf(original_cout); // 恢复原始的标准输出缓冲区
return 0;
}
A. cout << "This output will go to the log file." << endl;
B. log_file << "This output will go to the log file." << endl;
C. cout >> "This output will go to the log file." >> endl;
D. log_file >> "This output will go to the log file." >> endl;
七.异常处理
异常是程序在执行期间产生的问题。指在程序运行时发生的特殊情况，比如尝试除以零的操作。
异常提供了一种转移程序控制权的方式。C++异常处理涉及到三个关键字：try、catch、throw
- throw：当问题出现时，程序会抛出一个异常。这时通过使用throw关键字来完成的。
- catch：在你想要处理问题的地方，通过异常处理程序捕获异常。catch关键字用于捕获异常。
- try：try块中的代码标识将被激活的特定异常。它后面通常跟着一个或多个catch块。
#include<bits/stdc++.h>
using namespace std;
double df(int a,int b){
if(b==0){
throw "不能被0除";
}
return 1.0*a/b;
}
int main() {
int x=50,y=0,z;
try{
//保护代码
z=df(x,y);
cout<<z<<endl;
}catch(const char* msg){//捕获异常
cout<<msg<<endl;
}
return 0;
}
真题举例
八.算法复杂度的估算
算法复杂度的估算主要通过时间复杂度和空间复杂度来衡量，它们分别表示算法执行时间和所需存储空间随输入规模增长的变化趋势。
时间复杂度估算
时间复杂度用大O符号表示，描述算法执行时间与输入规模（）的关系。
估算方法
统计算法中基本操作（如循环、条件判断）的执行次数。
例如，双层嵌套循环通常为，单层循环为
它们都是估计值，不需要精确计算，常数项和低增长项都可以忽略，仅需保留最高增长项。比方说 等同于 等同于 。
常见类型：（常数）、（对数）、（线性）、（平方）。
冒泡排序：时间复杂度（双层循环），空间复杂度（原地交换）
空间复杂度估算
- 衡量算法运行时额外占用的内存空间，同样用大O表示。原地操作的算法空间复杂度为
复杂度估算的基本原则
- 关注高阶项：在多项式表达式中，仅保留最高阶项并忽略系数。例如， 的复杂度为 。
- 最坏情况分析：以算法在所有可能输入中最长的执行时间作为评估基准（如排序算法中对逆序数组的操作）。
- 常数操作：忽略与输入数据规模无关的固定操作（如赋值、简单运算）
总结：时间复杂度用来衡量一个算法的执行效率，空间复杂度用来衡量算法的内存消耗，它们都是越小越好。
比方说时间复杂度 $O(n)$的算法比 $O(n2)$ 的算法执行效率高，空间复杂度 $O(1)$ 的算法比 $O(n)$的算法内存消耗小。 $n$ 代表输入的数组的长度。
举例分析
数学中经典的“鸡兔同笼”问题，已知头共x个，脚共y只，问笼中的鸡和兔各有多少只?
示例一，时间复杂度 ，空间复杂度 ：
//假设法：假设都是鸡，算出兔子的数量 tu=(y-x*2)/2
int main(){
int x,y,ji,tu;
cin>>x>>y;
tu=(y-x*2)/2;
ji=x-tu;
cout<<ji<<" "<<tu;
return 0;
}
示例二，时间复杂度 ，空间复杂度 ：
//枚举法：一层循环：鸡的数量
int main(){
int x,y;
cin>>x>>y;
for(int ji=1;ji<=x;ji++){
int tu=x-ji;
if(ji+tu==x&&ji*2+tu*4==y){
cout<<ji<<" "<<tu;
return 0;
}
}
return 0;
}
示例三，时间复杂度 ，空间复杂度 ：
//枚举法：外层循环：鸡的数量 内层循环：兔子的数量
int main(){
int x,y;
cin>>x>>y;
for(int ji=1;ji<=x;ji++){
for(int tu=1;tu<=x;tu++){
if(ji+tu==x&&ji*2+tu*4==y){
cout<<ji<<" "<<tu;
return 0;
}
}
}
return 0;
}
真题举例
编程题单
二维数组、结构体、排序、递推
| 类型 | 题目编号 | 方法 |
|---|---|---|