2025暑假CSP笔试笔记

计算机基础知识

程序基本常识

算法的特性

程序设计基础知识 - 图1

算法的复杂度

时间复杂度

程序设计基础知识 - 图2

  • 增长越快，复杂度越高
  • 增长越慢，复杂度越底
    空间复杂度

    C++语言基础

    数据类型

    程序设计基础知识 - 图3

    递归示例

    例如编写一求1+2+..+n的值，其中n<=20

  1. #include <iostream>
  2. using namespace std;
  3. int add(int n){
  4.     if(n==1) {
  5.         return 1;
  6.     }
  7.     return add(n-1) + n;
  8.     1 + 2 + 3  
  9. }
  10. int main(){
  11.     cout <<  add(4);
  12.     return 0;
  13. }

排序

常见算法复杂度与稳定性

程序设计基础知识 - 图4

冒泡排序

  • 小的元素会经由交换慢慢“浮”到顶端，就像泡泡一样，故名“冒泡排序”。

  • 它的工作原理是，重复地走访过要排序的元素，依次比较两个相邻的两个元素，如果前面的数比后面的数大就把他们交换过来。

  • 走访元素的工作重复地进行，直到没有相邻元素需要交换

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. const int SIZE = 10;
    4. int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
    5. int main(){
    6.   for(int i = 0 ; i < SIZE - 1; i++){
    7.       for(int j = 0 ; j < SIZE-1 -i; j++){
    8.           if(arr[j] > arr[j+1])
    9.               swap(arr[j],arr[j+1]);
    10.       }
    11.   }
    12.   for(int x : arr) cout << x << " ";
    13.   return 0;
    14. }

    选择排序

  • 从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置

  • 然后再从剩余的未排序元素中寻找到最小元素，然后放到已排序的序列的后面。

  • 以此类推，直到全部待排序的数据元素的个数为零。

    1. #include<bits/stdc++.h>
    2. using namespace std;
    3. const int SIZE = 10;
    4. int arr[SIZE] = {2,7,8,4,36,78,1,91,42,13};
    5. int main(){
    6.   for(int i=0;i<SIZE - 1;i++){
    7.       for(int j=i+1;j<SIZE;j++){
    8.           if(arr[i]>arr[j]) swap(arr[i],arr[j]);
    9.       }
    10.   }
    11.   for(int x : arr) cout << x << " ";
    12.   return 0;
    13. }

    字符数组与字符串

    字符串

    字符串实际上是用null，字符即’\0’终止的一维字符数组。

    string类的函数 （ strlen(s) ）

    程序设计基础知识 - 图5

    字符串的方法 （ s.() ）

    程序设计基础知识 - 图6

    链表

    数据结构+算法

    数据结构

    存储、组织数据的方式

    数组 array

    顺序存储出，需要用到连续的内存空间

    链表 linked list

    随机存储，有效利用零散的碎片空间

  • 无论数组还是来链表，都是数据结构中的物理结构
  • 数据结构中还有逻辑结构
  • 逻辑结构更抽象，且依附于物理结构

栈

先进后出

应用

  • 网页回溯，撤销操作
  • 栈底 bottom 栈顶 top
  • 数据的出栈和入栈都在栈顶。

    队列 queue

    先进先出

    应用

  • 排队
  • 队头 front 队尾 rear/back
  • 我们插入数据在队尾，数据出列在码头

    树

    一、树的基本概念

    1.1 树的定义
    树是一种非线性的数据结构，由n(n≥0)个有限节点组成一个具有层次关系的集合。
    1.2 树的示意图
    1.       A        ← 根节点
    2.      / \
    3.     B   C      ← A的子节点
    4.    / \   \
    5.   D   E   F    ← 叶节点
    1.3 树的组成部分
  • 根节点(Root): 树的最顶层节点(如A)
  • 父节点/子节点: B是A的子节点，A是B的父节点
  • 叶节点(Leaf): 没有子节点的节点(如D,E,F)
  • 边(Edge): 连接两个节点的线
  • 深度: 从根到该节点的边数(A深度为0，B为1，D为2)
  • 高度: 从该节点到最深叶节点的边数

    二、树的常见类型

    2.1 二叉树
    每个节点最多有两个子节点(左子节点和右子节点)
    1.      A
    2.     / \
    3.    B   C
    4.   / \   \
    5.  D   E   F
    2.2 满二叉树
    每个节点都有0或2个子节点，且所有叶节点在同一层
    1.      A
    2.     / \
    3.    B   C
    4.   / \ / \
    5.  D  E F  G
    2.3 完全二叉树
    除最后一层外，其他层都填满，且最后一层节点靠左排列
    1.      A
    2.     / \
    3.    B   C
    4.   / \ /
    5.  D  E F

    三、树的应用场景

    1.文件系统: 文件夹和文件的层级结构 2.组织结构图: 公司部门层级关系 3.家谱图: 家族成员关系 4.HTML DOM树: 网页元素嵌套关系 5.决策树: 机器学习中的分类模型

    四、树的基本操作示意图

    4.1 遍历方式
  • 前序遍历: 根→左→右
  • 中序遍历: 左→根→右
  • 后序遍历: 左→右→根
    4.2 查找操作
    1. 查找E节点路径: A → B → E
    4.3 插入操作
    1. 在C节点下插入G:
    2.      A
    3.     / \
    4.    B   C
    5.   / \   \
    6.  D   E   G
    二叉树公式
    程序设计基础知识 - 图7
    一棵节点已知的二叉树，求至多有多少个节点有2个子节点公式：
    2 * n2 + 1 + n1 = 10

n2：度数为2的节点，n1度数为1的节点，n0度数为0的节点

逻辑结构

程序设计基础知识 - 图8

树的几要素：

程序设计基础知识 - 图9

二叉树
满二叉树

程序设计基础知识 - 图10

完全二叉树

程序设计基础知识 - 图11

满二叉树与完全二叉树的关系：

程序设计基础知识 - 图12 程序设计基础知识 - 图13 程序设计基础知识 - 图14

使用总边数一致推导：

N0 = N2 + 1 程序设计基础知识 - 图15

图

一、图的基本概念

1.图的定义：由顶点(点)和边组成的结构

2.图的分类：
无向图

边没有方向

有向图

边有方向

二、顶点与边的关系

1. 基本关系
  • 邻接关系：两个顶点之间有边直接相连
  • 关联关系：边与顶点之间的关系
    2. 数学表示
    无向图：
  • 边记为 (u,v)
  • 顶点度数 = 关联边数
    有向图
  • 边记为
  • 出度/入度概念

    三、特殊路径概念

    1. 欧拉路径
  • 经过图中每一条边且每边只经过一次的路径
    条件：
  • 无向图：恰好两个顶点度数为奇数
  • 有向图：一个顶点入度=出度+1，另一个出度=入度+1，其余相等
    2. 欧拉回路
  • 起点和终点相同的欧拉路径
    条件：
  • 无向图：所有顶点度数为偶数
  • 有向图：所有顶点入度=出度

    前辍与后辍表达式

    1. 表达式表示法

  • 中辍表达式：运算符位于操作数中间 (如 a + b)
  • 前辍表达式：运算符位于操作数前面 (如 + a b)
  • 后辍表达式：运算符位于操作数后面 (如 a b +)

    2. 表达式特性对比

    中辍表达式特性：
  • 人类最易读的形式
  • 需要括号来明确优先级
  • 运算符优先级规则复杂
  • 计算顺序不明确
    前辍表达式特性：
  • 无需括号即可明确运算顺序
  • 计算顺序从右向左
  • 运算符优先级隐含在结构中
  • 适合递归计算
  • 计算机处理效率高
    后辍表达式特性：
  • 无需括号即可明确运算顺序
  • 计算顺序从左向右
  • 适合使用栈结构计算
  • 运算符优先级隐含在结构中
  • 计算机处理效率最高

    三、除法运算详解

    1. 中辍表达式中的除法

  • 明确运算顺序：a / b 表示 a 除以 b
  • 带括号的情况：(a + b) / (c - d)
  • 除法的优先级高于加减法

    2. 后辍表达式中的除法处理

    计算规则：
  1. 从左到右扫描表达式
  2. 操作数压入栈
  3. 遇到运算符时：
    • 弹出栈顶两个元素
    • 第一个弹出的是右操作数
    • 第二个弹出的是左操作数

      示例：

      a b /
  4. 压入 a
  5. 压入 b
  6. 遇到 /：
    • 弹出 b (右)
    • 弹出 a (左)
    • 计算 a / b

      3. 前辍表达式中的除法处理

      计算规则：

  7. 从右到左扫描表达式
  8. 操作数压入栈
  9. 遇到运算符时：
    • 弹出栈顶两个元素
    • 第一个弹出的是左操作数
    • 第二个弹出的是右操作数

      示例：/ a b

  10. 从右到左扫描：
    • 压入 b
    • 压入 a
  11. 遇到 /：
    • 弹出 a (左)
    • 弹出 b (右)
    • 计算 a / b

      四、记忆技巧

      后辍表达式：

  • 运算符”站在”操作数后面
  • 计算顺序：”后进先出，先右后左”
  • 口诀：”先出来的是右边的”

    前辍表达式：

  • 运算符”站在”操作数前面
  • 计算顺序：”先进后出，先左后右”
  • 口诀：”先出来的是左边的”

    五、综合示例

    中辍表达式：(6 + 3) / (4 - 1)

    1. 转换为后辍表达式：
  • 步骤：6 3 + 4 1 - /
  • 计算过程：
    1. 6, 3 → 遇到 + → 6 + 3 = 9
    2. 4, 1 → 遇到 - → 4 - 1 = 3
    3. 9, 3 → 遇到 / → 9 / 3 = 3
      2. 转换为前辍表达式：
  • 步骤：/ + 6 3 - 4 1
  • 计算过程：
    1. 从右到左：
      • 1, 4 → 遇到 - → 4 - 1 = 3
      • 3, 6 → 遇到 + → 6 + 3 = 9
    2. 9, 3 → 遇到 / → 9 / 3 = 3

      六、课堂练习

  1. 将 (8 / 4) + (2 * 3) 转换为：
    • 前辍表达式
    • 后辍表达式
    • 并说明除法运算的处理过程
  2. 计算后辍表达式 5 1 2 + 4 * + 3 - 的值