北交数据结构复习重点.doc

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

1、数据结构复习重点申超波第一章绪论这章没有大题，但也有几个小的考点，如下：(1)数据结构的几种类型，基本概念；(2)数据结构类型和抽象数据类型要理解；(3)算法的五个要素及特点；(4)评价算法的标准，时间复杂度(每年必考，必须知道评价给定的一段程序的时间复杂度)和空间复杂度(这个无所谓)。第二，三章线性表和栈以及队列这两章应该合在一起，因为栈和队列本身就是特殊的线性表。复习要点：（1）熟悉线性表的概念和特点(理解就行)（2）线性表的两种存储结构，即顺序表和链表，能够清楚理解这两种结构的不同之处，比较优劣。

2、（3）能够用伪码写出线性表的创建，插入，删除，合并（非常重要）。（4）知道栈的特性，即先进后出，要理解这个特性以及它应用的领域，还要重点掌握三个操作，出栈(即删除)操作代码及注意判空，进栈(即插入)操作代码及注意判满，求栈当前长度代码。（5）知道队列的特性，即先进先出，要理解这个特性以及它应用的领域，还要重点掌握三个操作，出队列(即删除)操作代码及注意判空，进队列(即插入)操作代码及注意判满，求当前队列长度代码。第四章串，数组，广义表复习要点：（1）串：熟悉常见对串操作方法；理解模式匹配算法；理解KMP

3、算法原理，要求会求模式串的next，以及nextval.（2）数组：理解数组的原理及特点，重点掌握矩阵与数组存储之间彼此对应的运算。（3）广义表：会求表头，表尾，及深度，可以会可以学会广义表的两种画图表示。第五章树和二叉树全书最最最最重点的一章，考点最多，大题几乎最可能出在这章，所以对这章内容无论如何要吃透。复习要点：(1)二叉树的定义和性质，性质最重要就三点就是要知道边和结点之间的关系，以及度数为0和度数为2的结点关系，已知道结点总数求树的深度或相反。(2)遍历二叉树，掌握三种方式的递归代码伪代码，掌

4、握至少一种非递归遍历(书上有)，掌握二叉树的层次遍历。(3)掌握三种线索二叉树构造，理解中序线索二叉树的代码实现过程。(4)理解森林的几种存储方式，以及森林与二叉树转换，还有三种遍历的对应关系。(5)掌握构造最优哈夫曼树的方法，学会计算及带权路径长度。第六章图这章比较难，但考得不是很深。复习要点：(1)图的定义和性质。(2)图的两种常用存储：邻接矩阵和邻接表。(3)掌握图的深度优选遍历和广度优先遍历，要求能写出伪代码。(3)了解无向图和有向图，连通分量，强连通分量及生成树概念。(4)最小生成树的两种算法

5、，要求会写prim算法伪代码。(5)要求会拓扑排序和找关键路径，不要求代码。(6)掌握Dijstra算法，熟读代码，可能出代码填空。第九，十章查找和排序这章是仅次与树那章的重点，考点非常多，可以出大题。复习要点：(1)顺序表，有序表，索引表的查找，学会计算这三种查找的代价。(2)掌握二叉排序树，平衡二叉树以及B树的构建包括添加，和删除一个结果，不要求代码，还要尤其注意它们的性质。(3)掌握哈希表的构造方法，处理冲突的方法，哈希链表的构造方法，及两种哈希表查找失败和成功的代价。(4)比较各种排序的特点，包

6、括时间复杂度，空间复杂度，是否稳定等。(5)掌握直插，快排，简单排序，堆排的伪代码实现。第十一章外排这章要求很简单，知道外排的三种方式，并会构建最大败子树