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