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

题型说明算法设计题第一章绪论小结第二章线性表1.掌握ADT栈、队列及线性表的区别联系和各自特点1.了解串的概念和基本操作的定义第五章数组掌握树与二叉树结构特性与递归定义,明确二叉树是有序树,掌握二叉树n0n1n2与e及指针个数的关系和满二叉树、完全二叉树的性质,掌握二叉树各存储结构
会递归实现二叉树创建、销毁、先中后序遍历和输出、求树深、结点数、叶结点数、复制、左右子树互换、查找、删除。理解树和森林的深度和叶子树掌握图的分类及（强）连通分量、生成树或生成森林等概念，掌握图邻接矩阵、邻接表存储结构定义
掌握图的深度优先遍历和广度优先遍历的规则及算法实现，能写出遍历序列、画对应的生成树或生成森林(邻接点顺序小到大)
掌握图的各类应用背景,理解过程，会手工求解：
最小生成树:Prim算法(逐点)Kruskal算法(逐边)
拓扑排序:选入度为0的顶点输出(若有多个则全部入栈后从栈顶开始输出)并删除,至最后看图空，否则有回路
关键路径:初始化ve为0,找入度0的顶点,更新其后继ve,删除并入栈,至图空或有回路;初始化vl为工期,按拓扑逆序求各顶点vl.最后ee(a,b)=ve(a),el(a,b)=vl(b)-w(a,b)
最短路径:Dijstra算法(D[v]+final[v]+P[v][w]);画表 Floyd算法(Dk[i][j]+P[i][j][k])；写矩阵第九章查找第十章排序