第9章_总复习

《第9章_总复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、武汉理工大学数据结构与算法WuhanUniversityofTechnology数据结构与算法总总复复习习授课教师：肖攸安联系电话：86581632电子邮件：youan@21cn.com教学大纲：ACM&IEEE2007电子信息工程专业用电子信息工程专业用2009年8月2009年8月授课教师：肖攸安授课教师：肖攸安数据结构与算法绪论什么是数据、数据元素、数据项、数据结构、数据类型、抽象数据类型PartIPartI内容内容回顾回顾数据结构和算法的研究范畴；数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系；数据结构的二元组表示，对应的图形表示，

2、电子信息工程专业用序偶和边之间的对应关系；2009年8月集合结构、线性结构、树结构和图结构的特授课教师：肖攸安点；授课教师：肖攸安绪论线性表算法的定义、算法的特性和五大要素、算法线性表的概念；线性表的逻辑结构特性；的评价、算法的时间和空间代价；线性表的几种存储实现方式：空间复杂度度量；时间复杂度度量；时间复顺序存储；杂度的渐进表示法（数量级表示）；渐进的链接存储（游标存储）；空间复杂度。在使用上述存储结构的线性表上实现指定操计算语句频度和估算算法时间复杂度方法；作功能（包括线性表的各种基本运算，如：算法的描述：用伪C语言/C/VB

3、；搜索、插入、删除、查找、归并、排序等）给定算法的最好、最差和平均这三种情况的的算法的设计和分析。时间复杂度的计算。授课教师：肖攸安授课教师：肖攸安线性表线性表线性表的顺序存储结构的类型定义和实现。单链表的定义、构造、插入与删除等算法；应用顺序表作为集合的简单操作；双向链表的特点、定义及相关算法的实现；链表与顺序表一样，是一种实现级结构。循环链表的特点和类型定义，以及用循环链指针基本操作；表解决问题的方法；向链表中一个结点之后（前）插入新结点或从链表中删除一个结点的后继结点的指针链静态链表的定义、特点及相关操作的实现；接过程。单

4、链表的结构、特点，带表头结点的单链表授课教师：肖攸安授课教师：肖攸安堆栈与队列堆栈与队列栈的定义、特性和栈的抽象数据类型的描述队列的定义、特性；栈的顺序表示、链式表示以及相应操作和运队列的顺序表示、链式表示以及相应操作和算的实现和分析，注意栈空和栈满的条件。运算的实现。利用栈解决简单问题的算法分析和设计。利用队列解决简单问题的算法分析和设计，栈的应用：火车车厢重排问题、数制转换问重点：离散事件仿真。题、表达式求值问题和括号匹配问题；循环队列的定义、特性及其抽象数据类型定算术表达式的前缀、中缀和后缀表示法，以义，循环队列的插入与删除算

5、法。及相互转换的规则。循环队列的特征：特别是循环队列中队头与三种表达式求值的算法，重点：堆栈的使用队尾指针的变化情况。授课教师：肖攸安授课教师：肖攸安算法策略树递归与分而治之的概念：算法设计思想，应用条树和森林的概念，相关定义和术语、特别是件，基本步骤。树的递归定义；递归向非递归的转换.树的性质及其应用；利用分而治之和递归策略解决问题的分治法和回二叉树的定义和性质、顺序表示和链式表示溯法；（二叉链表表示法）；其它策略：分支定界、穷举、贪婪等二叉树中结点的编号规则和对应的顺序存储分而治之与递归策略的典型应用：伪币问题、棋盘覆盖问

6、题；结构；迷宫问题；普通树的先根、后根和逐层遍历的过程及其梵塔问题、九连环问题；算法。快速排序、归并排序；授课教师：肖攸安授课教师：肖攸安树树二叉树的遍历：中序遍历、前序遍历、后序堆的定义，堆的建立、最小堆和最大堆的异遍历和层次序遍历；同，向堆中插入元素、删除元素的过程，堆算术表达式树，以及与前缀、中缀和后缀表的向上和向下调整等操作；达式的对应；最优二叉树的定义和实现，树的带权路径长分而治之策略的状态空间描述：递归树；度的计算，根据若干个叶子结点的权构造最梵塔问题、快速排序过程的递归树。优二叉树的过程。二叉排序树的定义和性质，建

7、立方法。☆Huffman编码译码过程。授课教师：肖攸安授课教师：肖攸安图排序与查找图的定义；直接顺序查找、二分查找算法；插入类排序：直接插入排序、折半插入排序图的概念；链表插入排序、希尔排序。交换类排序：起泡排序、快速排序；图的表示方法；选择类排序：直接选择排序、堆排序归并类排序：二路归并排序、自然归并排序图的遍历。线性时间排序：计数排序、箱子排序、链式基数排序授课教师：肖攸安授课教师：肖攸安排序与查找排序与查找排序的基本概念、分类、工作过程和性能快速排序：分析方法；对一组数据的排序过程及对应的递归树；排序过程中划分的层数

8、和递归排序区间的个数；每一种排序算法的设计思想、算法描述、排序过程中涉及的相关算法。排序过程、稳定性及三