admin 的博客
全国青少年信息学奥林匹克系列竞赛大纲 (2025年修订版)
admin LV 9 SU @ 2025-10-16 11:23:14

全国青少年信息学奥林匹克系列竞赛大纲 (2025年修订版)

一、简介

1.1 目的

本大纲的制定目的在于:

为全国青少年信息学奥林匹克 (National Olympiad in Informatics, NOI) 系列竞赛以及中国计算机学会 (China Computer Federation, CCF) 主办的其他有关活动的题目命制提供依据;
为NOI指导教师的教学提供方向和指导;
为参加NOI系列竞赛、CCF主办的其他有关活动的学生和信息学爱好者的学习提供范围;
为各省市开展和组织NOI省选等活动提供参照。

1.2 原则

1.2.1 等级化原则

按照目前NOI系列活动开展的现状，以及将来可能的发展，大纲将各知识点分成入门级、提高级和NOI级。高级别自动包含低级别知识点。各级别与NOI系列活动以及CCF主办的其他活动的对应关系如下:

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

除将所有知识点划分为上述级别以外，还对每个知识点标定了学习难度系数 (范围为1 ~ 10)。考虑到相邻级别知识点的学习难度可能存在交错，因此将入门级知识点的难度系数范围设置为1 ~ 5，(除入门级知识点外的) 提高级知识点的难度系数范围设置为5 ~ 8，(除入门级、提高级知识点外的) NOI级知识点的难度系数范围设置为7 ~ 10。

各知识点难度系数以X的格式列在知识点之前。

1.2.2 差异化原则

为促进信息学和NOI活动的普及，大纲应较详尽地规定中低级别知识点的范围，以尽可能清晰地划定相应级别的知识范围，有效地指导入门学生的学习及相关的教学活动;为保证和促进我国选手在IOI竞赛中的竞争力，大纲应避免过于严格地限制命题的思路，须为NOI等高水平竞赛的题目命制留有充分的开放性，因此不宜过于细致地规定高级别知识点的范围。为此，大纲在制定中将采取“上粗下细”的指导思想: 知识级别越低，其内容规定得越细; 知识级别越高，其内容规定得越粗。

1.2.3 统一性原则

为保证大纲的简明性和系统性，高级别比赛的知识范围将自动地包含低级别比赛的所有知识点。同时，对每个级别按照竞赛环境 (Linux和Windows)、程序设计语言 (C++)、数据结构、算法以及数学等进行了分类。对每个大类又按照知识点的属性继续划分为若干小类; 某些知识点可能与多个类别均有紧密或松散联系，本大纲均按其主要属性划定其类别，以避免同一知识点在多个类别中的重复出现。

1.3 建议

建议在各级别竞赛题目的命制中，

各级别竞赛或活动的考察范围不超过对应的大纲级别，其中难度系数为10的知识点仅用于CTS; 避免对算法复杂度的常系数的考察;

部分单个知识点可能对应不同层次、不同性能的多个数据结构或算法。考察内容应以常见的、经典的内容为主，避免虽具有微弱性能优势 (例如算法复杂度的细微改进) 但较为冷僻或过新的数据结构和算法。

1.4 修订

大纲将根据NOI活动的发展而定期进行维护和修订，修订周期为两年;

本轮大纲维护小组成员为: 赵启阳 (召集人)、叶金毅、胡伟栋、金靖、李建、谢秋锋、汪星明、李曙、叶国平。欢迎将修订意见反馈给以上人员。

1.5 致谢

在本轮大纲的修订过程中，杨耀良、崔浩以及多位未具名的师生均提出了各种宝贵意见，在此表示感谢。

二、内容

2.1 入门级

2.1.1 基础知识与编程环境

计算机的基本构成 (CPU、内存、I/O设备等)
Windows、Linux等操作系统的基本概念及其常见操作
计算机网络和Internet的基本概念
计算机的历史和常见用途
NOI以及相关活动的历史
NOI以及相关活动的规则
位、字节与字
程序设计语言以及程序编译和运行的基本概念
使用图形界面新建、复制、删除、移动文件或目录
使用Windows系统下的集成开发环境 (例如Dev-C++等)
使用Linux系统下的集成开发环境 (例如Code::Blocks等)
常用编译命令g++的基本使用

2.1.2 C++程序设计

1. 程序基本概念

标识符、关键字、常量、变量、字符串、表达式的概念
常量与变量的命名、定义及作用
头文件与名字空间的概念
编辑、编译、解释、调试的概念

2. 基本数据类型

整数型: int、long long
实数型: float、double
字符型: char
布尔型: bool

3. 程序基本语句

cin语句、scanf语句、cout语句、printf语句、赋值语句、复合语句
if语句、switch语句、多层条件语句
for语句、while语句、do while语句
多层循环语句

4. 基本运算

算术运算: 加、减、乘、除、整除、求余
关系运算: 大于、大于等于、小于、小于等于、等于、不等于
逻辑运算: 与(&&)、或(||)、非(!)
变量自增与自减运算
三目运算
位运算: 与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)

5. 数学库常用函数

绝对值函数、四舍五入函数、下取整函数、上取整函数、平方根函数、常用三角函数、对数函数、指数函数

6. 结构化程序设计

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

7. 数组

数组与数组下标
数组的读入与输出
二维数组与多维数组

8. 字符串的处理

字符数组与相关函数
string类与相关函数

9. 函数与递归

函数定义与调用、形参与实参
传值参数与传引用参数
常量与变量的作用范围
递归函数

10. 结构体与联合体

结构体
联合体

11. 指针与引用

指针
基于指针的数组访问
字符指针
指向结构体的指针
引用

12. 文件及基本读写

文件的基本概念、文本文件的基本操作
文本文件类型与二进制文件类型
文件重定向、文件读写等操作

13. STL模板

常用函数与算法模板:min、max、swap、sort
栈(stack)、队列(queue)、链表(list)、向量(vector)等容器

2.1.3 数据结构

1. 线性结构

链表: 单链表、双向链表、循环链表
栈
队列

2. 简单树

树的定义与相关概念
树的表示与存储
二叉树的定义与基本性质
二叉树的表示与存储
二叉树的遍历: 前序、中序、后序

3. 特殊树

完全二叉树的定义与基本性质
完全二叉树的数组表示法
哈夫曼树的定义和构造、哈夫曼编码
二叉搜索树的定义和构造

4. 简单图

图的定义与相关概念
图的表示与存储: 邻接矩阵
图的表示与存储: 邻接表

2.1.4 算法

1. 算法概念与描述

算法概念
算法描述: 自然语言描述、流程图描述、伪代码描述

2. 入门算法

枚举法
模拟法

3. 基础算法

贪心法
递推法
递归法
二分法
倍增法

4. 算法策略

前缀和
差分

5. 数值处理算法

高精度的加法
高精度的减法
高精度的乘法
高精度整数除以单精度整数的商和余数

6. 排序算法

排序的基本概念
冒泡排序
选择排序
插入排序
计数排序

7. 搜索算法

深度优先搜索
广度优先搜索

8. 图论算法

深度优先遍历
广度优先遍历
泛洪算法 (Flood Fill)

9. 动态规划

动态规划的基本思路
简单一维动态规划
简单背包类型动态规划
简单区间类型动态规划

2.1.5 数学与其他

1. 数及其运算

自然数、整数、有理数、实数及其算术运算 (加、减、乘、除)
进制与进制转换: 二进制、八进制、十进制、十六进制

2. 初等数学

代数 (初中部分)
几何 (初中部分)

3. 初等数论

整除、因数、倍数、指数、质 (素) 数、合数
取整
模运算与取余
整数唯一分解定理
辗转相除法 (欧几里得算法)
素数筛法: 埃氏筛法与线性筛法

4. 离散与组合数学

集合
加法原理
乘法原理
排列
组合
杨辉三角

5. 其他

ASCII码

2.2 提高级

2.2.1 基础知识与编程环境

Linux系统终端中常用的文件与目录操作命令
Linux系统下常见文本编辑工具的使用
常用编译命令g++与相关编译选项
在Linux系统终端中运行程序, 使用time命令查看程序用时
调试工具GDB的使用

2.2.2 C++程序设计

1. 类 (class)

类的概念及简单应用
成员函数和运算符重载

2. STL模板

容器 (container) 和迭代器 (iterator)
对 (pair)、元组 (tuple)
集合 (set)、多重集合 (multiset)
树状数组
双端队列 (deque)、优先队列 (priority_queue)
线段树
字典树 (Trie)
映射 (map)、多重映射 (multimap)
笛卡尔树
位集合 (bitset)
平衡树: AVL、Treap、Splay等
算法模板库中的常用函数

4. 常见图

稀疏图

2.2.3 数据结构

1. 线性结构

欧拉图
双端栈
有向无环图
双端队列
连通图与强连通图
单调队列
双连通图
优先队列
ST表 (Sparse Table)
哈希表
数值哈希函数构造

2. 集合与森林

字符串哈希函数构造
并查集
哈希冲突的常用处理方法
树的孩子兄弟表示法

2.2.4 算法

1. 特殊树

二叉堆
时间复杂度分析
空间复杂度分析

2. 算法策略

离散化
扫描线

3. 基础算法

分治算法

4. 排序算法

归并排序
快速排序
堆排序
桶排序
基数排序

5. 字符串算法

字符串匹配: KMP算法
Manacher算法

6. 搜索算法

搜索的剪枝优化
记忆化搜索
启发式搜索
双向广度优先搜索
迭代加深搜索

7. 图论算法

最小生成树: Prim和Kruskal等算法
单源最短路: Bellman-Ford、Dijkstra、SPFA等算法
单源次短路
Floyd-Warshall算法
有向无环图的拓扑排序
欧拉道路和欧拉回路
二分图的判定
强连通分量
割点、割边
树的重心、直径、DFS序与欧拉序
树上差分、子树和与倍增
最近公共祖先

8. 动态规划

多维动态规划
树型动态规划
状态压缩动态规划
动态规划的常用优化

2.2.5 数学与其他

1. 初等数学

代数 (高中部分)
几何 (高中部分)

2. 初等数论

同余式
欧拉定理和欧拉函数
费马小定理
威尔逊定理
裴蜀定理
模运算意义下的逆元
扩展欧几里得算法
中国剩余定理

3. 离散与组合数学

多重集合
等价关系与等价类
多重集上的排列
多重集上的组合
错排列、圆排列
鸽巢原理
二项式定理
容斥原理
卡特兰 (Catalan) 数

4. 线性代数

向量与矩阵的概念
向量的运算
矩阵的初等变换
矩阵的运算: 加法、减法、乘法与转置
特殊矩阵的概念: 单位阵、三角阵、对称阵和稀疏矩阵
高斯消元法

2.3 NOI级

2.3.1 C++程序设计3

面向对象的程序设计思想 (OOP)

2.3.2 数据结构

1. 线性结构

块状链表

2. 复杂树

树链剖分
动态树:LCT
树套树
k-d树
虚树

3. 可合并堆

左偏树
二项堆

4. 可持久化数据结构

可持久化线段树
其他可持久化数据结构

2.3.3 算法

1. 算法策略

分块
离线处理思想
复杂分治思想
平衡规划思想
构造思想

2. 字符串算法

扩展KMP算法
有穷自动机的概念
AC自动机
后缀数组
后缀树
后缀自动机

3. 图论算法

基环树
最小树形图
2-SAT
网络流
图的支配集、独立集与覆盖集
匈牙利算法
KM算法
一般图的匹配

4. 动态规划

复杂动态规划模型的构建
复杂动态规划模型的优化

2.3.4 数学与其他

1. 初等数论

原根和指数
大步小步 (Baby Step Giant Step, BSGS) 算法
狄利克雷（Dirichlet）卷积
二次剩余
二次同余式

2. 离散与组合数学

群及其基本性质
置换群与循环群
母函数
莫比乌斯反演
Burnside 引理与 Pólya 定理
斯特林（Stirling）数
无根树的 Prüfer 序列

3. 线性代数

逆矩阵
行列式
向量空间与线性相关

4. 高等数学

多项式函数的微分
多项式函数的积分
泰勒（Taylor）级数
快速傅里叶变换

5. 概率论

概率的基本概念
随机变量的期望与方差
条件概率
贝叶斯公式

6. 博弈论

尼姆（Nim）博弈
SG 函数

7. 最优化

单纯形法

8. 计算几何

点、线、面之间位置关系的判定
一般图形面积的计算
二维凸包
半平面交

9. 信息论

熵、互信息、条件熵、相对熵

10. 其他

信息复杂度的概念
描述复杂度的概念
通讯复杂度的概念