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