《数据结构教学资料》数据结构复习课

《《数据结构教学资料》数据结构复习课》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Chapl绪论基本定义：数据元素、数据对象、数据结构（逻辑结构）、存储结构（物理结构）、数据类型、算法：了解抽象数据类型定义、表示及实现。熟悉数据的逻辑结构和存储结构Z间关系分清哪些是逻辑结构性质哪些是存储结构性质数据结构（逻辑结构）分类：线性结构、树状结构、图结构、集合存储结构（物理结构）分类：顺序存储结构和链式存储结构（定义）掌握算法的定义及算法五耍素的确切含义即算法的五个重要特性、掌握“好”算法的四大目标。掌握计算语句频度和估算算法时间复杂度的方法、时间复杂度和空间复杂度Chap2线性表了解顺序表的逻辑结构特性：数据元素之间存在线性关系、从第一个元素和最后一个元素外每个元素只有一

2、个前驱和后继；计算机表示这种关系的两种不同存储结构分别是顺序存储结构和链式存储结构,前者表示的线性表称为顺序表，后者表示的线性表称为链表。熟练掌握线性表两类存储结构的描述方法（顺序表和链表）。熟练掌握线性表在顺序存储结构（顺序表）上实现的基本操作：查找、插入、删除熟练掌握各种链表（单链表、双向链表、循环链表）中实现的基本操作：查找、插入、删除。能从时间复杂度和空间复杂度角度综合比较线性表两种存储结构的不同特点及其适用场合。应用与算法：单链表查找、插入和删除元素的主要算法Chap3栈与队列栈的逻辑结构特性栈的两种存储结构：顺序栈和链栈、在这两种结构上栈满和栈空的判别及描述方法、入栈和出栈

3、算法。给出入栈出栈数据，能够写出最后栈的状态以及栈的最小容量。队列的逻辑结构特性队列的两种存储结构：循环队列（为什么用循环队列？假溢出概念）和链队列的基本操作实现算法（入队和出队），注意在循环队列上队满和队空的描述方法（判别方法）。Chap4树二叉树及完全二叉树性质（几个定理及其应用）、存储结构（顺序存储结构、链式存储结构屮的二叉链表、三叉链表）的特点及适用范围、二叉树遍历算法（熟练掌握递归和非递归算法，能运用遍历算法实现二叉树其它操作。树的存储结构及特点、树和森林与二叉树的转换方法。了解最优树特性，掌握建立最优树和哈夫曼编码的方法先序和中序序列可以唯一确定一棵二叉树，掌握如何由先序和

4、中序序列建立二叉树的方法。应用及算法设计1、由二叉树（完全二叉树）性质引申出的应用2、己知树的先（根）序中（根）序序列或中序后序序列，能够画出该树。3、二叉树与树和森林的转化，给定二叉树能写出对应的树和森林，反之亦然。4、哈夫曼树及哈夫曼编码算法：中序遍历二叉树的非递归算法。Chap5图图的基本概念：有向图、无向图、有向图和无向图顶点入度和出度。如何根据邻接矩阵或邻接表计算有向图或无向图顶点入度和出度图的各种存储结构（邻接矩阵和邻接表）、了解不同存储结构的适用情况（稠密图和稀疏图）熟练掌握图的两种搜索路径遍历：遍历逻辑定义、广度优先搜索算法和深度优先搜索（递归和非递归算法）用图的遍历算

5、法求各种简单路径问题，如求有向图屮顶点U到V的所有简单路径。图的两个最小生成树算法图的拓扑排序思想图的两个最短路径算法应用及算法设计1、写出图的邻居接矩阵或邻接表2、写出图的两种遍历算法的遍历序列3、图示最小生成树的产生过程4、图示最短路径的求解过程（特别是DJ算法）Chap6查找静态查找表的各种方法：顺序表、有序表、哈希表（什么是同义词、同义词会对哈希表照成什么问题）熟练掌握顺序表和有序表的查找方法：直接查找、折半查找（与直接查找的差别），掌握各种查找方法在等概率情况下查找成功或不成功时的比较次数及平均查找长度。熟练掌握哈希表构造查找和维护方法、掌握哈希表在等概率情况下查找成功时的平

6、均查找长度。应用与算法1、折半查找算法2、实例说明查找过程3、根据给定哈希函数及冲突处理方法构造给定关键字的哈希表，并能求查找成功吋的平均查找长度。Chap7排序按排序过程所依据原则不同分为五类：插入排序（直接插入、折半插入、希尔排序）；交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、归并排序和基数排序按平均时间复杂度可分为三类：简单排序法0（『）（直接插入排序、折半插入排序、冒泡排序、简单选择排序（不稳定））高效排序法O（nlogn）（希尔排序、快速排序（不稳定）、堆排序（不稳定）、归并排序）基数排序（O（dn）算法时间复杂度和稳定性比较。深刻理解各种排序的定义及方

7、法特点。应用及算法1、给定关键字序列能够按照指定的排序思想手工推演出排序结果，要给出中间过程（中间结果）。特别是快速排序、简单选择排序、冒泡排序2、清楚学过的各种算法哪些是稳定的哪些是不稳定的3、知道排序算法的时间复杂度依据算法进行的关键字比较次数和交换次数，掌握各种排序算法对给定关键字排序时需要进行的关键字比较次数或交换次数。比较次数与关键字序列初始状态无关的排序算法是什么？最好情况即待排序列基本有序时不能发挥算法优势的算法是什么？4、判断给