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

1、题型说明,填空题：29=18 选择题：310=30 应用题：74=28 算法设计题:122=24,算法设计题,范围： 线性表相关操作 栈和队列的基本操作与应用 二叉树的创建、销毁、先中后序遍历,求树深、结点数、叶结点数、复制、左右子树互换、查找、删除(参考例程)。树的简单操作 图的存储结构与图的遍历 顺序查找、折半查找、二叉排序树查找 排序 从课件中出现的算法看起 资料:课件+例程+作业+教材+样题 +推荐习题,第一章 绪论 小结,理解数据结构、逻辑结构(分类)、存储结构的概念；给出数据元素及关系能给出所属逻辑结构；理解关系的顺序映像与链式映像，前者形成一个数组，后者形成一个链表，掌握各自优缺

2、点,会根据操作性质确定采用顺序存储结构或链式存储结构 掌握抽象数据类型的概念、表示和实现方法(有理数) 理解算法的特性(“有穷”性、确定性、可行性、输入、输出性)，区分算法与程序 理解时间复杂度的概念，会计算语句频度和时间复杂度。理解时间复杂度反映的是算法运行时间随问题规模的增长率T(n)=O(f(n),第二章 线性表,1.理解线性结构的定义,掌握线性表与栈和队列的联系区别 2.掌握顺序表与单链表存储结构定义及各自优缺点 3.熟练掌握顺序表与单链表各操作的实现 4. 双向链表、双向循环链表的插入、删除,1.掌握ADT栈、队列及线性表的区别联系和各自特点,2.熟练掌握顺序栈和链栈的存储定义、适用

3、场合、基本操作及其实现，特别注意栈满栈空的判断和处理,3.熟练掌握循环队列和链队列的定义、适用场合、基本操作及其实现，特别注意队满和队空的判断和处理,4.熟练掌握栈的用法(进制转换/括号匹配/行编辑)，理解栈在递归算法执行过程中的作用,第三章 栈和队列 小结,1. 了解串的概念和基本操作的定义,2. 理解掌握在串的各种存储结构,第四章,3. 理解串匹配的KMP算法，会手工计算给定模式串的next函数值和改进的nextval函数值,理解next和nextval的求取算法,第五章数组,理解数组属于线性结构，采用顺序存储 对称矩阵、上/下三角矩阵、对角矩阵、三对角矩阵的压缩存储与下标计算 熟悉稀疏矩

4、阵的三元组顺序存储表示，理解矩阵的快速转置算法 理解广义表的定义,掌握树与二叉树结构特性与递归定义,明确二叉树是有序树,掌握二叉树n0n1n2与e及指针个数的关系和满二叉树、完全二叉树的性质,掌握二叉树各存储结构 会递归实现二叉树创建、销毁、先中后序遍历和输出、求树深、结点数、叶结点数、复制、左右子树互换、查找、删除。理解树和森林的深度和叶子树,3. 理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，会构造线索二叉树(中序),会在中序线索化树上找给定结点的前驱和后继,第六章 树,4、掌握树、森林与二叉树之间的转换 5、掌握树和森林遍历规则及与二叉树各遍历规则间的对应关

5、系，给定遍历序列会画对应的二叉树、树或森林 6、理解带权路径长度的概念，会构造Huffman树并求Huffman编码及带权路径长度,掌握图的分类及（强）连通分量、生成树或生成森林等概念，掌握图邻接矩阵、邻接表存储结构定义 掌握图的深度优先遍历和广度优先遍历的规则及算法实现，能写出遍历序列、画对应的生成树或生成森林(邻接点顺序小到大) 掌握图的各类应用背景,理解过程，会手工求解： 最小生成树:Prim算法(逐点) Kruskal算法(逐边) 拓扑排序:选入度为0的顶点输出(若有多个则全部入栈后从栈顶开始输出)并删除, 至最后看图空，否则有回路 关键路径:初始化ve为0,找入度0的顶点,更新其后继

6、ve, 删除并入栈,至图空或有回路;初始化vl为工期,按拓扑逆序求各顶点vl.最后ee(a,b)=ve(a),el(a,b)=vl(b)-w(a,b) 最短路径:Dijstra算法(Dv+finalv+Pvw);画表 Floyd算法(Dkij+Pijk)；写矩阵,第七章 图,第九章 查找,掌握有序表的折半查找算法,明白折半查找在有序顺序表存储结构上方有效,理解折半查找ASL是对数阶的。理解判定树模拟折半查找的原理(比较时生成根,到左侧区间比较时递归生成左子树,右侧比较生成右子树,故判定树中左子树结点均小于根,右子树中结点均大于根),给定元素个数时能画出折半查找过程的判定树 对二叉排序树（二叉查找树）掌握其定义、查找算法和构造过程，知道其平均查找长度；掌握平衡二叉树及B-树的定义、构造、插入、删除等操作，B+树定义 理解Hash函数与普通查找方法的区别，给定Hash函数和处理冲突的方法能构造出具体的Hash表，并会求ASL，知道影响Hash表查找性能的因素,第十章 排序,明确直接插入排序、折半