GESP C++ 编程八级考试大纲¶
（一）知识点详述¶
- 掌握计数原理。包括加法原理和乘法原理。
- 掌握排列与组合基础知识。包括排列、组合的基本概念，及能实现基础排列和组合编程问题的一般方法。
- 掌握杨辉三角形（又称帕斯卡三角形）的概念。
- 掌握倍增法概念。了解倍增法的时间复杂度。
- 掌握代数与平面几何基础知识（初中数学部分）。包括方程的概念及一元一次方程、二元一次方程的基本求解技巧，求基础平面几何概念、求基本图形（如长方形、三角形、圆形等）的面积等。
- 掌握图论算法及综合应用技巧。包括最小生成树的概念、
Kruskal算法、Prim算法，掌握最短路径的概念、单源最短路径的Dijkstra算法、Floyd算法等。理解实现同一功能的不同算法的比较，并可以灵活解决相关问题。 - 算法的时间和空间效率分析。能够掌握较为复杂算法的时间和空间复杂度分析方法，能够分析各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及动态规划算法等）的时间和空间复杂度。
- 算法优化。理解不同方法求解一个问题在时间复杂度和空间复杂度上的差异，理解使用数学知识辅助求解问题的技巧（如可以用循环求出等差数列的和，也可以用数学公式求出等差数列的和），掌握一般的算法优化技巧。
（二）考核目标¶
掌握基本计数原理，理解加法原理和乘法原理的区别与使用。掌握排列组合概念，能够实现常见排列组合问题的编程求解方法。掌握杨辉三角形的概念和应用，了解杨辉三角形与组合之间的关系。掌握代数与平面几何的基本知识（限初中数学），能够求解一元一次方程、二元一次方程并掌握平面几何基本知识。掌握较为复杂算法的时间复杂度和空间复杂度分析方法，及其一般的算法优化技巧，能根据数学知识优化算法。
（三）知识块与知识点描述¶
| 编号 | 知识块 | 知识点 |
|---|---|---|
| 1 | 计数原理 | 加法原理、乘法原理 |
| 2 | 排列与组合 | 排列、组合 |
| 3 | 杨辉三角 | 杨辉三角的定义、实现方法 |
| 4 | 倍增法 | 倍增法的基本概念与复杂度 |
| 5 | 代数与几何 | 一元一次方程、二元一次方程、基本图形面积计算 |
| 6 | 图论算法及综合应用 | 最小生成树的概念、Kruskal 算法、Prim 算法、最短路径的概念、Dijkstra 算法、Floyd 算法、图论算法的综合应用与问题求解技巧 |
| 7 | 算法时间和空间效率分析 | 算法时间和空间复杂度的一般分析方法、各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及动态规划算法等）的时间和空间复杂度 |
| 8 | 算法优化 | 不同算法求解问题的差异分析、算法优化的一般方法、根据数学知识优化算法的一般方法（包括但不局限于等差、等比数列的求和公式等） |
（四）题型分布¶
- 单选题：15 道（2 分/道）
- 判断题：10 道（2 分/道）
- 编程题：2 道（25 分/道）
（五）考试时间¶
180 分钟