数据结构与数据库复习学习教案.pptx

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

1、数据结构数据结构(sh j ji u)与数据库与数据库 复习复习第一页，共31页。数据结构 70分参考题型：填空,选择,判断：解答(jid)题：算法题：第1页/共30页第二页，共31页。对算法的要求：根据教学知识对算法的要求：根据教学知识点的难易和重要性，将相关的点的难易和重要性，将相关的算法理解和应用分三个层次进算法理解和应用分三个层次进行要求：行要求：层次层次1)能阅读和理解算法，能能阅读和理解算法，能结合具体数据给出算法执行结结合具体数据给出算法执行结果；果；层次层次2)能写出算法的伪代码；能写出算法的伪代码；层次层次3)能灵活运用算法，对实能灵活运用算法，对实际问题际问题(wnt)进行

2、算法设计。进行算法设计。第2页/共30页第三页，共31页。第一章 序论(x ln)数据结构(jigu)的知识点：数据的逻辑结构(jigu)数据的存储结构(jigu)对数据的运算（运算的定义和运算的实现）抽象数据类型的概念和表示方法第3页/共30页第四页，共31页。第一章 序论(x ln)算法的知识点：算法的定义(dngy)算法的特性算法的时间分析和空间分析方法第4页/共30页第五页，共31页。第二章 线性表5个主要知识点：线性表的定义线性表的存储(cn ch)表示-顺序表，链表线性表的运算在不同存储(cn ch)结构上的实现有序表的操作线性表的应用第5页/共30页第六页，共31页。第二章 线性

3、表线性表顺序存储结构的特点：逻辑上相邻的元素在物理上也相邻；不需要为表示元素之间的逻辑相邻关系开辟附加空间；可以随机访问数据元素；插入(ch r)和删除元素时需要大量移动元素。第6页/共30页第七页，共31页。第二章 线性表线性表链式存储结构的特点：逻辑上相邻的元素在物理上不一定相邻；需要为表示元素之间的逻辑相邻关系开辟附加空间(kngjin)：指针域；无法随机访问数据元素；插入和删除元素时不需要大量移动元素，只要修改相关结点的指针值即可。第7页/共30页第八页，共31页。第二章 线性表几种常用的线性链表:单链表循环(xnhun)单链表(既可以用头指针引导,又可以用尾指针引导)双向链表双向循环

4、(xnhun)链表第8页/共30页第九页，共31页。第二章 线性表 带头结点的链表和不带头结点 的 链 表 在 操 作 上 有 差 别(chbi).判表空条件:带头结点时带头结点时不带头结点时不带头结点时单链表单链表head-next=NULLhead-next=NULLhead=NULLhead=NULL循环单链表循环单链表head=head-nexthead=head-nexthead=NULLhead=NULL第9页/共30页第十页，共31页。第三章 栈和队列(duli)栈和队列栈和队列栈和队列栈和队列(duli)(duli)都是插入和删除操作受都是插入和删除操作受都是插入和删除操作受都

5、是插入和删除操作受到限制的特殊线性表；到限制的特殊线性表；到限制的特殊线性表；到限制的特殊线性表；栈的特点：栈的特点：栈的特点：栈的特点：后进先出（后进先出（后进先出（后进先出（LIFOLIFO）队列队列队列队列(duli)(duli)的特点：先进先出（的特点：先进先出（的特点：先进先出（的特点：先进先出（FIFOFIFO）第10页/共30页第十一页，共31页。第三章 栈和队列(duli)栈的操作栈的操作栈的操作栈的操作(cozu)(cozu)：顺序栈：顺序表操作顺序栈：顺序表操作顺序栈：顺序表操作顺序栈：顺序表操作(cozu)(cozu)的特例的特例的特例的特例链栈：单链表操作链栈：单链表操

6、作链栈：单链表操作链栈：单链表操作(cozu)(cozu)的特例的特例的特例的特例第11页/共30页第十二页，共31页。第三章 栈和队列(duli)队列的操作：队列的操作：链队列：带头结点、头指针和尾指针的单链表，入链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。队端在表尾，出队端在表头。循环循环(xnhun)(xnhun)链队列：可以只用一个尾指针链队列：可以只用一个尾指针用定长数组作为队列的存储结构时，一般采用循环用定长数组作为队列的存储结构时，一般采用循环(xnhun)(xnhun)队列的形式队列的形式-循环循环(xnhun)(xnhun)队列。队列。第12页/共3

7、0页第十三页，共31页。第三章 栈和队列(duli)队列的操作：队列的操作：链队列：带头结点链队列：带头结点(ji din)(ji din)、头指针和尾指针的、头指针和尾指针的单链表，入队端在表尾，出队端在表头。单链表，入队端在表尾，出队端在表头。循环链队列：可以只用一个尾指针循环链队列：可以只用一个尾指针用定长数组作为队列的存储结构时，一般采用循用定长数组作为队列的存储结构时，一般采用循环队列的形式环队列的形式第13页/共30页第十四页，共31页。第三章 栈和队列(duli)循环队列(duli)：数组：Q1.maxsize-1front指向对头元素rear指向队尾元素的下一个队列(duli)

8、的最大容量：maxsize-106543217frontreara5a1a2a3a4第14页/共30页第十五页，共31页。第三章 栈和队列(duli)循环队列的计算公式Q0.maxsize-1：入队(r du)：rear=(rear+1)mod maxsize出队：front=(front+1)mod maxsize队空条件：front=rear队满条件：front=(rear+1)mod maxsize队列长度：(rear front+maxsize)mod maxsize第15页/共30页第十六页，共31页。第三章 栈和队列(duli)循环队列的计算公式Q1.maxsize：入队(r du

9、)：rear=rear mod maxsize+1出队：front=front mod maxsize+1队空条件：front=rear队满条件：front=rear mod maxsize+1队列长度：(rear front+maxsize)mod maxsize第16页/共30页第十七页，共31页。第4章 数组数组知识点：多维数组行优先和列优先的存储方式；数组元素地址的计算方法；特殊矩阵的压缩存储方法以及下标变换算公式的推导(tudo)；稀疏矩阵的压缩存储技术-三元组表、十字链表。第17页/共30页第十八页，共31页。第6章 树和二叉树知识点(1)：树和二叉树的定义二叉树的（5个）性质完全

10、二叉树的特点二叉树的存储结构，主要掌握(zhngw)二叉链表二叉树的遍历算法以及二叉树常用运算第18页/共30页第十九页，共31页。第6章 树和二叉树知识点（2）：表达式的二叉树表示树的存储结构(jigu)树、森林与二叉树的相互转换树和森林的遍历哈夫曼树的定义和构造，哈夫曼编码方法第19页/共30页第二十页，共31页。第7章 图知识点(1)：图的概念：有向图，无向图路径，回路(hul)（环），简单路径，简单环无向连通图、连通分量有向强连通图、强连通分量完全图第20页/共30页第二十一页，共31页。第7章 图知识点（2）：生成树、生成森林熟练掌握图的存储结构邻接(ln ji)矩阵和邻接(ln j

11、i)表，他们的特点和操作熟练掌握图的DFS遍历和BFS遍历的概念和实现算法第21页/共30页第二十二页，共31页。第7章 图知识点（3）：最小生成树的概念和prim、Kluscla算法思想拓扑序列的概念和拓扑排序算法最短路径(ljng)的概念和Dijkstra算法关键路径(ljng)的概念和关键路径(ljng)的算法思想第22页/共30页第二十三页，共31页。第8章 查找(ch zho)知识点(1)：平均查找长度ASL的定义(dngy)和计算方法顺序查找的特点、算法和ASL（等概情况下查找成功的ASL（n+1)/2）折半查找的特点、算法和ASL（折半查找判定树的定义(dngy)和使用）第23页

12、/共30页第二十四页，共31页。第8章 查找(ch zho)知识点(2)：索引顺序查找的特点(tdin)、查找方法和ASL二叉排序树的定义、查找、插入、删除哈希表的概念、哈希函数的构造、装填因子对查找效率的影响、解决冲突的方法（线性探测、二次探测和拉链法）、冲突和堆积的不同、哈希表的构造和ASL计算第24页/共30页第二十五页，共31页。第9章 排序(pi x)知识点：知识点：直接插入排序直接插入排序(pi x)(pi x)希尔排序希尔排序(pi x)(pi x)冒泡排序冒泡排序(pi x)(pi x)快速排序快速排序(pi x)(pi x)简单选择排序简单选择排序(pi x)(pi x)堆排

13、序堆排序(pi x)(pi x)归并排序归并排序(pi x)(pi x)排序排序(pi x)(pi x)算法思想（会写过程）算法思想（会写过程）稳定性稳定性时间复杂度时间复杂度特点特点最好、最坏情况分析最好、最坏情况分析第25页/共30页第二十六页，共31页。数据库系统基本概念：基本概念：DBDB，DBSDBS，DBMSDBMS，概念模型，概念模型，数据模型，实体，联系（数据模型，实体，联系（1:11:1，1:n1:n，n:m)n:m)，数，数据独立性，据独立性，ERER图，数据模型的三要素图，数据模型的三要素关键字：候选码，主码，外部码，主属性关键字：候选码，主码，外部码，主属性数据库系统模

14、式数据库系统模式(msh)(msh)结构（三级模式结构（三级模式(msh)(msh)，两级映射），两级映射）用数据库系统来管理数据的特点用数据库系统来管理数据的特点第26页/共30页第二十七页，共31页。数据库系统关系模型的数据结构关系模型的数据结构(sh j ji u)(sh j ji u)关系的定义、关系的性质关系的定义、关系的性质关系的完整性规则关系的完整性规则关系模式的概念关系模式的概念关系代数运算（关系代数运算（9 9种，其中原子运算有种，其中原子运算有5 5种）种）灵活运用关系代数运算实现复杂的查询灵活运用关系代数运算实现复杂的查询第27页/共30页第二十八页，共31页。数据库系统

15、函数依赖的概念函数依赖的概念完全函数依赖、部分函数依赖、传递函数依完全函数依赖、部分函数依赖、传递函数依赖赖1NF1NF、2NF2NF、3NF3NF定义定义会通过分解关系模式达到高级范式会通过分解关系模式达到高级范式(fn sh)(fn sh)会将会将E-RE-R图转换成关系模式图转换成关系模式数据库的设计（四个步骤）数据库的设计（四个步骤）第28页/共30页第二十九页，共31页。数据库系统会用会用SQLSQL的的SelectSelect语句实现查询语句实现查询单表查询、多表连接查询、嵌套查询、用集函单表查询、多表连接查询、嵌套查询、用集函数数(hnsh)(hnsh)查询、分组查询、结果排序查询、分组查询、结果排序会会CreateCreate，DeleteDelete，InsertInsert，UpdateUpdate第29页/共30页第三十页，共31页。感谢您的观看感谢您的观看(gunkn)。第30页/共30页第三十一页，共31页。