数据结构期末复习

《数据结构期末复习》由会员分享，可在线阅读，更多相关《数据结构期末复习（5页珍藏版）》请在金锄头文库上搜索。

1、大专计算机类数 据 结 构 期 末 复 习中央电大 ? 徐孝凯1? 复习提要1?1?绪论 1?1?1? 重点掌握的内容 ( 1) 数据结构的二元组表示, 对应的图形表示, 序 偶和边之间的对应关系。 ( 2) 集合结构、 线性结构、 树结构和图结构的特 点。 ( 3) 抽象数据类型的定义和表示方法。 ( 4) 一维和二维数组中元素按下标和按地址的访 问方式以及相互转换, 元素地址和数组地址的计算, 元素占用存储空间大小和数组占用存储空间大小的 计算。 ( 5) 普通函数重载和操作符函数重载的含义、 定 义格式和调用格式。 ( 6) 函数定义中值参数和引用参数的说明格式及 作用, 函数被调用执行

2、时对传送来的实际参数的影 响。 ( 7) 算法的时间复杂度和空间复杂度的概念, 计 算方法, 数量级表示。 ( 8) 一个简单算法的最好、 最差和平均这三种情 况的时间复杂度的计算。 1?1?2? 一般了解的内容 对于本章的其余内容均要求一般了解。1?2? 线性表 1?2?1? 重点掌握的内容 ( 1) 线性表的定义和抽象数据类型的描述, 线性 表中每一种操作的功能, 对应的函数名、 返回值类型 和参数表中每个参数的作用。( 2) 线性表的顺序存储结构的类型定义, 即 List 类型的定义和每个域的定义及作用。 ( 3) 线性表的每一种运算在顺序存储结构上实现 的算法及相应的时间复杂度。 (

3、4) 链接存储的概念, 线性表的单链接和双链接 存储的结构, 向单链表中一个结点之后插入新结点或 从单链表中删除一个结点的后继结点的指针链接过 程。 ( 5) 单链表中结点的结构, 每个域的定义及作用, 即LNode类型的定义及结构。 ( 6) 带表头附加结点的链表、 循环链表、 双向链表 的结构特点。 ( 7) 线性表的每一种运算在单链表上实现的算法 及相应的时间复杂度。 ( 8) 在顺序存储或链接存储的线性表上实现指定 功能的算法的分析和设计。 1?2?2? 一般了解的内容 对于本章的其余内容要求一般了解。1?3? 稀疏矩阵和广义表 1?3?1? 重点掌握的内容 ( 1) 稀疏矩阵的定义和

4、三元组线性表表示。 ( 2) 稀疏矩阵的顺序存储、 带行指针向量的链接 存储、 十字链接存储的类型定义, 在每一种存储中非 零元素结点的结构。 ( 3) 稀疏矩阵转置运算和算法描述。 ( 4) 广义表的定义和表示, 广义表长度和深度的 计算。 ( 5) 广义表的链接存储结构中结点类型的定义,15?大专计算机类? 2004?2? 当代电大?|分别求广义表长度和深度的递归算法, 它们对应的时 间复杂度。 1?3?2? 一般掌握的内容 两个稀疏矩阵做加法的过程和算法描述。 1?3?3? 一般了解的内容 对于本章的其余内容要求一般了解。1?4?栈和队列 1?4?1? 重点掌握的内容 ( 1) 栈的定义

5、和抽象数据类型的描述, 栈中每一 种操作的功能, 对应的函数名、 返回值类型和参数表 中每个参数的作用。 ( 2) 栈的顺序存储结构的类型定义, 即 Stack 类 型的定义和每个域的定义及作用。 ( 3) 栈的每一种运算在顺序存储结构上实现的算 法及相应的时间复杂度。 ( 4) 栈的每一种运算在链接存储结构上实现的算 法及相应的时间复杂度。 ( 5) 算术表达式的中缀表示和后缀表示, 相互转 换的规则, 后缀表达式求值的方法。 ( 6) 队列的定义和抽象数据类型的描述, 队列中 每一种操作的功能, 对应的函数名、 返回值类型和参 数表中每个参数的作用。 (7) 队列的顺序存储结构的类型定义,

6、 即 Queue 类型的定义和每个域的定义及作用。 ( 8) 队列的每一种运算在顺序存储结构上实现的 算法及相应的时间复杂度。 ( 9) 利用栈和队列解决简单问题的算法分析和设 计。 1?4?2? 一般掌握的内容( 1) 后缀表达式求值的算法, 把中缀表达式转换 为后缀表达式的算法。 ( 2) 求解阶乘问题和迷宫问题的方法和算法。 ( 3) 队列的链接存储结构以及实现每一种队列运 算的算法和相应的时间复杂度。1?5? 树和二叉树 1?5?1? 重点掌握的内容 ( 1) 树和二叉树的定义, 对于一棵具体树和二叉 树的二元组表示及广义表表示。 ( 2) 树和二叉树的概念, 如结点的度、 树的度、

7、树 的层数、 树的深度等。 ( 3) 树和二叉树的性质, 如已知树或二叉树的深 度 h 可求出相应的最多结点数, 已知结点数 n 可求出 对应树或二叉树的最大和最小高度。 ( 4) 二叉树中结点的编号规则和对应的顺序存储 结构。 ( 5) 二叉树的链接存储结构及存储结点的类型定义, 即 BT reeNode 类型的定义和每个域的定义及作 用。 ( 6) 二叉树的先序、 中序、 后序遍历的递归过程和 递归算法, 中序遍历的非递归算法, 按层遍历的过程 和算法, 每种算法的时间复杂度。 ( 7) 普通树的链接存储结构, GT reeNode 类型的 定义和每个域的定义及作用。 ( 8) 普通树的先

8、根、 后根和按层遍历的过程及算 法。 ( 9) 在链接存储的二叉树上实现指定功能的算法 分析和设计。 1?5?2? 一般掌握的内容 对于本章的其余内容要求一般掌握。1?6? 二叉树的应用 1?6?1? 重点掌握的内容 ( 1) 二叉搜索树的定义和性质。 ( 2) 二叉搜索树查找的递归算法和非递归算法, 相应的时间复杂度, 查找一个元素的查找长度, 即从 树根结点到该结点的路径上的结点数。 ( 3) 二叉搜索树插入的递归算法和非递归算法, 相应的时间复杂度, 根据一组数据生成一棵二叉搜索 树的过程。 ( 4) 堆的定义和顺序存储结构, 小根堆和大根堆 的异同。 ( 5) 向堆中插入元素的过程、

9、算法描述及时间复 杂度。 ( 6) 从堆中删除元素的过程、 算法描述及时间复 杂度。 ( 7) 霍夫曼树的定义, 树的带权路径长度的计算, 根据若干个叶子结点的权构造霍夫曼树的过程。 1?6?2? 一般了解的内容 本章的其余内容要求一般了解。1?7? 图 1?7?1? 重点掌握的内容 ( 1) 图的顶点集和边集的表示。 ( 2) 图的一些概念的含义, 如顶点、 边、 度、 完全 图、 子图、 路径、 路径长度、 连通图、 权、 网等。 ( 3) 图的邻接矩阵、 邻接表和边集数组三种存储 结构及相应的空间复杂度。 ( 4) 存 储图 使 用 的 vexlist、 adjmatrix、 adjli

10、st、 edgenode、 edgeset、 edge 等类型的定义及用途。 ( 5) 图的深度优先和广度优先搜索遍历的过程。 ( 6) 对分别用邻接矩阵和用邻接表表示的图进行 深度优先搜索遍历的过程、 算法描述以及相应的时间 复杂度。 ( 7) 对分别用邻接矩阵和用邻接表表示的图进行16|?当代电大? 2004?2? 大专计算机类广度优先搜索遍历的过程、 算法描述以及相应的时间 复杂度。 ( 8) 图的生成树、 生成树的权、 最小生成树等的定 义。 ( 9) 根据普里姆算法求图的最小生成树的过程和算法描述。 ( 10) 根据克鲁斯卡尔算法求图的最小生成树的 过程和算法描述。 ( 11) 图的

11、拓扑序列和拓扑排序的概念, 求图的拓扑序列的方法, 对用邻接表表示的图进行拓扑排序的 过程和算法。 1?7?2? 一般掌握的内容 对本章的其余内容均要求一般掌握。它包括建立图的邻接矩阵、 邻接表、 边集数组算法, 建立图的逆 邻接表和十字邻接表等内容。1?8? 查找1?8?1? 重点掌握的内容 ( 1) 在一维数组上进行顺序查找的过程、 算法、 平 均查找长度和时间复杂度。 ( 2) 在一维数组上进行二分查找的过程、 递归和非递归算法、 平均查找长度和时间复杂度, 二分查找 一个给定值元素的查找长度( 即查找路径上的元素 数) , 二分查找对应的判定树的性质。 ( 3) 索引存储的概念, 索引

12、表的存储结构和索引项的存储结构, 索引查找一个元素的过程、 平均查找 长度和时间复杂度。 ( 4) 散列存储的概念, 散列函数、 散列表、 冲突、 同 义词、 装填因子等术语的含义。 ( 5) 利用除留余数法建立散列函数求元素散列地址的方法。 ( 6) 利用开放定址法中的线性探查法处理冲突进 行散列存储和查找的过程, 利用链接法处理冲突进行 散列存储和查找的过程。( 7) 根据除留余数法构造散列函数, 采用线性探 查法或链接法处理冲突, 把一组数据散列存储到散列 表中, 计算出一个给定值元素的查找长度和查找所有 元素的平均查找长度。( 8) B 树中每个结点的结构, 树根结点或非树根 结点中关

13、键字的个数范围和子树的个数范围, B树 的结构特性, 从 B 树上查找一个给定值元素的过程。 1?8?2? 一般掌握的内容( 1) 索引查找和分块查找算法。 ( 2) B 树查找算法。 ( 3) 向 B 树中插入元素的过程。 1?8?3? 一般了解的内容本章的其余内容要求一般了解。1?9? 排序 1?9?1? 重点掌握的内容 ( 1) 直接插入、 直接选择和冒泡排序的方法, 排序 过程及时间复杂度。 ( 2) 在堆排序中建立初始堆的过程和利用堆排序 的过程, 对一个分支结点进行筛运算的过程、 算法及 时间复杂度, 整个堆排序的算法描述及时间复杂度。 ( 3) 快速排序的方法, 对一组数据的排序

14、过程, 对 应的二叉搜索树, 快速排序过程中划分的层数和递归 排序区间的个数。 ( 4) 递归排序的递归算法, 它在平均情况下的时间 和空间复杂度, 在最坏情况下的时间和空间复杂度。 ( 5) 二路归并排序的方法和对数据的排序过程, 每趟排序前、 后的有序表长度, 二路归并排序的趟数、 时间复杂度和空间复杂度。 1?9?2? 一般掌握的内容 ( 1) 每一种排序方法的稳定性。 ( 2) 直接插入排序和直接选择排序的算法。 1?9?3? 一般了解的内容 ( 1) 二路归并排序过程中涉及的每个算法。 ( 2) 冒泡排序算法。2? 综合练习2?1?选择题 ( 1) 在一个单链表 HL 中, 若要向表

15、头插入一个 由指针 P 指向的结点, 则执行( ? ) 。 ?A?HL= p; p- next= HL; ?B?p- next= HL; HL= p; ?C?P- next= HL; P= HL; ?D?p- next= HL- next; HL- next= p; ( 2) 在一个顺序队列中, 队首指针指向队首元素 的( ? ? ) 位置。 ?A? 前一个 ?B? 后一个 ?C? 当前 ?D? 后两个 ( 3) 从二叉搜索树中查找一个元素时, 其时间复 杂度大致为( ? ? ) 。 ?A?O( n) ?B?O( 1) ?C?O( 1og2n) ?D?O( n2) ( 4) 由权值分别为 3、

16、 8、 6、 2、 5 的叶子结点生成一 棵霍夫曼树, 它的带权路径长度为( ? ) 。 ?A?24 ?B?48 ?C?7217?大专计算机类? 2004?2? 当代电大?|?D?532?2? 填空题 ( 1) 一个算法的时间复杂度为( 3n2+ 2n1og2n+ 4n- 7) / ( 5n) , 其数量级表示为。 ( 2) 在以HL 为表头指针的带表头附加结点的单 链表和循 环单 链表 中, 链表 为空的 条件 分别 为 和。 (3) 一个广义表中的元素分为元素和 元素两类。 ( 4) 从一个链栈中删除一个结点时, 需要把栈顶 结点的域的值赋给。 ( 5) 在进行函数调用时, 需要把每个实参的值和 调用后的传送给被调用的函数中。 ( 6) 对于一棵具有 n 个结点的二叉树, 若一个结 点的编号为 i( 1 i n) , 则它的左孩子结点的编号为 , 右孩子结点的编号为, 双亲结点 的编号为。 ( 7) 在一棵高度为 5 的理想平衡树中, 最少含有 个结点, 最多含有个结点。 ( 8) 在一个堆的顺序存储中, 若一个元素的下标 为i( 0 i n- 1)