数据结构期末复习.ppt

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

1、数据结构期末复习2008.6第一章数据结构基本概念数据、数据元素、数据对象、数据类型数据结构的含义什么是数据结构逻辑结构、存储结构、算法逻辑结构的线性和非线性表示算法五个准则算法时间复杂度的基本概念和分析常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、……、k次方阶O(nk)、指数阶O(2n)第二章线性表的特性数据元素一致的数据类型、数据元素的位置取决于序号、逻辑关系线性线性表的运算插入、删除、查找线性表的存储结构顺序表、链表第二章（2）顺序表与链表的异同点顺序表的特点逻辑位置

2、相邻，其物理位置也相邻优缺点顺序表的插入和删除运算及时间复杂度分析第二章(3)链表的特点结点之间的相对位置由链表中的指针域指示优缺点带头结点的单链表存储表示单链表的建立、插入、删除运算第三章栈的概念栈的定义栈的基本运算后进先出算法特点栈与递归队列的概念队列的定义队列的基本运算先进先出算法特点循环队列的存储表示第四章、第五章串的基本概念什么是串空串、空白串、子串数组一维、二维数组的存储表示、地址运算矩阵表示、特殊矩阵对称矩阵、上三角矩阵、稀疏矩阵及压缩存储第六章树的定义和特点（一对多的逻辑关系）结点、度、叶子、层次、深度、森林二叉树五个性质三种遍历方法

3、（先序、中序、后序）基本操作（统计二叉树结点数、叶子数、深度）森林如何转变为二叉树第六章(2)先序序列和中序序列已知的情况下，如何确定一棵二叉树后序序列和中序序列已知的情况下，如何确定一棵二叉树哈夫曼树什么是哈夫曼树如何构造哈夫曼树第七章图的基本概念有向图、无向图、网络、完全图、顶点、边、弧、度、路径、路径长度、回路、简单路径、简单回路、连通图、强联通图、连通分量图的存储表示邻接矩阵与关联矩阵邻接表图的遍历DFS/BFS第七章(2)最小生成树如何将图转换为最小生成树拓扑排序如何得到一个AOV网的拓扑序列AOE网什么是AOE网关键活动、关键路径的求解第

4、九章查找的基本概念查找表、关键字、静态查找与动态查找的区别顺序查找与折半查找动态查找二叉排序树第十章排序的基本概念什么是排序、如何区分稳定和不稳定直接插入排序冒泡排序简单选择排序