数据结构期末复习提要2015.docVIP

《数据结构》期末复习提要2015 下面按照教材中各章次序给出每章的具体复习要求，以便指导同学们更好地进行期末复习。 第一章 绪论 重点掌握的内容： 1. 数据结构的概念。 2. 集合结构、线性结构、树结构和图结构的特点。 3. 抽象数据类型的定义和表示方法。 4. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。 5. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。 对于本章的其余内容均作一般掌握。 第二章 线性表 重点掌握的内容： 1. 线性表的定义和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。 2. 线性表的顺序存储结构的类型定义，即SeqList类型的定义和每个域的定义及作用。 3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。 4. 链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。 5. 单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。 6. 带表头附加结点的链表、循环链表、双向链表的结构特点。 7. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。 8. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。 9. 稀疏矩阵的定义和三元组线性表表示。 10. 广义表的定义和表示，广义表长度和深度的计算。 对于本章的其余内容均作一般了解。 第三章 栈和队列 重点掌握的内容： 1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。 2. 栈的顺序存储结构的类型定义，即SeqStack类型的定义和每个域的定义及作用。 3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。 4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。 5. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。 6. 队列的顺序存储结构的类型定义，即SeqQueue类型的定义和每个域的定义及作用。 7. 队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。 8. 利用栈和队列解决简单问题的算法分析和设计。 9. 求解阶乘问题的方法和算法。 一般掌握的内容： 1. 后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。 2. 队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。 第四章 串 重点掌握的内容： 1、串的基本概念和基本运算。 2、串的顺序存储结构以及定长串的基本运算。 3、串的简单的模式匹配以及KMP模式匹配算法。 一般掌握的内容： 1、串的链式存储结构表示。 2、串在文本编辑中处理方法。 第五章 数组和广义表 重点掌握的内容： 1、数组的基本概念，数组的存储结构特点以及数组元素存储地址的计算； 2、特殊矩阵的压缩存储技术，如对称矩阵、三角矩阵、对角矩阵可利用一维数组实现特殊矩阵的压缩存储； 3、稀疏矩阵的压缩存储方法：三元组表和十字链表。矩阵压缩存储中的矩阵运算的实现； 4、广义表的基本定义和概念，理解广义表的递归性； 一般掌握的内容： 广义表的存储特点和基本操作算法。 第六章 树和二叉树 重点掌握的内容： 1. 树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。 2. 树和二叉树的概念，如结点的度、树的度、树的层数、树的深度等。 3. 树和二叉树的性质，如已知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。 4. 二叉树中结点的编号规则和对应的顺序存储结构。(满二叉树和完全二叉树) 5. 二叉树的链接存储结构及存储结点的类型定义，即BinTreeNode类型的定义和每个域的定义及作用。 6. 二叉树的先序、中序、后序遍历的递归过程和递归算法。 7. 在链接存储的二叉树上实现指定功能的算法分析和设计。 8. 二叉树的先序、中序、后序线索化方法。 9. 根据若干个叶子结点的权构造哈夫曼树的过程及带权外部路径长度的计算。 对于本章的其余内容均作一般掌握。 第七章 图 重点掌握的内容： 1. 图的顶点集和边集的表示。