GESP等级考试C++&Python编程八级标准

（一）知识点详述

（1）掌握计数原理。包括加法原理和乘法原理。

（2）掌握排列与组合基础知识。包括排列、组合的基本概念，及能实现基础排列和组合编程问题的一般方法。

（3）掌握杨辉三角形（又称帕斯卡三角形）的概念。

（4）掌握倍增法概念。了解倍增法的时间复杂度。

（5）掌握代数与平面几何基础知识（初中数学部分）。包括方程的概念及一元一次方程、二元一次方程的基本求解技巧，求基础平面几何概念、求基本图形（如长方形、三角形、圆形等）的面积等。

（6）掌握图论算法及综合应用技巧。包括最小生成树的概念、kruskal算法、prim算法，掌握最短路径的概念、单源最短路径的dijkstra算法、Floyd 算法等。理解实现同一功能的不同算法的比较，并可以灵活解决相关问题。

（7）算法的时间和空间效率分析。能够掌握较为复杂算法的时间和空间复杂度分析方法，能够分析各类算法（包括排序算法、查找算法、树和图的遍历算法、搜索算法、分治及动态规划算法等）的时间和空间复杂度。

（8）算法优化。理解不同方法求解一个问题在时间复杂度和空间复杂度上的差异，理解使用数学知识辅助求解问题的技巧（如可以用循环求出等差数列的和，也可以用数学公式求出等差数列的和），掌握一般的算法优化技巧。

（二）考核目标

掌握基本计数原理，理解加法原理和乘法原理的区别与使用。掌握排列组合概念，能够实现常见排列组合问题的编程求解方法。掌握杨辉三角形的概念和应用，了解杨辉三角形与组合之间的关系。掌握代数与平面几何的基本知识（限初中数学），能够求解一元一次方程、二元一次方程并掌握平面几何基本知识。掌握较为复杂算法的时间复杂度和空间复杂度分析方法，及其一般的算法优化技巧，能根据数学知识优化算法。

（三）知识块

（四）知识点描述

（五）题型分布

考试时间：180分钟