数据结构与算法设计自学考试大纲[4]

第六章 二叉树和树

本章介绍了树和森林的定义特别介绍了二叉树的定义`二叉树的性质`二叉树的存储结构及二叉树基本操作的实现对二叉树的周游算法作了详细描述森林与二叉树之间的转换为树提供了一种自然的存储结构哈夫曼树和哈夫曼编码是树的一个重要应用树的另一个重要应用是描述状态空间回溯法是问题求解的有效方法

考核知识点

()基本概念: 树树根空树子树森林叶结点分支结点双亲结点孩子结点祖先结点子孙结点兄弟结点堂兄弟结点结点的度树的高度二叉树左子树右子树满二叉树完全二叉树二叉树的周游树和森林的周游树的路径长度树的带权路径长度哈夫曼树哈夫曼编码回溯等

()树和森林的定义

()二叉树的定义及其递归结构

()二叉树的存储结构

()二叉树的周游算法

()树的存储结构

()森林与二叉树的转换

()哈夫曼树构造算法

自学要求

熟悉二叉树的逻辑结构的存储结构

理解二叉树的递归结构及利用这种结构的算法

掌握二叉树周游递归与非递归算法

掌握将森林转换成二叉树的算法

掌握用哈夫曼树对通讯符号进行哈夫曼编码的方法

考核目标

识记有关基本概念

理解二叉树`树`森林的递归定义

掌握二叉树的二叉链表表示法和顺序表示法

掌握树和森林的孩子兄弟表示法

掌握二叉树`树`森林的周游算法

掌握二叉树和树在问题求解中的应用

分析哈夫曼树和哈夫曼编码的特性

第七章 图和广义表

本章介绍了图的类型定义及图的表示方法和图的基本操作着重介绍了图的应用以及蕴含在其中的问题求解技术例外还简单的介绍了广义表的基本概念存储结构和遍历算法

知识点

()基本概念: 图有向图无向图有向弧边顶点邻接顶点与顶点关联的边(弧)顶点的编号顶点的度顶点的入度顶点的出度生成树最小代价生成树拓扑有序拓扑排序有向无环图AOV网AOE网关键路径关键活动广义表等

()图的定义及存储结构

()图基本操作的实现

()深度优先搜索和广度优先搜索

()生成树构造算法

()普里姆算法和克鲁斯卡尔算法

()拓扑排序算法

()求关键路径算法

()迪杰斯特拉算法和弗洛伊德算法

自学要求

理解无向图和有向图的定义

理解图的表示方法

掌握图的周游算法

掌握构造生成森林的步骤

掌握普里姆算法和克鲁斯卡尔算法的使用方法

掌握拓扑排序和逆拓扑排序在求关键路径中的作用

掌握迪杰斯特拉算法和弗洛伊德算法的使用方法

考核目标

识记有关基本概念和术语

理解图的表示方法及其适用范围

理解图的基本操作的实现算法

运用图求解实际问题

综合分析图特性的能力

编写有关图的算法和程序的能力

[] [] [] [] [] [] [] [] []