电大数据结构复习大纲.docVIP

数据结构 第 1 页 共 30 页 数据结构与算法复习大纲 题型及分值分布 第一部份 复习大纲 第一章 绪论 1. 数据结构的基本概念和术语 1.1 数据、 数据元素、 数据项、 数据结构等基本概念 1.2 数据结构的逻辑结构、 存储结构及数据运算的含义及其相互关系 1.3 数据结构的两大逻辑结构和四种常用的存储表示方法 2. 算法的描述和分析 2.1 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念 2.2 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度 第二章 线性表 1. 线性表的逻辑结构 1.1 线性表的逻辑结构特征 2. 线性表的顺序存储结构 2.1 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系 2.2 顺序表上的 插入 、删除 操作及其平均时间性能分析 3. 线性表的链式存储结构 3.1 链表如何表示线性表中元素之间的逻辑关系 3.2 链表中头指针和头结点的使用 3.3 单链表 、双（向）链表 、循环链表链接方式上的区别 3.4 单链表上实现的建表 、查找 、插入 和删除 4. 顺序表和链表的比较 数据结构 第 2 页 共 30 页 4.1 顺序表和链表的主要优缺点 4.2 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能 取得较优的时空性能 第三章 栈和队列 1.栈的逻辑结构、存储结构及其相关算法 1.1 栈的逻辑结构特点，栈与线性表的异同 1.2 顺序栈和链栈上实现的进栈、退栈等基本算法 1.3 栈的“上溢”和“下溢”的概念及其判别条件 2. 队列的逻辑结构、存储结构及其相关算法 2.1 队列 的逻辑结构特点，队列与 线性表 的异同 2.2 顺序队列 （主要是 循环队列 ）和 链队列 上实现的 入队 、 出队 等基本算法 2.3 队列的“上溢”和“下溢”的概念及其判别条件 2.4 使用数组实现的循环队列取代普通的顺序队列的原因 2.5 循环队列中对边界条件的处理方法 3. 栈和队列的应用 3.1 栈和队列的特点，什么样的情况下能够使用栈或队列 3.2 表达式求值的算法思想，及栈变化情况。 第四章 串、数组和广义表 1.串 1.1 串的有关概念及基本运算 1.2 串与线性表的关系 2.多维数组 2.1 多维数组的逻辑结构特征 2.2 多维数组的顺序存储结构及地址计算方式 2.3 数组是一种随机存取结构的原因 2.4 矩阵的压缩存储（对称矩阵、三角矩阵、稀疏矩阵）的表示方式和对应的地址计算方 式。 3. 广义表的概念 3.1 广义表的有关概念及其与线性表的关系 3.2 求给定的广义表的表头、表尾运算 数据结构 第 3 页 共 30 页 第五章 树和二叉树 1.树的概念 1.1 树的逻辑结构特征 1.2 树的不同表示方法 1.3 树的常用术语及含义 2. 二叉树 2.1 二叉树的递归定义及树与二叉树的差别 2.2 二叉树的性质，了解相应的证明方法 3. 二叉树的遍历 3.1 二叉树的三种遍历算法，理解其执行过程 3.2 确定三种遍历所得到的相应的结点访问序列 4. 线索二叉树 4.1 二叉树线索化的目的及实质 4.2 在中序线索树中查找给定的中序前趋和中序后继的方法 5. 树和森林 5.1 树和森林与二叉树之间的转换方法 5.2 树的各种存储结构及其特点 5.3 树的两种遍历方法 6. Huffman 树 及其应用 6.1 最优二叉树和最优前缀码的概念及特点 6.2 Huffman 算法的思想 6.3 根据给定的叶结点及其权值构造出相应的最优二叉树 6.4 根据最优二叉树构造对应的 Huffman 编码 第六章 图 1.图的概念 1.1 图的逻辑结构特征 1.2 图的常用术语及含义 2. 图的存储结构 2.1 邻接矩阵和邻接表这两种存储结构的特点及适用范围 2.2 根据应用问题的特点和要求选择合适的存储结构 3. 图的遍历 3.1 连通图及非连通图的深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站两种遍历算法 3.2 确定两种遍历所得到的顶点访问序列及两种生成树 4.生成树和最小生成树 4.1 生成树和最小生成树的概念 数据结构 第 4 页 共 30 页 4.2 对遍历给定的图，画出深度优先和广度优先生成树或生成森林 4.3 Prim 和 Kruskal 算法的基本思想、时间性能及这两种算法各自的特点 4.4 要求对给定的连通图，根据 Prim 和 Kruskal 算法构造出最小生成树 5. 图的应用 5.1