GESP C++&Python 六级认证考试大纲、课程设计

（一）知识点详述

1. 1. 掌握树的基本概念，掌握其构造与遍历的相关算法。
2. 2. 掌握哈夫曼树、完全二叉树、二叉排序树的相关概念和应用。
3. 3. 理解哈夫曼编码、格雷编码相关原理并能进行简单应用。
4. 4. 掌握深度优先搜索算法(DFS)、宽度优先搜索算法(也称广度优先搜索算法，BFS)、二叉树的搜索算法的概念及应用，能够根据现实问题，选择合适的搜索算法。
5. 5. 掌握简单动态规划的算法思想，能够使用代码解决相应的一维动态规划问题和简单背包问题。
6. 6. 掌握面向对象的思想，了解封装、继承、多态的基本概念，并掌握类的创建和基本的使用方法。
7. 7. 掌握栈、队列、循环队列的基本定义，应用场景和常见操作。

（二）考核目标

掌握树的基础知识，并能够分辨和使用哈夫曼树、完全二叉树、二叉排序树。掌握搜索算法，可以根据不同的实际问题选择最优的搜索算法。掌握动态规划的思路和步骤，能够解决一维动态规划问题和简单背包问题。掌握面向对象的概念和特性，了解与面向过程思想的不同之处，并掌握类的创建及其基本使用方法。掌握栈、队列、循环队列的基本定义和常见操作，并可根据实际情况选择合适的数据结构。

（四）知识点描述

1. 1. 树
• • 树的基本概念
• • 哈夫曼树
• • 完全二叉树
• • 二叉排序树
2. 2. 基于树的编码
• • 格雷编码
• • 哈夫曼编码
3. 3. 搜索算法
• • 深度优先搜索算法 (DFS)
• • 宽度优先搜索算法 (也称广度优先搜索算法， BFS)
• • 二叉树的搜索算法
4. 4. 简单动态规划
• • 一维动态规划
• • 简单背包
5. 5. 面向对象
• • 面向对象思想
• • 类的创建和初始化
• • 类的特性：继承、封装、多态
6. 6. 栈和队列
• • 栈
• • 队列
• • 循环队列

（五）题型分布

• • 单选题：15道（2分/道）
• • 判断题：10道（2分/道）
• • 编程题：2道（25分/道）
• • 考试时间：180分钟

课时一：树的基础概念与遍历算法

教学目标

1. 1. 理解树结构的定义、基本术语（节点、根、父节点、子节点、叶节点、深度、高度等）。
2. 2. 掌握树的逻辑结构与存储方式（双亲表示法、孩子表示法、孩子兄弟表示法）。
3. 3. 熟练掌握树的先序、后序、层次遍历算法及其递归与非递归实现。

核心知识点与课程安排

• • 基本概念解析：通过家族树、公司组织架构等生活实例引入树的概念，详解各术语定义。
• • 存储结构剖析：对比分析不同存储结构的适用场景、优缺点及代码实现。
• • 遍历算法精讲：
• • 深度优先遍历：详细推导先序、后序遍历的递归过程，并引入栈结构讲解其非递归实现。
• • 广度优先遍历：引入队列结构讲解层次遍历的实现。
• • 实战练习：实现一个通用树结构的创建、存储和三种遍历，并输出遍历结果。

课时二：特殊二叉树 (I) - 完全二叉树与二叉排序树

教学目标

1. 1. 掌握完全二叉树的性质、判断方法及在数组中的紧凑存储。
2. 2. 理解二叉排序树（BST）的定义、性质及动态维护（查找、插入、删除）。

核心知识点与课程安排

• • 完全二叉树：
• • 讲解定义与性质（编号规则、父子节点索引关系）。
• • 演示如何使用数组高效存储完全二叉树。
• • 应用：优先队列（堆）的基础介绍。
• • 二叉排序树：
• • 从快速查找需求引入BST概念。
• • 分步讲解查找、插入操作的算法与实现。
• • 重点剖析节点删除的三种情况（叶子节点、单子树节点、双子树节点）及处理方法。
• • 实战练习：实现一个二叉排序树，完成一组数据的插入、查找指定值、删除指定节点及中序遍历（验证有序性）操作。

课时三：特殊二叉树 (II) - 哈夫曼树与编码基础

教学目标

1. 1. 理解哈夫曼树的概念、构建过程（贪心思想）及带权路径长度（WPL）的计算。
2. 2. 理解哈夫曼编码的原理及其在数据压缩中的应用。

核心知识点与课程安排

• • 哈夫曼树构建：
• • 通过字符频率统计案例引入问题。
• • 逐步演示哈夫曼树的构建算法：创建节点、优先队列（最小堆）合并。
• • 计算并理解WPL的意义。
• • 哈夫曼编码：
• • 讲解如何从哈夫曼树生成前缀编码。
• • 分析其保证无歧义解码的原理。
• • 对比定长编码，展示其压缩效率。
• • 实战练习：给定一组字符及其频率，编程构建哈夫曼树，输出每个字符的哈夫曼编码，并计算WPL。

课时四：搜索算法入门 - DFS与BFS

教学目标

1. 1. 掌握深度优先搜索（DFS）与广度优先搜索（BFS）的基本思想和算法框架。
2. 2. 能区分两种算法的特点及适用场景，并应用于树和图结构的遍历。

核心知识点与课程安排

• • DFS深度剖析：
• • “一路到底，回溯探寻”的思想讲解。
• • 递归实现模板与显式栈实现模板。
• • 在二叉树遍历上的应用回顾与扩展。
• • BFS广度剖析：
• • “层层递进，涟漪扩散”的思想讲解。
• • 队列实现模板。
• • 在二叉树层次遍历上的应用回顾与扩展。
• • 算法对比与应用：
• • 对比两者在时间复杂度、空间复杂度、解的特性（最短路问题）上的差异。
• • 引入简单网格迷宫问题，分别用DFS和BFS求解路径。
• • 实战练习：在给定的树或简单图结构上，分别使用DFS和BFS进行遍历，并记录节点访问顺序。

课时五：简单动态规划（一维）

教学目标

1. 1. 理解动态规划（DP）的核心思想（最优子结构、重叠子问题、状态转移）。
2. 2. 掌握一维DP问题的分析步骤：定义状态、推导转移方程、确定边界、编码实现。

核心知识点与课程安排

• • DP思想引入：通过经典的斐波那契数列问题（递归 vs 记忆化搜索 vs DP）引入，感受重叠子问题与优化。
• • 核心步骤精讲：结合“爬楼梯”、“最大子数组和”等经典例题，详细拆解DP四步法。
• • 简单背包问题（0/1背包）：
• • 介绍0/1背包问题描述。
• • 推导二维dp[i][j]的状态定义和转移方程。
• • 优化讲解：滚动数组降为一维空间。
• • 实战练习：求解一个具体的0/1背包问题实例，并输出最大价值。

课时六：简单动态规划（背包问题变体）与状态机思想萌芽

教学目标

1. 1. 理解完全背包问题与0/1背包问题的区别及其状态转移。
2. 2. 接触简单的状态机DP模型（如买卖股票I）。

核心知识点与课程安排

• • 完全背包问题：
• • 对比0/1背包，讲解物品无限取用对转移方程的影响。
• • 分析一维优化下内层循环顺序变化的原因。
• • 状态机DP入门：
• • 通过“只能买卖一次股票的最大利润”问题，引入“持有”和“不持有”两种状态。
• • 讲解如何定义dp[i][0]和dp[i][1]，并推导状态间的转移关系。
• • 实战练习：分别编程实现完全背包问题和“买卖股票一次”问题。

课时七：面向对象编程（OOP）基础

教学目标

1. 1. 理解面向对象与面向过程编程思想的区别。
2. 2. 掌握类与对象的基本概念，能定义类、创建对象。
3. 3. 了解封装、继承、多态三大特性的基本含义。

核心知识点与课程安排

• • OOP思想：通过“把数据和操作数据的方法打包在一起”的比喻，讲解类作为蓝图、对象作为实例的概念。
• • 类的创建与使用：
• • 讲解成员变量（属性）和成员函数（方法）。
• • 演示构造函数、析构函数（C++）或__init__（Python）的使用。
• • 三大特性初探：
• • 封装：介绍访问控制（public/private/protected in C++；命名约定 in Python）。
• • 继承：演示基类与派生类的语法，理解“is-a”关系。
• • 多态：通过基类指针/引用调用虚函数（C++）或鸭子类型（Python）简单介绍。
• • 实战练习：设计并实现一个Student类，包含姓名、学号等属性及显示信息的方法。尝试创建一个GraduateStudent类继承自Student，并添加新属性（如导师）。

课时八：栈、队列与循环队列

教学目标

1. 1. 掌握栈（LIFO）和队列（FIFO）的基本概念、操作及应用场景。
2. 2. 理解循环队列的原理，解决普通数组队列“假溢出”的问题。

核心知识点与课程安排

• • 栈：
• • 讲解入栈（push）、出栈（pop）、取栈顶（top）操作。
• • 应用实例：函数调用栈、表达式求值、括号匹配。
• • 队列：
• • 讲解入队（enqueue）、出队（dequeue）、取队首（front）操作。
• • 应用实例：BFS中的使用、任务调度。
• • 循环队列：
• • 分析普通队列的缺点。
• • 讲解循环队列利用数组“首尾相接”的实现方式，重点剖析队空、队满的判断条件。
• • 演示入队、出队操作中指针的循环移动。
• • 实战练习：用数组实现一个循环队列，并测试其基本操作。尝试使用栈解决一个括号匹配问题。