复习提纲数据结构.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,优秀精品课件文档资料,算法与数据结构,2011-2012,试题，题目类型：,一、单选,二、填空,三、判断题,四、应用题,五、程序设计题,本次课重点：,1.,数据结构的基本概念；,2.,数据的逻辑结构、存储结构以 及二者之间的关系；,3.,算法及特性。,1.4,算法及算法分析,本次课重点：,1.,估算算法时间复杂度的基本方法；,2.,大,记号的意义；,3.,问题规模、基本语句；,4.,线性表的定义；,5.,线性表的逻辑特征；,6.,顺序表的存储要点及存储特点；,7.,顺序表的随机存取特性；,本次课重点：,1.,顺序表类的构造函数；（了解）,2.,顺序表插入、删除、查找操作的实现；,3.,顺序表插入、删除、查找操作的时间性能。,本次课重点：,1.,双链表的存储结构；,2.,双链表的插入、删除操作；,3.,静态链表的存储结构；（了解）,本次课重点：,1.,栈的定义及操作特性；,2.,顺序栈及实现；,3.,链栈及实现；,4.,顺序栈和链栈的比较；,5.,队列的定义及操作特性；,6.,循环队列及实现；,7.,顺序队列的假溢出现象。,本次课重点：,1.,循环队列及实现；,2.,链队列及实现；,本次课重点：,1.,递归的定义；（课本上没有，讲课时有讲）,2.,树的定义；,3.,树的基本术语；,4.,树的遍历操作；,本次课重点：,1.,树的双亲表示法；（了解）,2.,树的孩子链表表示法；（了解）,3.,树的双亲孩子表示法；（了解）,4.,树的孩子兄弟表示法。,本次课重点：,1.,二叉树的基本术语和定义,2.,二叉树的性质（课本上的,5,个性质，,不仅要掌握，而且要会灵活运用）,3.,二叉树的各种遍历操作,本次课重点：,*,已知一棵二叉树的前序序列和中序序列，如何确定这棵二叉树（要求会操作，不是会讲理论）,1.,二叉树的顺序存储结构。,2.,二叉链表存储结构。（熟练掌握）,3.,二叉树遍历算法的递归实现。（熟练掌握）,4.,二叉树前序遍历的非递归算法。（了解）,本次课重点：,1.,二叉树的二叉链表存储结构,2.,二叉树中序线索链表的建立,本次课重点：,1.,在中序线索链表上查找某个结点的后继。（了解）,2.,树转换为二叉树。（熟练掌握,),3.,森林转换为二叉树。（熟练掌握,),4.,二叉树转换为树（或森林）。（熟练掌握,),本次课重点：,1.,哈夫曼树的构造方法。（熟练掌握,),2.,哈夫曼编码与解码方法。,本次课重点：,1.,图的定义和若干基本术语。（熟练掌握,),2.,图的深度优先遍历。（熟练掌握）,本次课重点：,1.,图的广度优先遍历。（熟练掌握）,2.,图的邻接矩阵存储结构。（熟练掌握,),3.,邻接矩阵存储类的构造函数。（熟练掌握,),本次课重点：,1.,图的邻接表存储结构。（熟练掌握,),2.,邻接表存储类的构造函数。（熟练掌握,),3.,基于邻接表的深度优先遍历算法。（了解）,4.,基于邻接表的广度优先遍历算法。（了解）,5.,无向图的连通性。,上次课重点：,Prim,算法的求解思想、过程及使用的最有利条件（稠密图）。（熟练掌握,),Prim,算法的伪代码描述。（了解）,Kruskal,算法的求解思想、过程,及使用的最有利条件（稀疏图）,。（熟练掌握,),4.Kruskal,算法的伪代码描述。（了解）,5.Dijkstra,算法的求解思想、过程。（熟练掌握,),6.Dijkstra,算法的伪代码描述。（了解）,本次课重点：,1.,拓扑序列的定义。（掌握）,2.,拓扑排序算法的求解思想及过程。（掌握,),3.,排序的基本术语，如内部排序、外部排序等。,4.,直接插入排序，起泡排序，快速排序算法思想，针对具体实例的操作过程，每趟的排序结果。性能分析的结果。,本次课重点：,简单选择排序，堆排序，归并排序算法思想，针对具体实例的操作过程，每趟的排序结果。性能分析的结果。,