数据结构复习大纲.pdf

《数据结构复习大纲.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构—杨剑数据结构复习大纲第一章绪论1.数据结构的基本概念和术语1.1数据、数据元素、数据项、数据结构等基本概念1.2数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系1.3数据结构的两大逻辑结构和四种常用的存储表示方法2.算法的描述和分析2.1算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念2.2算法描述和算法分析的方法，对于一般算法能分析出时间复杂度第二章线性表1.线性表的逻辑结构1.1线性表的逻辑结构特征2.线性表的顺序存储结构2.1顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系2.2顺序

2、表上的插入、删除操作及其平均时间性能分析3.线性表的链式存储结构3.1链表如何表示线性表中元素之间的逻辑关系3.2链表中头指针和头结点的使用3.3单链表、双（向）链表、循环链表链接方式上的区别3.4单链表上实现的建表、查找、插入和删除4.顺序表和链表的比较4.1顺序表和链表的主要优缺点4.2针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能第三章栈和队列1.栈的逻辑结构、存储结构及其相关算法1.1栈的逻辑结构特点，栈与线性表的异同1.2顺序栈和链栈上实现的进栈、退栈等基本算法1.3栈的“上溢”和“

3、下溢”的概念及其判别条件第1页共5页数据结构—杨剑2.队列的逻辑结构、存储结构及其相关算法2.1队列的逻辑结构特点，队列与线性表的异同2.2顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法2.3队列的“上溢”和“下溢”的概念及其判别条件2.4使用数组实现的循环队列取代普通的顺序队列的原因2.5循环队列中对边界条件的处理方法3.栈和队列的应用3.1栈和队列的特点，什么样的情况下能够使用栈或队列3.2表达式求值的算法思想，及栈变化情况。第四章串、数组和广义表1.串1.1串的有关概念及基本运算1.2串与线性表的关系2.多维数组2.

4、1多维数组的逻辑结构特征2.2多维数组的顺序存储结构及地址计算方式2.3数组是一种随机存取结构的原因2.4矩阵的压缩存储（对称矩阵、三角矩阵、稀疏矩阵）的表示方式和对应的地址计算方式。3.广义表的概念3.1广义表的有关概念及其与线性表的关系3.2求给定的广义表的表头、表尾运算第五章树和二叉树1.树的概念1.1树的逻辑结构特征1.2树的不同表示方法1.3树的常用术语及含义2.二叉树2.1二叉树的递归定义及树与二叉树的差别2.2二叉树的性质，了解相应的证明方法3.二叉树的遍历3.1二叉树的三种遍历算法，理解其执行过程3.2确定三种遍历所得到的

5、相应的结点访问序列第2页共5页数据结构—杨剑4.线索二叉树4.1二叉树线索化的目的及实质4.2在中序线索树中查找给定的中序前趋和中序后继的方法5.树和森林5.1树和森林与二叉树之间的转换方法5.2树的各种存储结构及其特点5.3树的两种遍历方法6.Huffman树及其应用6.1最优二叉树和最优前缀码的概念及特点6.2Huffman算法的思想6.3根据给定的叶结点及其权值构造出相应的最优二叉树6.4根据最优二叉树构造对应的Huffman编码第六章图1.图的概念1.1图的逻辑结构特征1.2图的常用术语及含义2.图的存储结构2.1邻接矩阵和邻接表

6、这两种存储结构的特点及适用范围2.2根据应用问题的特点和要求选择合适的存储结构3.图的遍历3.1连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法3.2确定两种遍历所得到的顶点访问序列及两种生成树4.生成树和最小生成树4.1生成树和最小生成树的概念4.2对遍历给定的图，画出深度优先和广度优先生成树或生成森林4.3Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点4.4要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树5.图的应用5.1对于给定的有向图，根据Dijkstra算法画出求单源最短路径的

7、过程示意图5.2拓扑排序的基本思想和步骤5.3对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列5.4关键路径的基本思想和步骤5.5对给定的有向图，写出求关键路径的过程第3页共5页数据结构—杨剑第七章查找1.线性表的查找1.1顺序查找、二分查找的基本思想、算法实现和查找效率分析1.2顺序查找中哨兵的作用1.3二分查找对存储结构及关键字的要求2.树的查找3.1二叉排序树和平衡二叉树的定义和特点3.2二叉排序树的插入、删除、建树和查找算法3.3建立一棵二叉查找树的过程实质上是对输入实例的排序过程，输入实例对所建立的二叉查找树形态的影

8、响3.4平衡二叉树的插入时平失衡的调整的基本思想4.哈希表4.1哈希表、哈希函数、哈希地址和装填因子等有关概念4.2哈希函数的选取原则及产生冲突的原因4.3采用线性探测法、平方探测法和链地址法