四级考纲

• 指针
• 函数与结构体
• 二维及多维数组
• 递推算法
• 排序算法
• 文件操作
• 异常处理
• 简单算法复杂度的估算

知识点解析

一.指针

主要内容：指针类型，指针类型定义变量，指针类型变量赋值、解引用

• 指针类型

  指针，用来描述内存地址，并通过指针操作来实现与内存相关的程序功能。

  数据类型* ——表示指向该数据类型变量的指针

• 指针类型定义变量

  数据类型 变量名; // 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;
  

  注意：解引用一定要保证，指针所指向的内存空间是可以访问的。

• 数组名指针，它存放了第一个元素的地址(首地址)

真题举例

1.执行下述代码后，变量 a 的值为（ ）。
int a = 10;
int* p = &a;
*p = 20;
A. 10  B. 20  C. 随机值  D. 编译错误

二. 函数与结构体

函数的定义、调用、声明

• 函数的定义

  返回类型  函数名(形参){
         函数体
         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函数 |

  变量按其在程序中作用的范围，分为全局变量和局部变量。全局变量是指在程序代码开始执行前初始化并分配存储空间的变量，它在程序的整个运行过程中都起作用，在静态数据区存储，在整个程序执行结束后释放存储空间。

  局部变量是指在程序函数内部定义的变量，它只在函数内部起作用，在动态数据区存储，在函数调用时动态初始化，函数调用完毕后释放存储空间。函数的形参是局部变量。同一个函数同一个形参在两次不同调用过程中其存储空间往往是不相同的。

值传递、地址传递、引用传递

• 值传递：将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. 编译错误

三. 二维及多维数组

二维及多维数组的定义

• 二维数组的定义：类型标识符 数组名[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

四.递推算法

基本思想

从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。

递推则是由“边界”往“结果”一步步求解。

真题举例

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

稳定性：相等的元素经过排序之后相对顺序是否发生了改变

• 稳定：如果排序前a在b的前面，且a==b,排序之后a仍然在b前面，称该算法稳定
• 不稳定：如果排序前a在b前面，且a==b,排序之后a可能在b后面,称该算法不稳定

计数排序：是一种特殊的桶排序。桶的个数是可能出现的数据种类数。

计数数组：数组下标是桶的编号，通常为数据值，数组的值表示数据个数。

适用条件：待排序数据为整数，数据范围有限。

sort排序

sort(begin,end,[cmp])
//begin:开始的地址  end:结束的地址
//cmp:比较的方式，如果不写的话默认调用<

比较函数：传入两个数组中元素类型的参数，返回第一个参数排在前面的条件。

若不写比较函数cmp，默认为升序排序。

真题举例

六.文件操作

文件重定向，读操作、写操作、读写操作

• 在默认情况下，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; 
}

真题举例

七.异常处理

异常是程序在执行期间产生的问题。指在程序运行时发生的特殊情况，比如尝试除以零的操作。

异常提供了一种转移程序控制权的方式。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符号表示，描述算法执行时间与输入规模（$n$）的关系。

• 估算方法

  • 统计算法中基本操作（如循环、条件判断）的执行次数。

  • 例如，双层嵌套循环通常为$O(n^2)$，单层循环为$O(n)$

• 它们都是估计值，不需要精确计算，常数项和低增长项都可以忽略，仅需保留最高增长项。比方说 $O(2n^2+3n+1)$等同于 $O(n^2),O(1000n+1000)$等同于 $O(n)$。

• 常见类型：$O(1)$（常数）、$O(log n)$（对数）、$O(n)$（线性）、$O(n^2)$（平方）。

• 冒泡排序：时间复杂度$O(n^2)$（双层循环），空间复杂度$O(1)$（原地交换）

空间复杂度估算

• 衡量算法运行时额外占用的内存空间，同样用大O表示。原地操作的算法空间复杂度为$O(1)$

复杂度估算的基本原则

1. ‌关注高阶项‌：在多项式表达式中，仅保留最高阶项并忽略系数。例如，$3n^2+2^n+1$ 的复杂度为 $O(n^2)$。
2. ‌最坏情况分析‌：以算法在所有可能输入中最长的执行时间作为评估基准（如排序算法中对逆序数组的操作）。
3. ‌常数操作‌：忽略与输入数据规模无关的固定操作（如赋值、简单运算）

总结：时间复杂度用来衡量一个算法的执行效率，空间复杂度用来衡量算法的内存消耗，它们都是越小越好。

比方说时间复杂度 $O(n)$的算法比 $O(n2)$ 的算法执行效率高，空间复杂度 $O(1)$ 的算法比 $O(n)$的算法内存消耗小。 $n$ 代表输入的数组的长度。

举例分析

数学中经典的“鸡兔同笼”问题，已知头共x个，脚共y只，问笼中的鸡和兔各有多少只?

示例一，时间复杂度 $O(1)$，空间复杂度 $O(1)$：

//假设法：假设都是鸡，算出兔子的数量 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;
}

示例二，时间复杂度 $O(n)$，空间复杂度 $O(1)$：

//枚举法：一层循环：鸡的数量
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;
}

示例三，时间复杂度 $O(n^2)$，空间复杂度 $O(1)$：

//枚举法：外层循环：鸡的数量  内层循环：兔子的数量 
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;
}

真题举例

编程题单