数据结构教学中的重点与难点_数据结构的重点和难点
数据结构教学中的重点与难点由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构的重点和难点”。
第一章 数据结构基本概念
1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。
2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象 = 对象 + 类 + 继承 + 通信。
要点： * 抽象数据类型的封装性 * 面向对象系统结构的稳定性
* 面向对象方法着眼点在于应用问题所涉及的对象
3、数据结构的抽象层次：理解用对象类表示的各种数据结构
4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
要点： * 算法与程序的不同之处需要从算法的特性来解释 * 算法的正确性是最主要的要求 * 算法的可读性是必须考虑的* 程序的程序步数的计算与算法的事前估计
* 程序的时间代价是指算法的渐进时间复杂性度量 第二章 数组
1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储
要点： * 数组元素的存放地址计算
2、顺序表：顺序表的定义、搜索、插入与删除 要点： * 顺序表搜索算法、平均比较次数的计算 * 插入与删除算法、平均移动次数的计算
3、多项式：多项式的定义
4、字符串：字符串的定义及其操作的实现 要点： * 串重载操作的定义与实现
第三章 链接表
1、单链表：单链表定义、相应操作的实现、单链表的游标类。要点： * 单链表的两种定义方式（复合方式与嵌套方式）* 单链表的搜索算法与插入、删除算法 * 单链表的递归与迭代算法
2、循环链表：单链表与循环链表的异同
3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点
4、多项式的链接表示
第四章 栈与队列
1、栈：栈的特性、栈的基本运算
要点： * 栈的数组实现、栈的链表实现
* 栈满及栈空条件、抽象数据类型中的先决条件与后置条件
2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示
3、队列：队列的特性、队列的基本运算
要点： * 队列的数组实现：循环队列中队头与队尾指针的表示，队满及 队空条件
* 队列的链表实现：链式队列中的队头与队尾指针的表示、4、双向队列：双向队列的插入与删除算法
5、优先级队列：优先级队列的插入与删除算法
第五章 递归与广义表
1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解 要点： * 链表是递归的数据结构，可用递归过程求解有关链表的问题
2、递归实现时栈的应用
要点： * 递归的分层（树形）表示：递归树
* 递归深度（递归树的深度）与递归工作栈的关系 * 单向递归与尾递归的迭代实现
3、广义表：广义表定义、广义表长度、广义表深度、广义表表头、广义表表尾 要点： * 用图形表示广义表的存储结构 * 广义表的递归算法 第六章 树与森林
1、树：树的定义、树的基本运算 要点： * 树的分层定义是递归的 * 树中结点个数与高度的关系
2、二叉树：二叉树定义、二叉树的基本运算
要点： * 二叉树性质、二叉树中结点个数与高度的关系、不同种类的二 叉树棵数
* 完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位 置
* 二叉树的前序·中序·后序·层次遍历
* 前序·中序·后序的线索化二叉树、前驱与后继的查找方法
3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算
4、树的存储：树的广义表表示、树的双亲表示、树与二叉树的对应关系、树的先根·中根·后根·层次遍历。
5、堆：堆的定义、堆的插入与删除算法
要点： * 形成堆时用到的向下调整算法及形成堆时比较次数的上界估计 * 堆插入时用到的向上调整算法 第七章 集合与搜索
1、集合的概念：集合的基本运算、集合的存储表示 要点： * 用位数组表示集合时集合基本运算的实现 * 用有序链表表示集合时集合基本运算的实现
2、并查集：并查集定义、并查集的三种基本运算的实现
3、基本搜索方法
要点： * 对一般表的顺序搜索算法（包括有监视哨和没有监视哨）* 对有序顺序表的顺序搜索算法、用判定树（即扩充二叉搜索树）
描述搜索，以及平均搜索长度（成功与不成功）的计算。
* 对有序顺序表的折半搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。
4、二叉搜索树：
要点： * 动态搜索树与静态搜索树的特性
* 二叉搜索树的定义、二叉搜索树上的搜索算法、二叉搜索树搜 索时的平均搜索长度（成功与不成功）的计算。
* AVL树结点上的平衡因子、AVL树的平衡旋转方法 * 高度为h的AVL树上的最少结点个数与最多结点个数 * AVL树的搜索方法、插入与删除方法 第八章 图
1、图：图的定义与图的存储表示
要点： * 邻接矩阵表示（通常是稀疏矩阵）* 邻接表与逆邻接表表示 * 邻接多重表(十字链表)表示
2、深度优先遍历与广度优先遍历 要点： * 生成树与生成树林的定义
* 深度优先搜索是个递归的过程，而广度优先搜索是个非递归的 过程
* 为防止重复访问已经访问过的顶点，需要设置一个访问标志数 组visited3、图的连通性
要点： * 深度优先搜索可以遍历一个连通分量上的所有顶点 * 对非连通图进行遍历，可以建立一个生成森林 * 对强连通图进行遍历，可能建立一个生成森林 * 关节点的计算和以最少的边构成重连通图
4、最小生成树
要点： * 对于连通网络、可用不会构成环路的权值最小的n-1条边构成 最小生成树
* 会画出用Kruskal算法及Prim算法构造最小生成树的过程
5、单源最短路径
要点： * 采用逐步求解的方式求某一顶点到其他顶点的最短路径 * 要求每条边的权值必须大于零
6、活动网络
要点： * 拓扑排序、关键路径、关键活动、AOE网 * 拓扑排序将一个偏序图转化为一个全序图。* 为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈 * 关键路径的计算 第九章 排序
1、基本概念：关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序
2、插入排序：
要点： * 当待排序的关键码序列已经基本有序时，用直接插入排序最快
3、选择排序：
要点： * 用直接选择排序在一个待排序区间中选出最小的数据时，与区 间第一个数据对调，而不是顺次后移。这导致方法不稳定。* 当在n个数据（n很大）中选出最小的5 ~ 8个数据时，锦标 赛排序最快
* 锦标赛排序的算法中将待排序的数据个数n补足到2的k次幂 2k-1
4、交换排序：
要点： * 快速排序是一个递归的排序方法
* 当待排序关键码序列已经基本有序时，快速排序显著变慢。
5、二路归并排序：
要点： * 归并排序可以递归执行
* 归并排序需要较多的附加存储。可以采用一种“推拉法”（参 见教科书上习题）实现归并排序，算法的时间复杂度为O(n)、空间复杂度为O(1)* 归并排序对待排序关键码的初始排列不敏感，排序速度较稳定
6、外排序
要点： * 多路平衡归并排序的过程、I/O缓冲区个数的配置 * 外排序的时间分析、利用败者树进行多路平衡归并 * 利用置换选择方法生成不等长的初始归并段 * 最佳归并树的构造及WPL的计算
第十章 索引与散列
1、线性索引：
要点： * 密集索引、稀疏索引、索引表计算 * 基于属性查找建立倒排索引、单元式倒排表
2、动态搜索树
要点： * 平衡的m路搜索树的定义、搜索算法 * B树的定义、B树与平衡的m路搜索树的关系
* B树的插入（包括结点分裂）、删除（包括结点调整与合并）方法
* B树中结点个数与高度的关系
* B+树的定义、搜索、插入与删除的方法
3、散列表
要点： * 散列函数的比较 * 装填因子 a 与平均搜索长度的关系，平均搜索长度与表长m 及表中已有数据对象个数n的关系
* 解决地址冲突的（闭散列）线性探查法的运用，平均探查次数 的计算
* 线性探查法的删除问题、散列表类的设计中必须为各地址设置 三个状态
* 线性探查法中的聚集问题
* 解决地址冲突的（闭散列）双散列法的运用，平均探查次数的 计算
* 双散列法中再散列函数的设计要求与表长m互质，为此m设 计为质数较宜
* 解决地址冲突的（闭散列）二次散列法的运用，平均探查次数 的计算
* 注意：二次散列法中装填因子 a 与表长m的设置
*解决地址冲突的（开散列）链地址法的运用，平均探查次数的 计算
