CSP-J信息学奥赛考试大纲（入门级）

2.1.1计算机基础与编程环境
[1] 计算机的基本构成(CPU、内存、I/O设备等)
[1] Windows、Linux等操作系统的基本概念及其常见操作
[1]计算机网络和Internet的基本概念
[1] 计算机的历史及其在现代社会中的常见应用
[1] NOI以及相关活动的历史
[1] 进制的基本概念与进制转换、字节与字
[1] 程序设计语言以及程序编译和运行的基本概念
[1] 使用图形界面新建、复制、删除、移动文件或目录[1] 使用Windows系统下的集成开发环境(例如Dev C++等)[1] 使用Linux系统下的集成开发环境(例如Code:: Blocks等)
[1] g++、gcc等常见编译器的基本使用
2.1.2 C++程序设计
1.程序基本概念
[1] 标识符、关键字、常量、变量、字符申、表达式的概念
[1] 常量与变量的命名、定义及作用
[1] 头文件与名字空间的定义与理解
[1] 编辑、编译、解释、调试等概念理解
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] 逻辑运算: 与(&&)、或(I)、非()
[1] 变量自增与自减运算
[1] 三目运算
[2] 位运算: 与(&)、或()、非()异或()、左移、右移5.数学库常用函数
[3] 值函数，四舍五入函数，取上整函数，取下整函数，常用三角函数，对数函数，指数函数，平方根函数6.结构化程序设计
[1] 顺序结构、分支结构和循环结构
[1] 自顶向下、逐步求精的模块化程序设计
[2] 流程图的概念及流程图描述
7.组
[1] 数组定义，数组与数组下标的含义
[1] 数组的读入与输出
[2] 纯一维数组的综合运用
[3] 纯二维数组与多维数组的综合应用
8.字符串的处理
[2]字符数组与字符串的关系
[2]字符数组的综合应用
[2]线类定义、相关函数引用
[3]线类的综合应用
9.函数与递归
[2]函数定义与调用，形参与实参
[3]传值参数与传引用参数
[2]常量与变量的作用范围
[2]递归函数的概念、定义与调用
10.结构体类型
[3]结构体的定义及应用
11.指针类型
[4]指针的概念及调用
[4]针与数组
[4]字符指针与string类
[4]指向结构体的指针
12.文件及基本读写
[2]文件的基本概念，文本文件的基本操作
[2]文本文件类型与二进制文件类型
[2] 文件重定向、文件读写等操作
13STL模板应用
[3] 中sort函数
[4]栈(stack)、队列(queue)、链表(list)、向量(vector)等容器
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] 编码: ASCI码，哈夫曼编码，格雷码
2.初中数学
[1] 初中代数
[1] 初中平面几何
3.初等数论
[3] 整除、因数、倍数、指数、质数、合数、同余等概念
[3] 分解定理
[3] 欧几里德算法(辗转相除法)
[4] 埃氏筛法和线性筛法求素数
4.组合数学
[2] 加法原理
[2] 乘法原理
[4] 排列及计算公式
[4] 组合及计算公式
[4] 杨辉三角公式