数据结构期末复习提要2015

《数据结构期末复习提要2015》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》期末复习提要2015下面按照教材中各章次序给出每章的具体复习要求，以便指导同学们更好地进行期末复习第一章绪论重点掌握的内容：1.数据结构的概念。2.集合结构、线性结构、树结构和阁结构的特点。3.抽象数据类型的定义和表示方法。4.算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。5.—个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。对于本章的其余内容均作一般掌握。第二章线性表重点掌握的内容：1.线性表的定义和抽象数据类型的描述，线性表中每一种操作的功能，对应的阑数名、返回值类型和参数表屮每个参数的作用。2.线性表的顺序存储结构的

2、类型定义，即SeqList类型的定义和每个域的定义及作用。3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。5.单链表屮结点的结构，每个域的定义及作用，即LNode类型的定义及结构。6.带表头附加结点的链表、循环链表、双向链表的结构特点。7.线性表的每一种运算在单链表上实现的算法及相应的吋间复杂度。8.在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。9.稀疏矩阵的定义和三元组线性表表示。1

3、0.广义表的定义和表示，广义表长度和深度的计算。对于本章的其余内容均作一般了解。第三章栈和队列重点掌握的內容：1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返冋值类型和参数表中每个参数的作用。2.栈的顺序存储结构的类型定义，即SeqStack类型的定义和每个域的定义及作用。3.栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4.栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。5.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。6.队列的顺序存储结构的

4、类型定义，即SeqQueue类型的定义和每个域的定义及作用。7.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。8.利用栈和队列解决简单问题的算法分析和设计。9.求解阶乘问题的方法和算法。一般掌握的内容：1.后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。2.队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。第四章串重点掌握的内容：1、串的基本概念和基本运算。2、串的顺序存储结构以及定长串的基本运算。3、串的简单的模戎匹配以及KMP模式匹配算法。一般掌握的內容：1、串的链式存储结构表示。2、串在文本编辑中处理方法。

5、第五章数组和广义表重点掌握的內容：1、数组的基本概念，数组的存储结构特点以及数组元素存储地址的计算；2、特殊矩阵的压缩存储技术，如对称矩阵、三角矩阵、对角矩阵可利用一维数组实现特殊矩阵的压缩存储；3、稀疏矩阵的压缩存储方法：三元组表和十字链表。矩阵压缩存储中的矩阵运算的实现；4、广义表的基本定义和概念，理解广义表的递归性；―般掌握的内容：广义表的存储特点和基本操作算法。第六章树和二叉树重点掌握的内容：1.树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。2.树和二叉树的概念，如结点的度、树的度、树的层数、树的深度等。3.树和二叉树的性质，如

6、己知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小髙度。4.二叉树中结点的编号规则和对应的顺序存储结构。（满二叉树和完全二叉树）5.二叉树的链接存储结构及存储结点的类型定义，即BinTreeNode类型的定义和每个域的定义及作用。6.二叉树的先序、屮序、后序遍历的递归过程和递归算法。7.在链接存储的二叉树上实现指定功能的算法分析和设计。8.二叉树的先序、中序、后序线索化方法。9.根据若千个叶子结点的权构造哈夫曼树的过程及带权外部路径长度的计算。对于本章的其余内咨均作一般掌握。策七章图重点掌握的内容：1.图的顶点集和边

7、集的表示。2.图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。3.图的邻接矩阵、邻接表两种存储结构。1.图的深度优先和广度优先搜索遍历的过程。2.图的生成树、生成树的权、最小生成树等的定义。3.根据普里姆算法求图的最小生成树的过程和算法描述。4.根据克鲁斯卡尔算法求阁的最小生成树的过程和算法描述。5.图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法。6.图的最短路径的求解过程（辿氏算法和Floyd算法）。7.图的关键路径的求解过程。对本章的其余内容均作一般掌握。它包拈建立图的邻接矩阵、邻接表、边集数组算法，建立图的逆邻

8、接表和十字邻接表等内容。第八章查找重点掌握的内容：1.在一维数组上