全国青少年奥林匹克系列竞赛大纲(2021版)

2022年9月17日 | 分类: 【编程】

新闻:https://www.noi.cn/xw/2021-04-02/724387.shtml
下载:https://www.noi.cn/upload/resources/file/2021/04/06/152179.pdf

全国青少年奥林匹克系列竞赛大纲

一、简介

 

2021 年 4 月,全国青少年信息学奥林匹克竞赛大纲在 NOI 官网发布。为方便大家的查阅和收藏,把大纲的入门级、提高级和 NOI 级全部整理了出来。以下是NOI官网发布的大纲详情。

 

二、大纲

2.1 入门级

 

2.1.1 计算机基础与编程环境

 

1.【1】计算机的基本构成(CPU、内存、I/O 设 备等)

2.【1】Windows、 Linux 等操作系统的基本概念及其常见操作

3.【1】计算机网络和 Internet 的基本概念

4.【1】计算机的历史及其在现代社会中的常见应用

5.【1】 NOI 以及相关活动的历史

6.【1】进制的基本概念与进制转换、字节与字

7.【1】程序设计语言以及程序编译和运行的基本概念

8.【1】使用图形界面新建、复制、删除、移动文件或目录

9.【1】使用 Windows 系统下的集成开发环境(例如 Dev C++等)

10.【1】使用 Linux 系统下的集成开发环境(例如 Code::Blocks 等)

11.【1】g++、gcc 等常见编译器的基本使用

【X】表示难度系数

 

2.1.2 C++程序设计 1    

 

1.程序基本概念

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

2.基本数据类型

  • 【1】整数型:int, long long
  • 【1】实数型:float, double
  • 【1】字符型:char
  • 【1】布尔型:bool

3.程序基本语句

  • 【2】cin 语句,scanf 语句,cout 语句,printf 语句,赋值语句,复合语句
  • 【2】if 语句,switch 语句,多层条件语句
  • 【2】for 语句,while 语句,do while 语句
  • 【3】多层循环语句

4.基本运算

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

5.数学库常用函数

  • 【3】绝对值函数,四舍五入函数,取上整函数, 取下整函数,常用三角函数,对数函数,指数 函数,平方根函数

6.结构化程序设计

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

7.数组

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

8.字符串的处理

  • 【2】字符数组与字符串的关系
  • 【2】字符数组的综合应用
  • 【2】string 类定义、相关函数引用
  • 【3】string 类的综合应用

9.函数与递归

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

10.结构体类型

  • 【3】结构体的定义及应用

11.指针类型

  • 【4】指针的概念及调用
  • 【4】指针与数组
  • 【4】字符指针与 string 类
  • 【4】指向结构体的指针

12.文件及基本读写

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

13.STL 模板应用

  • 【3】中 sort 函数
  • 【4】 栈(stack)、 队列(queue)、链表(list)、向量(vector)等容器

1 C++以外的其他高级程序设计语言可参照本部分内容。

2.1.3 数据结构    

1.线性表

  • 【3】链表:单链表、双向链表、循环链表
  • 【3】栈
  • 【3】队列

2.简单树

  • 【3】树的定义及其相关概念
  • 【4】树的父亲表示法
  • 【3】二叉树的定义及其基本性质
  • 【4】二叉树的孩子表示法
  • 【4】二叉树的遍历:前序、中序、后序遍历

3.特殊树

  • 【4】完全二叉树的定义与基本性质
  • 【4】完全二叉树的数组表示法
  • 【4】哈夫曼树的定义、构造及其遍历
  • 【4】二叉树的定义、构造及其遍历

4.简单图

  • 【3】图的定义及其相关概念
  • 【4】图的邻接矩阵存储
  • 【4】图的邻接表存储

2.1.4 算法    

1.算法概念与描述

  • 【1】算法概念
  • 【2】算法描述:自然语言描述、流程图描述、伪代码描述

2.入门算法

  • 【1】枚举法
  • 【1】模拟法

3.基础算法

  • 【3】贪心法
  • 【3】递推法
  • 【4】递归法
  • 【4】二分法
  • 【4】倍增法

4.数值处理算法

  • 【4】高精度的加法
  • 【4】高精度的减法
  • 【4】高精度的乘法
  • 【4】求高精度整数除以单精度整数的商和余数

5.排序算法

  • 【3】排序的基本概念(稳定性等)
  • 【3】冒泡排序
  • 【3】简单选择排序
  • 【3】简单插入排序

6.图论算法

  • 【4】图的深度优先遍历算法
  • 【4】图的宽度优先遍历算法
  • 【5】洪水填充算法(floodfill)

7.动态规则

  • 【4】动态规划的基本思路
  • 【4】简单一维动态规划
  • 【5】简单背包类型动态规划
  • 【5】简单区间类型动态规划

2.1.5 数学

1.数及其运算

  • 【1】数的概念,算术运算(加、减、乘、除、求余)
  • 【1】数的进制:二进制、八进制、十六进制和十进制及其转换
  • 【2】编码:ASCII 码,哈夫曼编码,格雷码

2.初中数学

  • 【1】初中代数
  • 【1】初中平面几何

3.初等数论

  • 【3】整除、因数、倍数、指数、质数、合数、同余等概念
  • 【3】唯一分解定理
  • 【3】欧几里得算法(辗转相除法)
  • 【4】埃氏筛法和线性筛法求素数

4.组合数学

  • 【2】加法原理
  • 【2】乘法原理
  • 【4】排列及计算公式
  • 【4】组合及计算公式
  • 【4】杨辉三角公式

2.2 提高级

2.2.1 计算机基础与编程环境

1.【5】在 Linux 系统终端中使用 mkdir、cp、rm、mv 等命令新建、复制、删除、移动文件或目录

2.【5】在 Linux 系统终端中使用 cd、pwd、ls 等命令更改、显示目录路径和查看目录中的文件

3.【5】在 Linux 系统下使用 Gedit、Vim 或 Emacs 等文本编辑工具编写代码

4.【5】熟悉 g++、gcc 等编译器以及优化、数学库等常见编译选项

5.【5】在 Linux 系统终端中运行程序,并使用 time 命令查看程序用时(区分 real time、sys time 和 user time)

6.【5】了解调式工具 gdb 及其 break、display、continue、step 等命令

2.2.1 C++程序设计 2    

1.类(class)

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

2.STL 模板

  • 【5】集合(set)
  • 【5】列表(list),双端队列(deque),优先队列(priority_queue)
  • 【5】多重集合(multiset)
  • 【5】映射(map),多重映射(multimap)
  • 【5】对(pair),元组(tuple)

2 C++以外的其他高级程序设计语言可参照本部分内容

2.2.2 数据结构

1.线性结构

  • 【5】双端栈
  • 【5】双端队列
  • 【5】有序队列
  • 【6】优先队列
  • 【6】倍增表(ST 表)

2.集合与森林

  • 【6】等价类
  • 【6】并查集
  • 【6】树与二叉树的转化——孩子兄弟表示法

3.特殊树

  • 【6】线段树与树状数组
  • 【6】字典树(trie 树)
  • 【7】笛卡尔树
  • 【8】二叉平衡树 AVL、treap、splay 等
  • 【8】基环树

4.常见图

  • 【5】稀疏图
  • 【6】偶图(二分图)
  • 【6】欧拉图
  • 【6】有向无环图
  • 【7】连通图与强连通图
  • 【7】重连通图

5.哈希表

  • 【5】数值哈希函数构造
  • 【6】排列哈希函数构造
  • 【6】字符串哈希函数构造
  • 【6】哈希函数冲突的常见解决方法

2.2.3 算法

1.复杂度分析

  • 【6】空间复杂度分析
  • 【6】时间复杂度分析

2.基础算法

  • 【6】分治算法

3.排序算法

  • 【5】归并排序
  • 【5】快速排序
  • 【6】堆排序
  • 【6】树形选择排序(锦标赛排序)
  • 【5】桶排序
  • 【6】基数排序

4.字符串相关算法

  • 【5】字符串匹配算法——KMP

5.搜索算法

  • 【6】搜索的剪枝优化
  • 【6】记忆化搜索
  • 【7】启发式搜索
  • 【7】双向宽度优先搜索
  • 【7】迭代加深搜索
  • 【8】搜索对象的压缩存储

6.图论算法

  • 【6】Prim 和 Kruskal 等求最小生成树算法
  • 【7】求次小生成树算法
  • 【6】Dijkstra、bellman ford、SPFA 等求单源最短路算法
  • 【7】求单源次短路径算法
  • 【6】Floyd-Warshall 算法求任意两点间的最短路和传递闭包
  • 【6】有向无环图的拓扑排序算法
  • 【6】求欧拉道路和欧拉回路算法
  • 【6】二分图的构造及其判定算法
  • 【6】最近公共祖先
  • 【7】求强联通分量算法
  • 【7】强连通分量的缩点算法
  • 【7】求割点、割边算法

7.动态规划

  • 【6】树型动态规划
  • 【7】状态压缩动态规划
  • 【8】动态规划的常用优化

2.2.4 数学

1.高中数学

  • 【5】代数
  • 【6】解析几何
  • 【6】立体几何

2.初等数论

  • 【5】同余式
  • 【7】欧拉定理和欧拉函数
  • 【7】费马小定理
  • 【7】威尔逊定理
  • 【7】裴蜀定理
  • 【7】逆元
  • 【7】扩展欧几里得算法
  • 【7】孙子定理(即中国剩余定理)

3.组合数学

  • 【6】可重集排列
  • 【6】可重集组合
  • 【6】错排列、圆排列
  • 【6】鸽巢原理
  • 【6】二项式定理
  • 【7】容斥原理
  • 【7】卡特兰数

4.线性代数

  • 【5】矩阵概念
  • 【6】特殊矩阵:稀疏矩阵,三角矩阵,对称矩阵
  • 【6】矩阵的初等变换
  • 【6】矩阵的加减乘和转置运算
  • 【7】线性方程组的高斯消元法

2.3 NOI 级

2.3.1 C++程序设计 3

1.【8】STL 模板:容器(containers)、迭代器(iterators)、空间配置器(allocators)、配接器(adapters)、算法(algorithms)、仿函数(functors)

2.【8】面向对象的程序设计思想(OOP)

3. C++以外的其他高级程序设计语言可参照本部分内容

2.3.2 数据结构

1.线性结构

  • 【8】分块
  • 【8】块状链表

2.序列

  • 【8】后缀数组
  • 【9】跳跃表
  • 【9】无根树的 Prüfer 序列

3.复杂树

  • 【8】树链剖分
  • 【8】主席树
  • 【8】二位线段树
  • 【9】后缀树
  • 【9】树套树
  • 【9】k-d 树
  • 【10】最小树形图
  • 【10】动态树(LCT)

4.可合并堆

  • 【8】左偏树
  • 【10】二项堆

   5.【9】可持久化数据结构
2.3.3 算法

1.算法策略

  • 【9】复杂分治思想
  • 【9】平衡规划思想
  • 【9】构造思想

2.字符串算法

  • 【8】求最长回文串的 Manacher 算法
  • 【8】多模匹配算法——AC 自动机
  • 【9】求字符串前缀和后缀算法——扩展 KMP
  • 【9】确定性有穷自动机——DFA 算法
  • 【10】非确定性有穷自动机——NFA 算法
  • 【10】后缀自动机

3.图论算法

  • 【8】网络流算法
  • 【10】图的支配集、独立集与覆盖集
  • 【8】二分图的最大匹配——匈牙利算法
  • 【9】二分图的最佳匹配算法——KM 算法
  • 【10】一般图的匹配

4.动态规划

  • 【9】复杂动态规划模型构建
  • 【9】复杂动态规划模型的优化

2.2.4 数学
1.信息论基础

  • 【10】熵、互信息、条件熵、相对熵的基本概念
  • 【10】信息复杂度的基本概念
  • 【10】描述复杂度的基本概念
  • 【10】通讯复杂度的基本概念

2.初等数论

  • 【8】原根和指数
  • 【8】大步小步(Baby Step Giant Step,BSGS)算法
  • 【9】完全数
  • 【9】狄利克雷(Dirichlet)卷积
  • 【10】平方剩余
  • 【10】二次同余式
  • 【10】二次互反律

3.离散数学

  • 【9】代数系统的基本概念
  • 【9】群的基本概念
  • 【9】置换群与循环群

4.组合数学

  • 【9】母函数
  • 【9】莫比乌斯变换
  • 【9】Burnside 引理与 Pólya 原理
  • 【9】斯特林数

5.高等数学

  • 【9】多项式函数微分
  • 【9】多项式函数积分
  • 【10】泰勒级数
  • 【10】快速傅里叶变换(Fast Fourier Transform,FFT)
  • 【10】卷积

6.线性代数

  • 【9】矩阵的逆运算
  • 【9】行列式及其运算
  • 【9】线性相关与矩阵的逆

7.概率论

  • 【8】概率相关概念
  • 【9】求概率的乘法公式、全概率公式、贝叶斯公式

8.博弈论

  • 【9】零和博弈问题——Nim 博弈等
  • 【9】Sprague-Garundy(SG)函数概念及应用

9.运筹学

  • 【10】线性规划之单纯形法

10.计算几何

  • 【7】矢量及其运算
  • 【8】点、线、面之间的位置判断
  • 【8】常见图形的面积计算
  • 【8】二维凸包的求及其应用
  • 【9】半平面交