CSP考点

admin

一、基础数据结构及操作
1. 线性结构
数组 / 向量（vector）
核心操作：遍历（for 循环）、元素访问（下标 /at ()）、插入（push_back ()）、删除（pop_back ()）、扩容 / 缩容、多维数组（矩阵）的行 / 列遍历。
应用场景：存储序列数据（如统计数字出现次数、前缀和数组）。
栈（stack）
核心操作：入栈（push ()）、出栈（pop ()）、取栈顶（top ()）、判空（empty ()）。
应用场景：括号匹配、表达式求值、单调栈（如求最大矩形面积）。
队列（queue）
核心操作：入队（push ()）、出队（pop ()）、取队头（front ()）、判空（empty ()）。
应用场景：BFS 遍历、滑动窗口、模拟排队问题。
链表（单链表 / 双链表）
核心操作：节点创建（new）、插入（前插 / 后插）、删除（释放节点）、遍历（指针移动）。
应用场景：模拟链表反转、环检测（阅读程序题常考指针操作逻辑）。
2. 非线性结构
二叉树（尤其是二叉搜索树 BST）
核心操作：递归遍历（前序 / 中序 / 后序）、迭代遍历（栈辅助）、查找（根据 BST 性质：左小右大）、插入、删除。
应用场景：通过遍历序列还原树结构、判断 BST 合法性（阅读程序题高频）。
堆（优先队列，priority_queue）
核心操作：插入（push ()）、取最值（top ()）、删除最值（pop ()）。
应用场景：TopK 问题（如取前 k 大元素）、堆排序、合并有序序列。
哈希表（unordered_map/unordered_set）
核心操作：插入（insert ()）、查找（count ()/find ()）、删除（erase ()）、键值对访问（[]）。
应用场景：统计元素出现次数、两数之和（快速查找互补元素）。
二、常用算法及核心逻辑
1. 排序与查找
排序算法
基础排序：冒泡排序（相邻交换）、选择排序（选最值交换）、插入排序（逐个插入有序区）。
高级排序：快速排序（分治 + 基准划分）、归并排序（分治 + 合并有序子列）、堆排序（堆维护）。
核心函数：sort()（C++ STL，默认升序，需理解自定义比较器）。
查找算法
二分查找：在有序数组中查找目标值（需注意边界条件：left <= right 还是 left < right）。
线性查找：遍历数组逐个匹配（适用于无序数据）。
2. 递归与分治
递归基础：阶乘计算、斐波那契数列（含优化：记忆化递归）、汉诺塔问题。
分治思想：归并排序（分拆 + 合并）、快速排序（基准划分）、大整数乘法（拆分计算）。
核心逻辑：递归终止条件（base case）、子问题拆分、结果合并。
3. 动态规划（DP）
经典问题：
一维 DP：最长递增子序列（LIS）、爬楼梯（斐波那契变种）。
二维 DP：最长公共子序列（LCS）、0-1 背包（状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])）、矩阵路径（求从左上角到右下角的路径和）。
核心逻辑：状态定义、转移方程、初始化（边界条件）。
4. 贪心算法
典型场景：区间调度（选最多不重叠区间）、 Huffman 编码（构建最优前缀码）、找零问题（优先用大面额硬币）。
核心逻辑：局部最优决策（需证明其能导出全局最优）。
5. 图论基础
遍历算法：
DFS（深度优先搜索）：递归或栈实现，用于连通性判断、路径查找（如迷宫求解）。
BFS（广度优先搜索）：队列实现，用于最短路径（无权图）、层次遍历。
最短路：Dijkstra 算法（单源最短路，适用于非负权图，优先队列实现）。
6. 字符串处理
核心操作：
字符串遍历（按字符访问）、拼接（+ 或 append()）、子串提取（substr(pos, len)）。
字符统计（用数组 / 哈希表记录每个字符出现次数）。
字符串匹配：KMP 算法（部分匹配表 / 前缀函数的构建与应用）。
三、数学相关算法
数论基础：
素数判断（试除法：检查 2 到√n 的约数）。
最大公约数（gcd，辗转相除法：gcd(a,b) = gcd(b,a%b)）、最小公倍数（lcm，lcm(a,b) = a*b/gcd(a,b)）。
快速幂（模运算优化：a^b % mod，分治思想减少乘法次数）。
前缀和与差分：
前缀和：快速计算区间和（sum[l..r] = pre[r] - pre[l-1]）。
差分：快速实现区间增减（diff[l] += x, diff[r+1] -= x，再求前缀和还原数组）。
四、C++ STL 高频函数
输入输出：cin/cout、scanf/printf（注意格式控制，如%d、%s）。
算法库（algorithm）：sort()（排序）、swap()（交换）、max/min（取最值）、reverse()（反转序列）、lower_bound/upper_bound（二分查找）。
容器：vector（动态数组）、string（字符串）、stack（栈）、queue（队列）、priority_queue（堆）、map/set（有序映射 / 集合）。

admin

（1）入门级：CCF 非专业级软件能力认证入门组（Certified Software Professional Junior，简称 CSP-J）；
（2）提高级：全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，NOIP）、CCF 非专业级软件能力认证提高组（Certified Software Professional Senior，简称 CSP-S）；
（3）NOI 级：全国青少年信息学奥林匹克竞赛（NOI）及以上，包括国际信息学奥林匹克（International Olympiad in Informatics，IOI）中国队选拔（CTS）、NOI 冬令营、国家集训队集训等。

【1】：难度系数（范围为 1~10）。考虑到相邻级别中知识点的难度系数范围可能互有交叉，入门级知识点难度系数范围取 1~5，（除入门级知识点外的）提高级知识点难度系数范围取 5~8，（除入门级、提高级知识点外的）NOI级知识点难度系数范围取 7~10。

CSP-J信息学奥赛考试大纲（入门级）
1．计算机基础与编程环境
1．1 【1】计算机的基本构成（CPU、内存、I/O设备等）
1．2 【1】Windows、Linux等操作系统的基本概念及其常见操作
1．3 【1】计算机网络和Internet的基本概念
1．4 【1】计算机的历史和常见用途
1．5 【1】NOI以及相关活动的历史
1．6 【1】NOI以及相关活动的规则
1．7 【1】进制的基本概念与进制转换、字节与字
1．8 【1】程序设计语言以及程序编译和运行的基本概念
1．9 【1】使用图形界面新建、复制、删除、移动文件或目录
1．10 【1】使用Windows系统下的集成开发环境（例如Dev C++等）
1．11 【1】使用Linux系统下的集成开发环境（例如Code:：Blocks等）
1．12 【1】g++、gcc等常见编译器的基本使用

2． C++程序设计
2．1 程序基本概念
1．【1】标识符、关键字、常量、变量、字符申、表达式的概念
2．【1】常量与变量的命名、定义及作用
3．【2】头文件与名字空间的定义与理解
4．【2】编辑、编译、解释、调试等概念理解

2．2 基本数据类型
1．【1】整数型：int，long long
2．【1】实数型：float，double
3．【1】字符型：char
4．【1】布尔型：bool

2．3 程序基本语句
1．【2】cin语句，scanf语句，cout语句，printf语句，赋值语句，复合语句
2．【2】if语句，switch语句，多层条件语句
3．【2】for 语句，while 语句，do while 语句
4．【2】多层循环语句

2．4 基本运算
1．【1】算术运算：加、减、乘、除、整除、求余
2．【1】关系运算：大于，大于等于，小于，小于等于，等于，不等于
3．【1】逻辑运算：与（&&）、或（||）、非（！）
4．【1】变量自增与自减运算
5．【1】三目运算
6．【2】位运算：与（&）、或（|）、非（~）异或（^）、左移、右移

2．5 数学库常用函数
1．【3】绝对值函数，四舍五入函数，取上整函数，取下整函数，常用三角函数，对数函数，指数函数，平方根函数

2．6 结构化程序设计
1．【1】顺序结构、分支结构和循环结构
2．【2】自顶向下、逐步求精的模块化程序设计
3．【2】流程图的概念及流程图描述

2．7 数组
1．【1】数组定义，数组与数组下标的含义
2．【1】数组的读入与输出
3．【2】纯一维数组的综合运用
4．【3】纯二维数组与多维数组的综合应用

2．8 字符串的处理
1．【2】字符数组与字符串的关系
2．【2】字符数组的综合应用
3．【2】string类定义、相关函数引用
4．【2】string类的综合应用

2．9 函数与递归
1．【2】函数定义与调用，形参与实参
2．【3】传值参数与传引用参数•
3．【2】常量与变量的作用范围
4．【2】递归函数的概念、定义与调用

2．10 结构体与联合体
1．【3】结构体的定义及应用
2．【3】联合体的定义及应用

2．11 指针类型
1．【4】指针的概念及调用
2．【4】指针与数组
3．【4】字符指针与string类
4．【4】指向结构体的指针

2．12 文件及基本读写
1．【2】文件的基本概念，文本文件的基本操作
2．【2】文本文件类型与二进制文件类型
3．【2】文件重定向、文件读写等操作

2．13 STL模板应用
1．【3】 中sort函数
2．【4】栈（stack）、队列（queue）、链表（list）、向量（vector）等容器

3．数据结构
3．1 线性表
1．【3】链表：单链表、双向链表、循环链表
2．【3】栈
3．【3】队列

3．2 简单树
1．【3】树的定义及其相关概念
2．【4】树的父亲表示法
3．【3】二叉树的定义及其基本性质
4．【4】二叉树的孩子表示法
5．【4】二叉树的遍历：前序、中序、后序遍历

3．3 特殊树
1．【4】完全二叉树的定义与基本性质
2．【4】完全二叉树的数组表示法
3．【4】哈夫曼树的定义、构造及其遍历
4．【4】二叉排序树的定义、构造及其遍历

3．4 简单图
1．【3】图的定义及其相关概念
2．【4】图的邻接矩阵存储
3．【4】图的邻接表存储

４．算法
4．1 算法概念与描述
•1．【1】算法概念
•2．【2】算法描述：自然语言描述、流程图描述、伪代码描述

4．2 人门算法
1．【1】枚举法
2．【1】模拟法

4．3 基础算法
1．【3】贪心法
2．【3】递推法
3．【4】递归法
4．【4】二分法•
5．【4】倍增法

4．4 数值处理算法
1．【4】高精度的加法•
2．【4】高精度的减法•
3．【4】高精度的乘法
4．【4】求高精度整数除以单精度整数的商和余数

4．5 排序算法
1．【3】排序的基本概念（稳定性等）
2．【3】冒泡排序
3．【3】简单选择排序
4．【3】简单插入排序

4．6 搜索算法
1．【5】深度优先算法
2．【5】广度优先算法

4．7 图论算法
1．【4】图的深度优先遍历算法
2．【4】图的宽度优先遍历算法
3．【5】洪水填充算法（floodfill）

4．8 动态规划
1．【4】动态规划的基本思路
2．【4】简单一维动态规划
3．【5】简单背包类型动态规划
4．【5】简单区间类型动态规划

5．数学与其他
5．1 数及其运算
1．【1】数的概念，算术运算（加、减、乘、除、求余）
2．【1】数的进制：二进制、八进制、十六进制和十进制及其转换
3．【1】编码：ASCI码，哈夫曼编码，格雷码

5．2 初等数学
1．【1】初中代数
2．【1】初中平面几何

5．3 初等数论
1．【3】整除、因数、倍数、指数、质数、合数、同余等概念
2．【3】取整
3．【3】模运算与同余
4．【3】整数唯一分解定理
5．【3】辗转相除法（欧几里德算法）
6．【4】素数筛法：埃氏筛法和线性筛法

5．4 离散与组合数学
1．【2】集合
2．【2】加法原理
3．【2】乘法原理
4．【4】排列及计算公式
5．【4】组合及计算公式
6．【4】杨辉三角公式

5．5 其他
1．【2】ASCII码
2．【2】格雷码