数据结构复习.ppt

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

1、总复习一、学习数据结构的意义二、试题形式和分数三、数据结构的学习重点学习数据结构的意义对事物的特征和事物之间的关系加以分析、抽象，可得到集合、线性表、树、图这四种基本关系，由此得到四类基本数据结构。研究这些结构的特点和处理方法可以方便我们通过计算机实现对现实世界中的这些事物的描叙和处理。提高程序的可读性，使编程更规范学习先进、典型算法，进一步提高编程水平，能够编出有一定难度的程序能够将相关信息组合为一个结构体，初步具有模块化，层次化的编程思想(如open操作包括读入数据集，显示数据集两部分，而前者又包括scan记录，插入记录两步)试题形式和分数一般

2、难题比例：20-25%，平均成绩：75～80基于动态数组、静态数组的顺序结构都有可能考。不考的内容：地址传递、类C语言、空间复杂度、基于游标的链表结构、复杂链表归并、二叉树的删除操作、树的操作、平衡二叉树、B+/B-树、高效排序算法。数据结构的学习重点0.(2')引用、用结构体组织数据和描叙事物1.(1‘)四种基本数据类型及其形式定义、数据结构的逻辑结构、存储结构(顺序结构、链式结构)的含义例：已知数据结构A＝(D,R)，其中D＝{a,b,c}，R＝{,}。请问A是何种数据结构？2.抽象数据类型及其三要素：数据对象、数据关系、基

3、本操作。3.(5')如何分析算法的优劣？时间复杂度、空间复杂度、可读性、正确性4.(2')线性表的概念和主要特征：前驱后继1:1。数据结构的学习重点5.(5‘+10’)顺序表的特点、存储结构、主要操作和经典问题的实现及其效率顺序表的特点：随机存取(优点)、大量元素移动注意事项：空表的判断、表满的判断，位序与数组下标相差1，基地址与顺序表经典问题：有序表的插入删除、基于哨兵的查找、有序表归并，以枢轴为中心划分数据(一趟快速排序)数据结构的学习重点6.(5‘+10’)链表(单链表、循环链表、循环双链表)的特点、存储结构、主要操作的实现及其效率注意事项：

4、空表的判断、遍历结束的标志、头指针和头结点和首元素及其地址、带头结点的优点、链表类型与元素类型、插入删除元素要先找到其前驱数据结构的学习重点7.(5‘)栈和队列的概念、特点、存储结构、算法注意事项：空栈、栈满、空队、循环顺序队列队满的判断，遍历结束的条件数据结构的学习重点8.(5')二叉树的概念(根、子树、双亲、孩子、结点、叶子、度、层次和高度、满二叉树、完全二叉树、二叉排序树)、二叉树的性质、二叉排序树的性质(中序遍历得到有序序列)数据结构的学习重点9.(5‘+10’)二叉树的存储结构(顺序表和二叉链)、四种遍历方法和三种递归遍历算法、根据先序序

5、列构造二叉树、根据随机序列构造二叉排序树，根据先序序列和中序序列求二叉树、二叉树凹入法显示例：已知二叉树A的先序序列为abcd，中序序列为bcda，求该二叉树的后序序列？与该二叉树对应的树的形态怎样。10.(5')树和森林的概念、树与二叉树的转换、树的三种遍历方法数据结构的学习重点11.(10')图的概念(权、网、度、路径、长度、生成树)、存储结构(邻接矩阵，邻接表，十字链表，邻接多重表)、图的遍历(深度优先遍历，广度优先遍历)、经典问题(生成树、最小生成树，关键路径，最短路径)数据结构的学习重点12.关键字与主关键字13.(5'+8')各种查找方

6、法的概念、算法及其效率(基于哨兵的顺序查找、二分法查找、二叉排序树查找)14.(5‘)哈希查找的概念、简单哈希函数的构造、简单的冲突处理方法、哈希查找的效率。例：构建哈希表，插入元素的序列为13562，表长为5，采用的哈希函数为h(key)=key%5，如采用线形探测再散列，最终的哈希表中元素的序列为(注意数组下标是从0开始的)，其平均查找长度是。数据结构的学习重点15.(5‘+10’)插入排序、冒泡排序、选择排序的算法及其效率，快速排序的算法思想及其效率，归并排序的算法思想及其效率，排序的稳定性，堆的概念。注意归并算法、划分算法要考，构造

7、二叉排序树也是排序过程。例：序列4,2,1,3,5,6,0经过一趟快速排序后的序列为，经过一趟归并排序后的序列为。该序列是否为堆，对应二叉树形状怎样？