复习提纲 数据结构2011.ppt

* 算法与数据结构2011-2012试题，题目类型： 一、单选 二、填空 三、判断题 四、应用题 五、程序设计题 本次课重点： 1. 数据结构的基本概念； 2. 数据的逻辑结构、存储结构以 及二者之间的关系； 3. 算法及特性。 1.4 算法及算法分析 本次课重点： 1. 估算算法时间复杂度的基本方法； 2. 大Ο记号的意义； 3.问题规模、基本语句； 4. 线性表的定义； 5. 线性表的逻辑特征； 6. 顺序表的存储要点及存储特点； 7. 顺序表的随机存取特性； 本次课重点： 1. 顺序表类的构造函数；（了解） 2. 顺序表插入、删除、查找操作的实现； 3.顺序表插入、删除、查找操作的时间性能。 本次课重点： 1. 单链表的存储要点及存储特点； 2. 单链表的顺序存取特性； 3. 单链表的插入、删除操作； 4. 单链表的插入、删除操作操作的时间性能。 本次课重点： 1. 单链表类的构造函数和析构函数（了解）； 2. 顺序表和单链表的比较； 3. 循环链表的存储结构； 4. 循环链表的操作。 本次课重点： 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算法的伪代码描述。（了解） *