数据结构与数据库 复习.pptx

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

1、数据结构 70分参考题型：填空,选择,判断：解答题：算法题：第1页/共30页对算法的要求：根据教学知识点的难易和重要性，将相关的算法理解和应用分三个层次进行要求：层次1)能阅读和理解算法，能结合具体数据给出算法执行结果；层次2)能写出算法的伪代码；层次3)能灵活运用算法，对实际问题进行算法设计。第2页/共30页第一章 序论数据结构的知识点：1.数据的逻辑结构2.数据的存储结构3.对数据的运算（运算的定义和运算的实现）4.抽象数据类型的概念和表示方法第3页/共30页第一章 序论算法的知识点：算法的定义算法的特性算法的时间分析和空间分析方法第4页/共30页第二章 线性表5个主要知识点：1.线性表的

2、定义2.线性表的存储表示-顺序表，链表3.线性表的运算在不同存储结构上的实现4.有序表的操作5.线性表的应用第5页/共30页第二章 线性表线性表顺序存储结构的特点：1.逻辑上相邻的元素在物理上也相邻；2.不需要为表示元素之间的逻辑相邻关系开辟附加空间；3.可以随机访问数据元素；4.插入和删除元素时需要大量移动元素。第6页/共30页第二章 线性表线性表链式存储结构的特点：1.逻辑上相邻的元素在物理上不一定相邻；2.需要为表示元素之间的逻辑相邻关系开辟附加空间：指针域；3.无法随机访问数据元素；4.插入和删除元素时不需要大量移动元素，只要修改相关结点的指针值即可。第7页/共30页第二章 线性表几种

3、常用的线性链表:1.单链表2.循环单链表(既可以用头指针引导,又可以用尾指针引导)3.双向链表4.双向循环链表第8页/共30页第二章 线性表 带头结点的链表和不带头结点的链表在操作上有差别.判表空条件:带头结点时带头结点时不带头结点时不带头结点时单链表单链表head-next=NULLhead-next=NULLhead=NULLhead=NULL循环单链表循环单链表head=head-nexthead=head-nexthead=NULLhead=NULL第9页/共30页第三章 栈和队列栈和队列都是插入和删除操作受到限制的特殊线性表；栈的特点：后进先出（LIFO）队列的特点：先进先出（FIF

4、O）第10页/共30页第三章 栈和队列栈的操作：顺序栈：顺序表操作的特例链栈：单链表操作的特例第11页/共30页第三章 栈和队列队列的操作：链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。循环链队列：可以只用一个尾指针用定长数组作为队列的存储结构时，一般采用循环队列的形式-循环队列。第12页/共30页第三章 栈和队列队列的操作：链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。循环链队列：可以只用一个尾指针用定长数组作为队列的存储结构时，一般采用循环队列的形式第13页/共30页第三章 栈和队列循环队列：数组：Q1.maxsize-1front指向对头元

5、素rear指向队尾元素的下一个队列的最大容量：maxsize-106543217frontreara5a1a2a3a4第14页/共30页第三章 栈和队列循环队列的计算公式Q0.maxsize-1：入队：rear=(rear+1)mod maxsize出队：front=(front+1)mod maxsize队空条件：front=rear队满条件：front=(rear+1)mod maxsize队列长度：(rear front+maxsize)mod maxsize第15页/共30页第三章 栈和队列循环队列的计算公式Q1.maxsize：入队：rear=rear mod maxsize+1出队

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

7、树和二叉树知识点（2）：表达式的二叉树表示树的存储结构树、森林与二叉树的相互转换树和森林的遍历哈夫曼树的定义和构造，哈夫曼编码方法第19页/共30页第7章 图知识点(1)：图的概念：有向图，无向图路径，回路（环），简单路径，简单环无向连通图、连通分量有向强连通图、强连通分量完全图第20页/共30页第7章 图知识点（2）：生成树、生成森林熟练掌握图的存储结构邻接矩阵和邻接表，他们的特点和操作熟练掌握图的DFS遍历和BFS遍历的概念和实现算法第21页/共30页第7章 图知识点（3）：最小生成树的概念和prim、Kluscla算法思想拓扑序列的概念和拓扑排序算法最短路径的概念和Dijkstra算法关

8、键路径的概念和关键路径的算法思想第22页/共30页第8章 查找知识点(1)：平均查找长度ASL的定义和计算方法顺序查找的特点、算法和ASL（等概情况下查找成功的ASL（n+1)/2）折半查找的特点、算法和ASL（折半查找判定树的定义和使用）第23页/共30页第8章 查找知识点(2)：索引顺序查找的特点、查找方法和ASL二叉排序树的定义、查找、插入、删除哈希表的概念、哈希函数的构造、装填因子对查找效率的影响、解决冲突的方法（线性探测、二次探测和拉链法）、冲突和堆积的不同、哈希表的构造和ASL计算第24页/共30页第9章 排序知识点：直接插入排序希尔排序冒泡排序快速排序简单选择排序堆排序归并排序排

9、序算法思想排序算法思想（会写过程）（会写过程）稳定性稳定性时间复杂度时间复杂度特点特点最好、最坏情况分析最好、最坏情况分析第25页/共30页数据库系统基本概念：DB，DBS，DBMS，概念模型，数据模型，实体，联系（1:1，1:n，n:m)，数据独立性，ER图，数据模型的三要素关键字：候选码，主码，外部码，主属性数据库系统模式结构（三级模式，两级映射）用数据库系统来管理数据的特点第26页/共30页数据库系统关系模型的数据结构关系的定义、关系的性质关系的完整性规则关系模式的概念关系代数运算（9种，其中原子运算有5种）灵活运用关系代数运算实现复杂的查询第27页/共30页数据库系统函数依赖的概念完全函数依赖、部分函数依赖、传递函数依赖1NF、2NF、3NF定义会通过分解关系模式达到高级范式会将E-R图转换成关系模式数据库的设计（四个步骤）第28页/共30页数据库系统会用SQL的Select语句实现查询单表查询、多表连接查询、嵌套查询、用集函数查询、分组查询、结果排序会Create，Delete，Insert，Update第29页/共30页感谢您的观看。第30页/共30页