全国青少年信息学奥林匹克系列竞赛大纲
（草案）
1.介绍
1.1目的
本大纲的制定目的在于：
（1）为NOI系列竞赛题目的命制提供依据；
（2）为NOI指导教师的教学提供方向和指导；
（3）为参加NOI系列活动的学生及其他信息学爱好者提供学习范围；
（4）为各省市开展和组织NOI省选等工作提供参照。
1.2原则
（1）差异化原则
为促进信息学和NOI活动的普及，大纲应较详尽地规定中低等级知识点的范围，以尽可能清晰地划定相应等级的知识范围，有效地指导入门学生的学习及相关的教学活动；为促进NOI的国际竞争力，大纲应避免过于严格地限制命题的思路，须为NOI等高水平竞赛的题目命制留有充分的开放性，因此不宜过于细致地规定高等级知识点的范围。
为此，大纲的制定将采取“上粗下细”的指导思想：知识等级越低，其内容规定得越细；知识等级越高，其内容规定得越粗。
（2）统一性原则
为保证大纲的简明性和系统性，高等级比赛的知识范围将自动地包含低等级比赛的所有知识点。同时，对每个等级按照竞赛环境（Linux和Windows）、程序设计语言（C++）、数据结构、算法、以及数学等进行了分类。对每个大类又按照知识点的属性继续划分为若干小类；某些知识点可能与多个类别均有紧密或松散
联系，本大纲均按其主要属性划定其类别，以避免同一知识点在多个类别中的重复出现。
2.考纲内容
2.1全国青少年信息学奥林匹克联赛普及组（简称NOIP-J）
2.1.1C++集成调试工具（IDE）使用
1.Windows系统下：例如Dev C++,….，等【1】
2.Linux系统下：例如Guide，…，等【1】
2.1.2C++程序设计
1.程序基本概念
a)标识符、关键字、常量、变量、字符串、表达式的概念【1】
b)常量与变量的命名、定义及作用【1】
c)头文件与名字空间的定义与理解【2】
d)编辑、编译、解释、调试等概念理解【2】
2.基本数据类型
a)整型：int,long long【1】
b)实型：float,double【1】
c)字符型：char【1】
d)逻辑型：bool【1】
3.程序基本语句
a)cin语句，scanf语句，cout语句，printf语句，赋值语句，复合语句
【2】
b)if语句，switch语句，多层条件语句【2】
c)for语句，while语句，do while语句
d)多层循环语句【3】
4.基本运算
a)算术运算：加、减、乘、除、整除、求余【1】
b)关系运算：大于，大于等于，小于，小于等于，等于，不等于【1】
c)逻辑运算：与&&、或||、非！【1】
d)变量自增与自减运算【1】
e)三目运算【1】
f)位运算：与&、或|、非~、异或^、左移、右移【2】
5.数学库常用函数
绝对值函数，四舍五入函数，取上整函数，取下整函数，常用三角函
数，对数函数，指数函数，平方根函数【3】
6.结构化程序设计
a)顺序结构、分支结构和循环结构【1】
b)自顶向下、逐步求精的模块化程序设计【2】
c)流程图的概念及流程图描述【2】
7.数组
a)数组定义，数组与数组下标的含义【1】
b)数组的读入与输出【1】
c)纯一维数组的综合运用【2】
d)纯二维数组与多维数组的综合应用【3】
8.字符串的处理
a)字符数组与字符串的关系【2】
b)字符数组的综合应用【2】
c)string类定义、相关函数引用【2】
d)string类的综合应用【3】
9.函数与递归
a)函数定义与调用，形参与实参【2】
b)传值参数与传引用参数【3】
c)常量与变量的作用范围【2】
d)递归函数的概念、定义与调用【2】
10.结构体类型
a)结构体的定义及应用【3】
11.指针类型
a)指针的概念及调用【4】
b)指针与数组【4】
c)指针与string类【4】
d)指向结构体的指针【4】
12.文件的读写操作
a)文件的基本概念，文本文件的基本操作【2】
b)文件类型【2】
c)文件读入、输出等操作【2】
13.STL模板应用
a)<algorithm>中sort函数【3】
b)栈（stack）、队列（queue）、链表（list）、集合（set）等容器【4】
2.1.3数据结构
1.线性表
a)链表：单链表、双向链表、循环链表【3】
欧拉linux系统
b)栈【3】
c)队列【3】
2.简单树
a)树的定义及其相关概念【3】
b)树的父亲表示法【4】
c)二叉树的定义及其基本性质【3】
d)二叉树的孩子表示法【4】
e)二叉树的遍历：前序、中序、后序遍历【4】
3.特殊树
a)完全二叉树的定义与基本性质【4】
b)完全二叉树的数组表示法【4】
c)哈夫曼树的定义、构造及其遍历【4】
d)二叉排序树的定义、构造及其遍历【4】
4.简单图
a)图的定义及其相关概念【3】
b)图的邻接矩阵存储【4】
c)图的邻接表存储【4】
2.1.4算法
1.算法概念与描述
a)算法概念【1】
b)算法描述：自然语言描述、流程图描述、伪代码描述【2】
2.入门算法
a)枚举法【1】
b)模拟法【1】
3.基础算法
a)贪心法【3】
b)递推法【3】
c)递归法【4】
d)二分法【4】
e)倍增法【4】
4.数值处理算法
a)高精度的加法【4】
b)高精度的减法【4】
c)高精度的乘法【4】
d)求高精度整数除以单精度整数的商和余数【4】
5.排序算法
a)冒泡排序【3】
b)简单选择排序【3】
c)简单插入排序【3】
6.图论算法
a)图的深度优先遍历算法【4】
b)图的宽度优先遍历算法【4】
c)洪水填充算法（floodfill）【5】
7.动态规划
a)动态规划的基本原理【4】
b)简单线型动态规划【4】
c)简单背包类型动态规划【5】
d)简单区间类型动态规划【5】
2.1.5数学
1.数及其运算
a)数的概念，算术运算（加、减、乘、除、求余）【1】
b)数制：二进制、八进制、十六进制和十进制数及其转换【1】
c)编码：ASCII码，哈夫曼编码，格雷码【2】
2.初中数学
a)初中代数【1】
b)初中平面几何【1】
3.初等数论
a)整除、因数、倍数、指数、质数、合数、同余等概念【3】
b)唯一分解定理【3】
c)欧几里德算法（辗转相除法）【3】
d)埃氏筛法和线性筛法求素数【4】
4.组合数学
e)加法原理【2】
f)乘法原理【2】
g)排列及计算公式【4】
h)组合及计算公式【4】
i)杨辉三角公式【4】
2.2全国青少年信息学奥林匹克联赛提高组（简称NOIP-S）
2.2.1Linux系统
1.会使用mkdir、cp、rm、mv等命令新建、复制、删除、移动等文件或
目录【5】
2.会使用cd、pwd、ls等命令更改、显示目录路径和查看目录中的文件
【5】