《数据结构与数据库》复习.ppt
数据结构复习,（仅供复习参考，考试范围不受此课件的限制）,数据结构 70分参考题型：填空,选择,判断：解答题：算法题：,对算法的要求：根据教学知识点的难易和重要性，将相关的算法理解和应用分三个层次进行要求：层次1)能阅读和理解算法，能结合具体数据给出算法执行结果；层次2)能写出算法的伪代码；层次3)能灵活运用算法，对实际问题进行算法设计。,第一章 序论,数据结构的知识点：数据的逻辑结构数据的存储结构对数据的运算（运算的定义和运算的实现）抽象数据类型的概念和表示方法,第一章 序论,算法的知识点：算法的定义算法的特性算法的时间分析和空间分析方法,第二章 线性表,5个主要知识点：线性表的定义线性表的存储表示-顺序表，链表线性表的运算在不同存储结构上的实现有序表的操作线性表的应用,第二章 线性表,线性表顺序存储结构的特点：逻辑上相邻的元素在物理上也相邻；不需要为表示元素之间的逻辑相邻关系开辟附加空间；可以随机访问数据元素；插入和删除元素时需要大量移动元素。,第二章 线性表,线性表链式存储结构的特点：逻辑上相邻的元素在物理上不一定相邻；需要为表示元素之间的逻辑相邻关系开辟附加空间：指针域；无法随机访问数据元素；插入和删除元素时不需要大量移动元素，只要修改相关结点的指针值即可。,第二章 线性表,几种常用的线性链表:单链表循环单链表(既可以用头指针引导,又可以用尾指针引导)双向链表双向循环链表,第二章 线性表,带头结点的链表和不带头结点的链表在操作上有差别.判表空条件:,第三章 栈和队列,栈和队列都是插入和删除操作受到限制的特殊线性表；栈的特点：后进先出（LIFO）队列的特点：先进先出（FIFO）,第三章 栈和队列,栈的操作：顺序栈：顺序表操作的特例链栈：单链表操作的特例,第三章 栈和队列,队列的操作：链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。循环链队列：可以只用一个尾指针用定长数组作为队列的存储结构时，一般采用循环队列的形式-循环队列。,第三章 栈和队列,队列的操作：链队列：带头结点、头指针和尾指针的单链表，入队端在表尾，出队端在表头。循环链队列：可以只用一个尾指针用定长数组作为队列的存储结构时，一般采用循环队列的形式,第三章 栈和队列,循环队列：数组：Q1.maxsize-1front指向对头元素rear指向队尾元素的下一个队列的最大容量：maxsize-1,第三章 栈和队列,循环队列的计算公式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,第三章 栈和队列,循环队列的计算公式Q1.maxsize：入队：rear=rear mod maxsize+1出队：front=front mod maxsize+1队空条件：front=rear队满条件：front=rear mod maxsize+1队列长度：(rear front+maxsize)mod maxsize,第4章 数组,数组知识点：多维数组行优先和列优先的存储方式；数组元素地址的计算方法；特殊矩阵的压缩存储方法以及下标变换算公式的推导；稀疏矩阵的压缩存储技术-三元组表、十字链表。,第6章 树和二叉树,知识点(1)：树和二叉树的定义二叉树的（5个）性质完全二叉树的特点二叉树的存储结构，主要掌握二叉链表二叉树的遍历算法以及二叉树常用运算,第6章 树和二叉树,知识点（2）：表达式的二叉树表示树的存储结构树、森林与二叉树的相互转换树和森林的遍历哈夫曼树的定义和构造，哈夫曼编码方法,第7章 图,知识点(1)：图的概念：有向图，无向图路径，回路（环），简单路径，简单环无向连通图、连通分量有向强连通图、强连通分量完全图,第7章 图,知识点（2）：生成树、生成森林熟练掌握图的存储结构邻接矩阵和邻接表，他们的特点和操作熟练掌握图的DFS遍历和BFS遍历的概念和实现算法,第7章 图,知识点（3）：最小生成树的概念和prim、Kluscla算法思想拓扑序列的概念和拓扑排序算法最短路径的概念和Dijkstra算法关键路径的概念和关键路径的算法思想,第8章 查找,知识点(1)：平均查找长度ASL的定义和计算方法顺序查找的特点、算法和ASL（等概情况下查找成功的ASL（n+1)/2）折半查找的特点、算法和ASL（折半查找判定树的定义和使用）,第8章 查找,知识点(2)：索引顺序查找的特点、查找方法和ASL二叉排序树的定义、查找、插入、删除哈希表的概念、哈希函数的构造、装填因子对查找效率的影响、解决冲突的方法（线性探测、二次探测和拉链法）、冲突和堆积的不同、哈希表的构造和ASL计算,第9章 排序,知识点：直接插入排序希尔排序冒泡排序快速排序简单选择排序堆排序归并排序,排序算法思想（会写过程）稳定性时间复杂度特点最好、最坏情况分析,数据库系统,基本概念：DB，DBS，DBMS，概念模型，数据模型，实体，联系（1:1，1:n，n:m)，数据独立性，ER图，数据模型的三要素关键字：候选码，主码，外部码，主属性数据库系统模式结构（三级模式，两级映射）用数据库系统来管理数据的特点,数据库系统,关系模型的数据结构关系的定义、关系的性质关系的完整性规则关系模式的概念关系代数运算（9种，其中原子运算有5种）灵活运用关系代数运算实现复杂的查询,数据库系统,函数依赖的概念完全函数依赖、部分函数依赖、传递函数依赖1NF、2NF、3NF定义会通过分解关系模式达到高级范式会将E-R图转换成关系模式数据库的设计（四个步骤）,数据库系统,会用SQL的Select语句实现查询单表查询、多表连接查询、嵌套查询、用集函数查询、分组查询、结果排序会Create，Delete，Insert，Update,
