数据结构期末复习提要63

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

1、数据结构期末复习提要632、业精于勤，荒于嬉；行成于思，毁于随——韩愈数据结构期末复习提要(适用范围：普通专科、成人专科、开放专科)数据结构是中央电大计算机应用专业一门统设必修课和专业基础课，它主要研究数据的各种逻辑结构，在计算机中的存储结构，对数据进行的插入、查找、删除、排序、遍历等运算，这些运算在存储结构上具体实现的算法学习好该课程将为学好整个计算机专业打下坚实的基础第一部分各章复习要求下面按照主教材中各章次序给出每章的具体复习要求，以便指导同学们更好地进行期末复习第一章绪论重点掌握的内容：1.数据结构

2、的二元组表示，对应的图形表示，序偶和边之间的对应关系2.集合结构、线性结构、树结构和图结构的特点3.抽象数据类型的定义和表示方法4.一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算5.普通函数重载和操作符函数重载的含义，定义格式和调用格式6.函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响7.算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示8.一个简单算法的最好、最差和平均这三种

3、情况的时间复杂度的计算对于本章的其余内容均作一般掌握第二章线性表重点掌握的内容：1.线性表的定义和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用2.线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程5.单链表中结点的结构，每个域的定义及作用

4、，即LNode类型的定义及结构6.带表头附加结点的链表、循环链表、双向链表的结构特点7.线性表的每一种运算在单链表上实现的算法及相应的时间复杂度8.在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计对于本章的其余内容均作一般掌握第三章稀疏矩阵和广义表重点掌握的内容：1.稀疏矩阵的定义和三元组线性表表示2.稀疏矩阵的顺序存储、带行指针向量的链接存储、十字链接存储的类型定义，在每一种存储中非零元素结点的结构3.广义表的定义和表示，广义表长度和深度的计算4.广义表的链接存储结构中结点类型的定义，分别求广

5、义表长度和深度的递归算法，它们对应的时间复杂度一般掌握的内容：1.稀疏矩阵的转置运算和算法描述2.两个稀疏矩阵的做加法的过程和算法描述对于本章的其余内容均作一般了解第四章栈和队列重点掌握的内容：1.栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用2.栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度4.栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度5.算术表达式

6、的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法6.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用7.队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用8.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度9.利用栈和队列解决简单问题的算法分析和设计一般掌握的内容：1.后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法2.求解阶乘问题和迷宫问题的方法和算法3.队列的链接存储结构，以及实现每一种队列运

7、算的算法和相应的时间复杂度第五章树和二叉树重点掌握的内容：1.树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示2.树和二叉树的概念，如结点的度、树的度、树的层数、树的深度等3.树和二叉树的性质，如已知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度4.二叉树中结点的编号规则和对应的顺序存储结构5.二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用6.二叉树的先序、中序、后序遍历的递归过程和递归算法，中序遍历的

8、非递归算法，按层遍历的过程和算法，每种算法的时间复杂度7.普通树的链接存储结构，GTreeNode类型的定义和每个域的定义及作用8．普通树的先根、后根和按层遍历的过程及算法9.在链接存储的二叉树上实现指定功能的算法分析和设计对于本章的其余内容均作一般掌握第六章二叉树的应用重点掌握的内容：1.二叉搜索树的定义和性质2.二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结