复习提纲数据结构2011.ppt

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