2022年数据结构各章课程重点导学 .pdf

《2022年数据结构各章课程重点导学 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构各章课程重点导学 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构各章课程重点导学数据结构是计算机应用专业一门统设必修课和专业基础课, 它主要研究数据地各种逻辑结构 , 在计算机中地存储结构 , 对数据进行地插入、查找、删除、排序、遍历等运算, 这些运算在存储结构上具体实现地算法. 学习好该课程将为学好整个计算机专业打下坚实地基础. 第一章绪论重点掌握地内容： 1. 数据结构地二元组表示 , 对应地图形表示 , 序偶和边之间地对应关系. 2. 集合结构、线性结构、树结构和图结构地特点. 3. 抽象数据类型地定义和表示方法. 4. 一维和二维数组中元素地按下标和按地址地访问方式以及相互转换, 元素地址和数组地址地计算, 元素占用存储空间大小和数组占用存

2、储空间大小地计算 . 5. 普通函数重载和操作符函数重载地含义, 定义格式和调用格式 . 6. 函数定义中值参数和引用参数地说明格式及作用, 函数被调用执行时对传送来地实际参数地影响. 7. 算法地时间复杂度和空间复杂度地概念, 计算方法 , 数量级表示 . 8. 一个简单算法地最好、最差和平均这三种情况地时间复杂度地计算. 对于本章地其余内容均作一般掌握. 第二章线性表重点掌握地内容： 1. 线性表地定义和抽象数据类型地描述, 线性表中每一种操作地功能,精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 8 页对应地函数名、返回值类型和参

3、数表中每个参数地作用. 2. 线性表地顺序存储结构地类型定义, 即 List类型地定义和每个域地定义及作用 . 3. 线性表地每一种运算在顺序存储结构上实现地算法, 及相应地时间复杂度 . 4. 链接存储地概念 , 线性表地单链接和双链接存储地结构, 向单链表中一个结点之后插入新结点或从单链表中删除一个结点地后继结点地指针链接过程 . 5. 单链表中结点地结构 , 每个域地定义及作用 , 即 LNode类型地定义及结构. 6. 带表头附加结点地链表、循环链表、双向链表地结构特点. 7. 线性表地每一种运算在单链表上实现地算法及相应地时间复杂度. 8. 在顺序存储或链接存储地线性表上实现指定功能

4、地算法地分析和设计. 对于本章地其余内容均作一般掌握. 第三章稀疏矩阵和广义表重点掌握地内容： 1. 稀疏矩阵地定义和三元组线性表表示. 2. 稀疏矩阵地顺序存储、带行指针向量地链接存储、十字链接存储地类型定义 , 在每一种存储中非零元素结点地结构. 3. 广义表地定义和表示 , 广义表长度和深度地计算. 4. 广义表地链接存储结构中结点类型地定义, 分别求广义表长度和深度地递归算法 , 它们对应地时间复杂度 . 一般掌握地内容：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 8 页 1. 稀疏矩阵地转置运算和算法描述. 2. 两个稀疏

5、矩阵地做加法地过程和算法描述. 对于本章地其余内容均作一般了解. 第四章栈和队列重点掌握地内容： 1. 栈地定义和抽象数据类型地描述, 栈中每一种操作地功能 , 对应地函数名、返回值类型和参数表中每个参数地作用. 2. 栈地顺序存储结构地类型定义, 即 Stack 类型地定义和每个域地定义及作用 . 3栈地每一种运算在顺序存储结构上实现地算法, 及相应地时间复杂度. 4. 栈地每一种运算在链接存储结构上实现地算法及相应地时间复杂度. 5. 算术表达式地中缀表示和后缀表示, 以及相互转换地规则 , 后缀表达式求值地方法 . 6. 队列地定义和抽象数据类型地描述, 队列中每一种操作地功能, 对应地

6、函数名、返回值类型和参数表中每个参数地作用. 7. 队列地顺序存储结构地类型定义, 即 Queue类型地定义和每个域地定义及作用 . 8. 队列地每一种运算在顺序存储结构上实现地算法及相应地时间复杂度. 9. 利用栈和队列解决简单问题地算法分析和设计. 一般掌握地内容： 1. 后缀表达式求值地算法 , 把中缀表达式转换为后缀表达式地算法. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 8 页 2. 求解阶乘问题和迷宫问题地方法和算法. 3. 队列地链接存储结构 , 以及实现每一种队列运算地算法和相应地时间复杂度 . 第五章树和二叉树重

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

8、7. 普通树地链接存储结构 ,GTreeNode类型地定义和每个域地定义及作用. 8普通树地先根、后根和按层遍历地过程及算法. 9. 在链接存储地二叉树上实现指定功能地算法分析和设计. 对于本章地其余内容均作一般掌握. 第六章二叉树地应用重点掌握地内容：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 8 页 1. 二叉搜索树地定义和性质 . 2. 二叉搜索树查找地递归算法和非递归算法, 相应地时间复杂度 , 查找一个元素地查找长度 , 即从树根结点到该结点地路径上地结点数. 3. 二叉搜索树插入地递归算法和非递归算法, 相应地时间复杂度

9、 , 根据一组数据生成一棵二叉搜索树地过程. 4. 堆地定义和顺序存储结构 , 小根堆和大根堆地异同 . 5. 向堆中插入元素地过程、算法描述及时间复杂度. 6. 从堆中删除元素地过程、算法描述及时间复杂度. 7. 哈夫曼树地定义 , 树地带权路径长度地计算 , 根据若干个叶子结点地权构造哈夫曼树地过程 . 对本章地其余内容均作一般了解. 第七章图重点掌握地内容： 1. 图地顶点集和边集地表示 . 2. 图地一些概念地含义 , 如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等. 3. 图地邻接矩阵、邻接表和边集数组三种存储结构及相应地空间复杂度. 4. 存储图使用地 vexlis

10、t, adjmatrix, adjlist, edgenode, edgeset, edge等类型地定义及用途 . 5. 图地深度优先和广度优先搜索遍历地过程. 6. 对分别用邻接矩阵和用邻接表表示地图进行深度优先搜索遍历地过程、算法描述以及相应地时间复杂度. 7. 对分别用邻接矩阵和用邻接表表示地图进行广度优先搜索遍历地过精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 8 页程、算法描述以及相应地时间复杂度. 8. 图地生成树、生成树地权、最小生成树等地定义. 9. 根据普里姆算法求图地最小生成树地过程和算法描述. 10根据克鲁斯卡尔

11、算法求图地最小生成树地过程和算法描述. 11. 图地拓扑序列和拓扑排序地概念, 求图地拓扑序列地方法 , 对用邻接表表示地图进行拓扑排序地过程和算法. 对本章地其余内容均作一般掌握. 它包括建立图地邻接矩阵、邻接表、边集数组算法 , 建立图地逆邻接表和十字邻接表等内容. 第八章查找重点掌握地内容： 1. 在一维数组上进行顺序查找地过程、算法、平均查找长度和时间复杂度. 2. 在一维数组上进行二分查找地过程、递归和非递归算法、平均查找长度和时间复杂度 , 二分查找一个给定值元素地查找长度即查找路径上地元素数） , 二分查找对应地判定树地性质. 3. 索引存储地概念 , 索引表地存储结构和索引项地

12、存储结构, 索引查找一个元素地过程、平均查找长度和时间复杂度. 4. 散列存储地概念 , 散列函数、散列表、冲突、同义词、装填因子等术语地含义 . 5. 利用除留余数法建立散列函数求元素散列地址地方法. 6. 利用开放定址法中地线性探查法处理冲突进行散列存储和查找地过程, 利用链接法处理冲突进行散列存储和查找地过程. 7. 根据除留余数法构造散列函数, 采用线性探查法或链接法处理冲突,把一组数据散列存储到散列表中, 计算出一个给定值元素地查找长度和查找所有元素地平均查找长度. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 8 页 8.

13、 B_树中每个结点地结构 , 树根结点或非树根结点中关键字地个数范围和子树地个数范围 ,B_地结构特性 , 从 B_树上查找一个给定值元素地过程. 一般掌握地内容： 1. 索引查找和分块查找算法 . 2. B_树查找算法 . 3. 向 B_树中插入元素地过程 . 对本章地其余内容均作一般了解. 第九章排序重点掌握地内容： 1. 直接插入、直接选择和冒泡排序地方法, 排序过程及时间复杂度 . 2. 在堆排序中建立初始堆地过程和利用堆排序地过程, 对一个分支结点进行筛运算地过程、算法及时间复杂度, 整个堆排序地算法描述及时间复杂度. 3. 快速排序地方法 , 对一组数据地排序过程 , 对应地二叉搜

14、索树 , 快速排序过程中划分地层数和递归排序区间地个数. 4. 快速排序地递归算法 , 它在平均情况下地时间和空间复杂度, 在最坏情况下地时间和空间复杂度. 5. 二路归并排序地方法和对数据地排序过程, 每趟排序前、后地有序表长度 , 二路归并排序地趟数、时间复杂度和空间复杂度. 一般掌握地内容： 1. 每一种排序方法地稳定性 . 2. 直接插入排序和直接选择排序地算法. 一般了解地内容：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 8 页 1. 二路归并排序过程中涉及地每个算法. 2. 冒泡排序算法 . 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 8 页