信息学奥林匹克辞典——全国青少年信息学奥林匹克系列竞赛大纲详解

序Ⅰ
序Ⅱ
前言
符号表
主要信息学竞赛及相关活动列表
入门级
1.1　基础知识与编程环境3
1.1.1　计算机的基本构成3
1.1.2　Windows、Linux等操作系统的基本概念及其常见操作3
1.1.3　计算机网络和Internet的基本概念4
1.1.4　计算机的历史和常见用途4
1.1.5　NOI以及相关活动的历史6
1.1.6　NOI以及相关活动的规则7
1.1.7　位、字节与字8
1.1.8　程序设计语言以及程序编译和运行的基本概念8
1.1.9　使用图形界面新建、复制、删除、移动文件或目录9
1.1.10　使用Windows系统下的集成开发环境10
1.1.11　使用Linux系统下的集成开发环境10
1.1.12　g 、gcc等常见编译器的基本使用10
1.2　C 程序设计11
1.2.1　程序基本概念11
1.2.2　基本数据类型14
1.2.3　程序基本语句16
1.2.4　基本运算21
1.2.5　数学库常用函数24
1.2.6　结构化程序设计25
1.2.7　数组27
1.2.8　字符串的处理29
1.2.9　函数与递归30
1.2.10　结构体与联合体34
1.2.11　指针类型35
1.2.12　文件及基本读写38
1.2.13　STL模板40
1.3　数据结构44
1.3.1　线性结构44
1.3.2　简单树48
1.3.3　特殊树52
1.3.4　简单图59
1.4　算　法65
1.4.1　算法概念与描述65
1.4.2　入门算法66
1.4.3　基础算法69
1.4.4　数值处理算法74
1.4.5　排序算法82
1.4.6　搜索算法88
1.4.7　图论算法90
1.4.8　动态规划93
1.5　数学与其他100
1.5.1　数及其运算100
1.5.2　初等数论102
1.5.3　离散与组合数学108
1.5.4　其他113
提高级
2.1　基础知识与编程环境117
2.1.1　Linux系统终端中常用的文件与目录操作命令117
2.1.2　Linux系统下常见文本编辑工具的使用118
2.1.3　g 、gcc等编译器与相关编译选项119
2.1.4　在Linux系统终端中运行程序，使用time命令查看程序用时120
2.1.5　调试工具GDB的使用120
2.2　C 程序设计121
2.2.1　类121
2.2.2　STL模板125
2.3　数据结构135
2.3.1　线性结构135
2.3.2　集合与森林144
2.3.3　特殊树146
2.3.4　常见图161
2.3.5　哈希表166
2.4　算　法169
2.4.1　复杂度分析169
2.4.2　算法策略（离散化）173
2.4.3　基础算法（分治算法）173
2.4.4　排序算法174
2.4.5　字符串相关算法（字符串匹配：KMP算法）182
2.4.6　搜索算法184
2.4.7　图论算法188
2.4.8　动态规划218
2.5　数学与其他224
2.5.1　初等数学224
2.5.2　初等数论224
2.5.3　离散与组合数学229
2.5.4　线性代数234
NOI级
3.1　C 程序设计（面向对象的程序设计思想）243
3.2　数据结构244
3.2.1　线性结构（块状链表）244
3.2.2　序列（跳跃表）245
3.2.3　复杂树246
3.2.4　可合并堆267
3.2.5　可持久化数据结构270
3.3　算　法275
3.3.1　算法策略275
3.3.2　字符串算法282
3.3.3　图论算法295
3.3.4　动态规划322
3.4　数学与其他330
3.4.1　初等数论330
3.4.2　离散与组合数学335
3.4.3　线性代数342
3.4.4　高等数学344
3.4.5　概率论349
3.4.6　博弈论352
3.4.7　*优化（单纯形法）353
3.4.8　计算几何357
3.4.9　信息论（熵、互信息、条件熵、相对熵）362
3.4.10　其他363