【数据结构】复习大纲.ppt

1、上页上页 下页下页节节末页末页结束结束题型说明题型说明l填空题：填空题：29=18l选择题：选择题：310=30l应用题：应用题：74=28l算法设计题算法设计题:122=24上页上页 下页下页节节末页末页结束结束算法设计题算法设计题l范围：范围：线性表相关操作线性表相关操作栈和队列的基本操作与应用栈和队列的基本操作与应用二叉树的创建、销毁、先中后序遍历二叉树的创建、销毁、先中后序遍历,求树深、求树深、结点数、叶结点数、复制、左右子树互换、查结点数、叶结点数、复制、左右子树互换、查找、删除找、删除(参考例程参考例程)。树的简单操作。树的简单操作图的存储结构与图的遍历图的存储结构与图的遍历顺序查

2、找、折半查找、二叉排序树查找顺序查找、折半查找、二叉排序树查找排序排序从课件中出现的算法看起从课件中出现的算法看起l资料资料:课件课件+例程例程+作业作业+教材教材+样题样题+推荐习题推荐习题上页上页 下页下页节节末页末页结束结束第一章第一章 绪论绪论 小结小结理解数据结构、逻辑结构理解数据结构、逻辑结构(分类分类)、存储结构的概念、存储结构的概念；给出数据元素及关系能给出所属逻辑结构；理解关系给出数据元素及关系能给出所属逻辑结构；理解关系的顺序映像与链式映像，前者形成一个数组，后者形的顺序映像与链式映像，前者形成一个数组，后者形成一个链表，掌握各自优缺点成一个链表，掌握各自优缺点,会根据操作

3、性质确定采会根据操作性质确定采用顺序存储结构或链式存储结构用顺序存储结构或链式存储结构掌握抽象数据类型的概念、表示和掌握抽象数据类型的概念、表示和实现实现方法方法(有理数有理数)理解算法的特性理解算法的特性(“有穷有穷”性、确定性、可行性、输入、性、确定性、可行性、输入、输出性输出性)，区分算法与程序，区分算法与程序理解时间复杂度的概念，会理解时间复杂度的概念，会计算语句频度和时间复杂计算语句频度和时间复杂度度。理解时间复杂度反映的是算法运行时间随问题规。理解时间复杂度反映的是算法运行时间随问题规模的增长率模的增长率T(n)=O(f(n)上页上页 下页下页节节末页末页结束结束第二章第二章 线性

4、表线性表1.理解线性结构的定义理解线性结构的定义,掌握线性表与栈和掌握线性表与栈和队列的联系区别队列的联系区别2 2.掌握顺序表与单链表存储结构定义及各自掌握顺序表与单链表存储结构定义及各自优缺点优缺点3.熟练掌握顺序表与单链表各操作的实现熟练掌握顺序表与单链表各操作的实现4.双向链表、双向循环链表的插入、删除双向链表、双向循环链表的插入、删除上页上页 下页下页节节末页末页结束结束1.1.掌握掌握ADTADT栈、队列栈、队列及线性表的区别联系和各自特点及线性表的区别联系和各自特点2.2.熟练掌握熟练掌握顺序栈和链栈顺序栈和链栈的的存储定义存储定义、适用场合、基本、适用场合、基本操作及其实现，特

5、别注意操作及其实现，特别注意栈满栈空栈满栈空的判断和处理的判断和处理3.3.熟练掌握熟练掌握循环队列和链队列循环队列和链队列的的定义定义、适用场合、基本、适用场合、基本操作及其实现，特别注意操作及其实现，特别注意队满和队空队满和队空的判断和处理的判断和处理4.4.熟练掌握熟练掌握栈的用法栈的用法(进制转换进制转换/括号匹配括号匹配/行编辑行编辑)，理，理解栈在递归算法执行过程中的作用解栈在递归算法执行过程中的作用第三章第三章 栈和队列栈和队列 小结小结上页上页 下页下页节节末页末页结束结束 1.1.了解串的概念和基本操作的定义了解串的概念和基本操作的定义 2.2.理解掌握在串的各种存储结构理解

6、掌握在串的各种存储结构第四章第四章 3.3.理解串匹配的理解串匹配的KMPKMP算法，会手工计算给定算法，会手工计算给定模式串的模式串的nextnext函数值和改进的函数值和改进的nextvalnextval函数值函数值,理解理解nextnext和和nextvalnextval的求取算法的求取算法上页上页 下页下页节节末页末页结束结束第五章数组第五章数组理解数组属于线性结构，采用顺序存储理解数组属于线性结构，采用顺序存储对称矩阵、上对称矩阵、上/下三角矩阵、对角矩阵、下三角矩阵、对角矩阵、三对角矩阵的压缩存储与下标计算三对角矩阵的压缩存储与下标计算熟悉稀疏矩阵的熟悉稀疏矩阵的三元组顺序存储表示

7、三元组顺序存储表示，理，理解矩阵的快速转置算法解矩阵的快速转置算法理解广义表的定义理解广义表的定义上页上页 下页下页节节末页末页结束结束1.掌握树与二叉树结构特性与递归定义二叉树结构特性与递归定义,明确二叉树是有序树,掌握二叉树n0n1n2与e及指针个数的关系和满二叉树、完全二叉树的性质,掌握二叉树各存储结构存储结构2.会递归实现二叉树创建、销毁、先中后序遍历和输出、求二叉树创建、销毁、先中后序遍历和输出、求树深、结点数、叶结点数、复制、左右子树互换、查找、树深、结点数、叶结点数、复制、左右子树互换、查找、删除。理解树和森林的深度和叶子树删除。理解树和森林的深度和叶子树3.理解二叉树线索化的实

8、质线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，会构造线索二叉树构造线索二叉树(中序中序),会在中序线索化树上找给定结点的前驱和后继第六章第六章 树树4、掌握树、森林与二叉树之间的转换、掌握树、森林与二叉树之间的转换5、掌握树和森林遍历规则及与二叉树各遍历规则间的对应关掌握树和森林遍历规则及与二叉树各遍历规则间的对应关系，给定遍历序列会画对应的二叉树、树或森林系，给定遍历序列会画对应的二叉树、树或森林6、理解带权路径长度的概念，会构造理解带权路径长度的概念，会构造Huffman树并求树并求Huffman编码及带权路径长度编码及带权路径长度上页上页 下页下页节节末页末页结束结

9、束u掌握图的分类及（强）连通分量、生成树或生成森林等概念，掌握图的分类及（强）连通分量、生成树或生成森林等概念，掌握图掌握图邻接矩阵、邻接表邻接矩阵、邻接表存储结构定义存储结构定义u掌握图的深度优先遍历和广度优先遍历的规则及算法实现，能掌握图的深度优先遍历和广度优先遍历的规则及算法实现，能写出遍历序列、画写出遍历序列、画对应的生成树或生成森林对应的生成树或生成森林(邻接点顺序小到大邻接点顺序小到大)u掌握图的各类应用背景掌握图的各类应用背景,理解过程，理解过程，会手工求解：会手工求解：u最小生成树最小生成树:Prim算法算法(逐点逐点)Kruskal算法算法(逐边逐边)u拓扑排序拓扑排序:选入

10、度为选入度为0的顶点输出的顶点输出(若有多个则全部入栈后从栈若有多个则全部入栈后从栈顶开始输出顶开始输出)并并删除删除,至至最后看图空，否则有回路最后看图空，否则有回路u关键路径关键路径:初始化初始化ve为为0,找入度找入度0的顶点的顶点,更新其后继更新其后继ve,删除删除并入栈并入栈,至图空或有回路至图空或有回路;初始化初始化vl为工期为工期,按拓扑逆序求各顶按拓扑逆序求各顶点点vl.最后最后ee(a,b)=ve(a),el(a,b)=vl(b)-w(a,b)u最短路径最短路径:Dijstra算法算法(Dv+finalv+Pvw);画表画表 Floyd算法算法(Dkij+Pijk)；写矩阵；

11、写矩阵 第七章第七章 图图上页上页 下页下页节节末页末页结束结束第九章第九章 查找查找l掌握有序表的折半查找算法掌握有序表的折半查找算法,明白折半查找在有序顺序明白折半查找在有序顺序表存储结构上方有效表存储结构上方有效,理解折半查找理解折半查找ASL是对数阶的。是对数阶的。理解判定树模拟折半查找的原理理解判定树模拟折半查找的原理(比较时生成根比较时生成根,到左侧到左侧区间比较时递归生成左子树区间比较时递归生成左子树,右侧比较生成右子树右侧比较生成右子树,故判故判定树中左子树结点均小于根定树中左子树结点均小于根,右子树中结点均大于根右子树中结点均大于根),给定元素个数时能画出折半查找过程的判定树

12、给定元素个数时能画出折半查找过程的判定树l对二叉排序树（二叉查找树）掌握其定义、对二叉排序树（二叉查找树）掌握其定义、查找算法查找算法和构造和构造过程，知道其平均查找长度；掌握平衡二叉树过程，知道其平均查找长度；掌握平衡二叉树及及B-树的定义、构造、插入、删除等操作，树的定义、构造、插入、删除等操作，B+树定义树定义l理解理解Hash函数与普通查找方法的区别，函数与普通查找方法的区别，给定给定Hash函函数和处理冲突的方法能构造出具体的数和处理冲突的方法能构造出具体的Hash表，并会求表，并会求ASL，知道影响知道影响Hash表查找性能的因素表查找性能的因素上页上页 下页下页节节末页末页结束结束第十章第十章 排序排序l明确直接插入排序、折半插入排序、明确直接插入排序、折半插入排序、希尔希尔排序排序、冒泡排序、冒泡排序、快速排序快速排序、选择排序、选择排序、堆排序堆排序、2-路归并排序、基数排序的排序路归并排序、基数排序的排序原理与过程原理与过程,课件算法会实现课件算法会实现,综合比较各综合比较各种排序方法的最好、最坏、平均时间复杂种排序方法的最好、最坏、平均时间复杂度及空间复杂度、稳定性，明确各自适用度及空间复杂度、稳定性，明确各自适用场合场合