《数据结构与数据库》复习.ppt

《《数据结构与数据库》复习.ppt》由会员分享，可在线阅读，更多相关《《数据结构与数据库》复习.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构复习复习（仅供复习参考，考试范围不受此课件的限制）（仅供复习参考，考试范围不受此课件的限制）数据结构 70分参考题型：n n填空,选择,判断：n n解答题：n n算法题：对算法的要求：对算法的要求：根据教学知识点的难易和重要性，将相关的算法理解和应用分三个层次进行要求：层次1)能阅读和理解算法，能结合具体数据给出算法执行结果；层次2)能写出算法的伪代码；层次3)能灵活运用算法，对实际问题进行算法设计。第一章 序论数据结构的知识点：1.1.数据的逻辑结构数据的逻辑结构2.2.数据的存储结构数据的存储结构3.3.对数据的运算（运算的定义和运算的实现）对数据的运算（运算的定义和运算的

2、实现）4.4.抽象数据类型的概念和表示方法抽象数据类型的概念和表示方法第一章第一章 序论序论算法的知识点：n n算法的定义算法的定义n n算法的特性算法的特性n n算法的时间分析和空间分析方法算法的时间分析和空间分析方法第二章 线性表5个主要知识点：1.1.线性表的定义线性表的定义2.2.线性表的存储表示线性表的存储表示-顺序表，链表顺序表，链表3.3.线性表的运算在不同存储结构上的实现线性表的运算在不同存储结构上的实现4.4.有序表的操作有序表的操作5.5.线性表的应用线性表的应用第二章 线性表线性表顺序存储结构的特点：1.1.逻辑上相邻的元素在物理上也相邻；逻辑上相邻的元素在物理上也相邻；

3、2.2.不需要为表示元素之间的逻辑相邻关系开辟附不需要为表示元素之间的逻辑相邻关系开辟附加空间；加空间；3.3.可以随机访问数据元素；可以随机访问数据元素；4.4.插入和删除元素时需要大量移动元素。插入和删除元素时需要大量移动元素。第二章 线性表线性表链式存储结构的特点：1.1.逻辑上相邻的元素在物理上不一定相邻；逻辑上相邻的元素在物理上不一定相邻；2.2.需要为表示元素之间的逻辑相邻关系开辟附需要为表示元素之间的逻辑相邻关系开辟附加空间：指针域；加空间：指针域；3.3.无法随机访问数据元素；无法随机访问数据元素；4.4.插入和删除元素时不需要大量移动元素，只插入和删除元素时不需要大量移动元素

4、，只要修改相关结点的指针值即可。要修改相关结点的指针值即可。第二章 线性表几种常用的线性链表:1.1.单链表单链表2.2.循环单链表循环单链表(既可以用头指针引导既可以用头指针引导,又可以用又可以用尾指针引导尾指针引导)3.3.双向链表双向链表4.4.双向循环链表双向循环链表第二章 线性表 带头结点的链表和不带头结点的链表在操作上有差别.判表空条件:带头结点时带头结点时不带头结点时不带头结点时单链表单链表head-next=NULLhead-next=NULLhead=NULLhead=NULL循环单链表循环单链表head=head-nexthead=head-nexthead=NULLhea

5、d=NULL第三章 栈和队列n n栈和队列都是插入和删除操作受到限制的特栈和队列都是插入和删除操作受到限制的特栈和队列都是插入和删除操作受到限制的特栈和队列都是插入和删除操作受到限制的特殊线性表；殊线性表；殊线性表；殊线性表；n n栈的特点：栈的特点：栈的特点：栈的特点：后进先出（后进先出（后进先出（后进先出（LIFOLIFO）n n队列的特点：先进先出（队列的特点：先进先出（队列的特点：先进先出（队列的特点：先进先出（FIFOFIFO）第三章 栈和队列栈的操作：栈的操作：栈的操作：栈的操作：n n顺序栈：顺序表操作的特例顺序栈：顺序表操作的特例顺序栈：顺序表操作的特例顺序栈：顺序表操作的特例

6、n n链栈：单链表操作的特例链栈：单链表操作的特例链栈：单链表操作的特例链栈：单链表操作的特例第三章 栈和队列队列的操作：队列的操作：n n链队列：带头结点、头指针和尾指针的单链链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。表，入队端在表尾，出队端在表头。n n循环链队列：可以只用一个尾指针循环链队列：可以只用一个尾指针n n用定长数组作为队列的存储结构时，一般采用定长数组作为队列的存储结构时，一般采用循环队列的形式用循环队列的形式-循环队列循环队列。第三章 栈和队列队列的操作：队列的操作：n n链队列：带头结点、头指针和尾指针的单链链队列：带头结点、头指针和尾指针的单

7、链表，入队端在表尾，出队端在表头。表，入队端在表尾，出队端在表头。n n循环链队列：可以只用一个尾指针循环链队列：可以只用一个尾指针n n用定长数组作为队列的存储结构时，一般采用定长数组作为队列的存储结构时，一般采用用循环队列循环队列循环队列循环队列的形式的形式第三章 栈和队列循环队列：数组：数组：Q1.maxsize-1Q1.maxsize-1frontfront指向对头元素指向对头元素rearrear指向队尾元素的下一个指向队尾元素的下一个队列的最大容量：队列的最大容量：maxsize-1maxsize-106543217frontreara5a1a2a3a4第三章 栈和队列循环队列的计算

8、公式Q0.maxsize-1：入队：入队：rear=(rear+1)mod maxsizerear=(rear+1)mod maxsize出队：出队：front=(front+1)mod maxsizefront=(front+1)mod maxsize队空条件：队空条件：front=rearfront=rear队满条件：队满条件：front=(rear+1)mod maxsizefront=(rear+1)mod maxsize队列长度：队列长度：(rear(rear front+maxsize)mod maxsize front+maxsize)mod maxsize第三章 栈和队列循环队

9、列的计算公式Q1.maxsize：入队：入队：rear=rear mod maxsize+1rear=rear mod maxsize+1出队：出队：front=front mod maxsize+1front=front mod maxsize+1队空条件：队空条件：front=rearfront=rear队满条件：队满条件：front=rear mod maxsize+1front=rear mod maxsize+1队列长度：队列长度：(rear(rear front+maxsize)mod maxsize front+maxsize)mod maxsize第4章 数组数组知识点：n n

10、多维数组多维数组行优先行优先和和列优先列优先的存储方式；的存储方式；n n数组元素地址的计算方法；数组元素地址的计算方法；n n特殊矩阵的压缩存储方法以及下标变换算公特殊矩阵的压缩存储方法以及下标变换算公式的推导；式的推导；n n稀疏矩阵的压缩存储技术稀疏矩阵的压缩存储技术-三元组表、十三元组表、十字链表。字链表。第6章 树和二叉树知识点(1)：n n树和二叉树的定义树和二叉树的定义n n二叉树的（二叉树的（5 5个）性质个）性质n n完全二叉树的特点完全二叉树的特点n n二叉树的存储结构，主要掌握二叉链表二叉树的存储结构，主要掌握二叉链表n n二叉树的遍历算法以及二叉树常用运算二叉树的遍历算

11、法以及二叉树常用运算第6章 树和二叉树知识点（2）：n n表达式的二叉树表示表达式的二叉树表示n n树的存储结构树的存储结构n n树、森林与二叉树的相互转换树、森林与二叉树的相互转换n n树和森林的遍历树和森林的遍历n n哈夫曼树的定义和构造，哈夫曼编码方法哈夫曼树的定义和构造，哈夫曼编码方法第7章 图知识点(1)：图的概念：图的概念：n n有向图，无向图有向图，无向图n n路径，回路（环），简单路径，简单环路径，回路（环），简单路径，简单环n n无向连通图、连通分量无向连通图、连通分量n n有向强连通图、强连通分量有向强连通图、强连通分量n n完全图完全图第7章 图知识点（2）：n n生成树

12、、生成森林生成树、生成森林n n熟练掌握图的存储结构邻接矩阵和邻接熟练掌握图的存储结构邻接矩阵和邻接表，他们的特点和操作表，他们的特点和操作n n熟练掌握图的熟练掌握图的DFSDFS遍历和遍历和BFSBFS遍历的概念和遍历的概念和实现算法实现算法第7章 图知识点（3）：n n最小生成树的概念和最小生成树的概念和primprim、KlusclaKluscla算法思想算法思想n n拓扑序列的概念和拓扑排序算法拓扑序列的概念和拓扑排序算法n n最短路径的概念和最短路径的概念和DijkstraDijkstra算法算法n n关键路径的概念和关键路径的算法思想关键路径的概念和关键路径的算法思想第8章 查找

13、知识点(1)：n n平均查找长度平均查找长度ASLASL的定义和计算方法的定义和计算方法n n顺序查找的特点、算法和顺序查找的特点、算法和ASLASL（等概情况下（等概情况下查找成功的查找成功的ASLASL（n+1)/2n+1)/2）n n折半查找的特点、算法和折半查找的特点、算法和ASLASL（折半查找判（折半查找判定树的定义和使用）定树的定义和使用）第8章 查找知识点(2)：n n索引顺序查找的特点、查找方法和索引顺序查找的特点、查找方法和ASLASLn n二叉排序树的定义、查找、插入、删除二叉排序树的定义、查找、插入、删除n n哈希表的概念、哈希函数的构造、装填因子哈希表的概念、哈希函数

14、的构造、装填因子对查找效率的影响、解决冲突的方法（线性对查找效率的影响、解决冲突的方法（线性探测、二次探测和拉链法）、冲突和堆积的探测、二次探测和拉链法）、冲突和堆积的不同、哈希表的构造和不同、哈希表的构造和ASLASL计算计算第9章 排序知识点：知识点：n n直接插入排序直接插入排序n n希尔排序希尔排序n n冒泡排序冒泡排序n n快速排序快速排序n n简单选择排序简单选择排序n n堆排序堆排序n n归并排序归并排序排序算法思想排序算法思想（会写过程）（会写过程）稳定性稳定性时间复杂度时间复杂度特点特点最好、最坏情况分析最好、最坏情况分析数据库系统n n基本概念：基本概念：DBDB，DBSD

15、BS，DBMSDBMS，概念模型，数，概念模型，数据模型，实体，联系（据模型，实体，联系（1:11:1，1:n1:n，n:m)n:m)，数据，数据独立性，独立性，ERER图，数据模型的三要素图，数据模型的三要素n n关键字：候选码，主码，外部码，主属性关键字：候选码，主码，外部码，主属性n n数据库系统模式结构（三级模式，两级映射）数据库系统模式结构（三级模式，两级映射）n n用数据库系统来管理数据的特点用数据库系统来管理数据的特点数据库系统n n关系模型的数据结构关系模型的数据结构n n关系的定义、关系的性质关系的定义、关系的性质n n关系的完整性规则关系的完整性规则n n关系模式的概念关系

16、模式的概念n n关系代数运算（关系代数运算（9 9种，其中原子运算有种，其中原子运算有5 5种）种）n n灵活运用关系代数运算实现复杂的查询灵活运用关系代数运算实现复杂的查询数据库系统n n函数依赖的概念函数依赖的概念n n完全函数依赖、部分函数依赖、传递函数依赖完全函数依赖、部分函数依赖、传递函数依赖n n1NF1NF、2NF2NF、3NF3NF定义定义n n会通过分解关系模式达到高级范式会通过分解关系模式达到高级范式n n会将会将E-RE-R图转换成关系模式图转换成关系模式n n数据库的设计（四个步骤）数据库的设计（四个步骤）数据库系统n n会用会用SQLSQL的的SelectSelect语句实现查询语句实现查询单表查询、多表连接查询、嵌套查询、用集函单表查询、多表连接查询、嵌套查询、用集函数查询、分组查询、结果排序数查询、分组查询、结果排序n n会会CreateCreate，DeleteDelete，InsertInsert，UpdateUpdate