数据结构 考前复习

《数据结构 考前复习》由会员分享，可在线阅读，更多相关《数据结构 考前复习（33页珍藏版）》请在金锄头文库上搜索。

1、数据结构 与 算法考前复习v期末考试题型：10道大题，其中一道算法编程 题，其余为问答题或分析题。v考试范围：上课讲过的内容（较难的算法如字 符串相关的KMP算法不做要求）v算法编程题：面向问题，解决问题。作答最好 是先给出算法描述，再给出具体的程序（可以 利用书上的数据结构和基本操作）。v问答题和分析题：如数据结构的基本概念，数 据结构的性质及其证明，经典算法的时间复杂 度及其执行过程分析等等v最终成绩：期末考试成绩为主，平时表现为辅期末考试概述v我们讲过的内容包括q绪论q线性表q栈和队列q串和数组q树q图q查找q排序一般数据结构学科的章 节划分基本上为： 概论 线性表 栈和队列 串 多维数

2、组和广义表 树和二叉树 图 查找 内排 （外排，文件，动态 存储分配）。我们讲过的内容v对于每一章，要清楚 1 想解决的问题 2 基本的数据结构 3 基本的操作 4 算法（特别是经典算法）的解决思路，程序 实现及时间复杂性 经典算法比如：有序表的归并，矩阵的快速转置 ，二叉树的遍历，哈夫曼树的构造，图的（广 度优先和深度优先）遍历，最小生成树，最短 路径，折半查找，冒泡排序，直接插入排序， 快速排序等等各章需注意的要点v绪论：内容很少，概念简单，分数大多只有几分。v线性表：基础章节，常考内容之一。考题多数为基本概念题 ，一般鲜有大型算法设计题。如果有，也是与其它章节内容 相结合。v栈和队列：基

3、础章节，容易出基本概念题，必考内容之一。 而栈常与其它章节配合考查，也常与递归等概念相联系进行 考查。v串和数组 ：基础章节，概念较为简单。基于数组的算法题 也是常见的，分数比例波动较大，是出题的“可选单元”或“ 侯补单元”。一般如果要出题，多数不会作为大题出。数组 常与“查找，排序”等章节结合来作为大题考查。 各章考点（一）v树和二叉树 ：重点难点章节，必考章节。考研时各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。v图 ：重点难点章节，考研时名校尤爱考。如果作为重点来考，则多出现于分析与设计题型

4、当中，可与树一章共同构成算法设计大题的题型设计。各章考点（二）v查找 ：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。v排序 ：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。各章考点（三）v本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，比如逻辑结构和存储结构以及数

5、据元素间的各种关系；时间和空间复杂度的概念及度量方法，算法设计时的注意事项等。本章考点不多，只要稍加注意理解即可。v主要考时间复杂性的计算，时间复杂性的比较回顾：绪论v作为线性结构的开篇章节，线性表一章在线性结构的学 习乃至整个数据结构学科的学习中，其作用都是不可低 估的。在这一章，第一次系统性地引入链式存储的概念 ，链式存储概念将是整个数据结构学科的重中之重，无 论哪一章都涉及到了这个概念。v总体来说，线性表一章可供考查的重要考点有以下几个 方面： 1.线性表的相关基本概念，如：前驱、后继、表长、空 表、头结点，头指针等概念。 2.线性表的结构特点，主要是指：除第一及最后一个元 素外，每个结

6、点都只有一个前趋和只有一个后继。回顾：线性表3.线性表的顺序存储方式及其在具体语言环境下的两种 不同实现：表空间的静态分配和动态分配。静态链表与 顺序表的相似及不同之处。 4.线性表的链式存储方式及以下几种常用链表的特点和 运算：单链表、循环链表，双向链表，双向循环链表。 其中，单链表的归并算法、循环链表的归并算法、双向 链表及双向循环链表的插入和删除算法等都是较为常见 的考查方式。此外，近年来在不少学校中还多次出现要 求用递归算法实现单链表输出（可能是顺序也可能是倒 序）的问题。 5.线性表的顺序存储及链式存储情况下，其不同的优缺 点比较，即其各自适用的场合。单链表中设置头指针、 循环链表中

7、设置尾指针而不设置头指针的各自好处。 回顾：线性表（续）v复习此章前，你可以问一下自己是不是已经知道了以下几 点：v1.栈、队列的定义及其相关数据结构的概念，包括：顺序 栈，链栈，循环队列，链队列等。栈与队列存取数据（请 注意包括：存和取两部分）的特点。v2.栈的应用：数值表达式的求解，括号的配对等的原理， 只作原理性了解，具体要求考查此为题目的算法设计题不 多。v3.循环队列中判队空、队满条件，循环队列中入队与出队 算法。v4. 栈的InitStack, Push, Pop, StackEmpty等基 本操作，队列的InitQueue, QueueEmpty, EnQueue, DeQueu

8、e等基本操作回顾：栈与队列v1.串的基本概念，串与线性表的关系（串是其元素均 为字符型数据的特殊线性表），空串与空格串的区别， 串相等的条件v2.串的基本操作，以及这些基本函数的使用，包括： 取子串，串连接，串替换，求串长等等。v3.顺序串与链串及块链串的区别和联系，实现方式。v4.多维数组中某数组元素的position求解。一般是给 出数组元素的首元素地址和每个元素占用的地址空间并 组给出多维数组的维数，然后要求你求出该数组中的某 个元素所在的位置。v5.将特殊矩阵中的元素按相应的换算方式存入数组中 。这些矩阵包括：对称矩阵，三角矩阵，具有某种特点 的稀疏矩阵等。熟悉稀疏矩阵的存储方式。回顾

9、：串和数组v从对线性结构的研究过度到对树形结构的研究，是数据结 构课程学习的一次跃变，此次跃变完成的好坏，将直接关 系到你到实际的考试中是否可以拿到高分，而这所有的一 切，将最终影响你的课程总分。所以，树这一章的重要性 ，已经不说自明了。总体来说，树一章的知识点包括：v二叉树的概念、性质和存储结构，二叉树遍历的三种算法 （递归与非递归），在三种基本遍历算法的基础上实现二 叉树的其它算法，线索二叉树的概念和线索化算法以及线 索化后的查找算法，最优二叉树的概念、构成和应用，树 的概念和存储形式，树与森林的遍历算法及其与二叉树遍 历算法的联系，树与森林和二叉树的转换。回顾：树和二叉树（一）下面我们来

10、看考试中对以上知识的主要考查方法：v1.二叉树的概念、性质和存储结构.考查方法可有：q直接考查二叉树的定义，让你说明二叉树与普通双分支 树的区别；q考查满二叉树和完全二叉树的性质，普通二叉树的五个 性质：第i层的最多结点数，深度为k的二叉树的最多结 点数，n0=n2+1的性质，n个结点的完全二叉树的深度.q顺序存储二叉树时孩子结点与父结点之间的换算关系（ 左为：2*i，右为：2*i+1）。q二叉树的顺序存储和二叉链表存储的各自优缺点及适用 场合，二叉树的三叉链表表示方法。回顾：树和二叉树（二）v2.二叉树的三种遍历算法q这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关 系到树一章

11、的算法设计题能否顺利完成。二叉树的遍历算法有三种：前 序，中序和后序。其划分的依据是视其每个算法中对根结点数据的访问 顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其执行的实际步 骤，并且应该熟练掌握三种遍历算法。由于二叉树一章的很多算法，可 以直接根据三种递归算法改造而来（比如：求叶子个数）。v3.可在三种遍历算法的基础上改造完成的其它二叉树算法q求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二 叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除 值为n的某个指定结点，诸如此类等等等等。如果你可以熟练掌握二叉树的递归遍历算法，那么解决以上问题就是小菜一碟了。回顾

12、：树和二叉树（三）v4.线索二叉树：q线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知， 递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层 次一多，势必带来资源耗尽的危险，为了避免此类情况，线索二叉树便 堂而皇之地出现了。对于线索二叉树，应该掌握：线索化的实质，线索 化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问 题。 v5.最优二叉树（哈夫曼树）：q最优二叉树是为了解决特定问题引出的特殊二叉树结构，它的前提是给 二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的 。最优二叉树一节，直接考查算法源码的很少，一般是给你一组数据， 要求你建立基

13、于这组数据的最优二叉树，并求出其最小权值之和，此类 题目不难，属送分题。另外，还有考叶子结点与结点总数的关系。回顾：树和二叉树（四）v6.树与森林：q二叉树是一种特殊的树。这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重要的特殊之处是在于：二叉树是有序的！即：二叉树的左右孩子 是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树 与原二叉树我们认为是不相同的两棵二叉树。但是，对于普通的双分支树而 言，不具有这种性质。q树、二叉树与森林三者之间的相互转换。简单，必须掌握。q树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法：先根与后 根（对于森林而言称作：先序与后序遍历

14、）。一般只是要求你根据先根或后 根写出他们的遍历序列。此二者的先根与后根遍历与二叉树中的遍历算法是 有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的 中序遍历。这一点成为很多学校的考点，考查的方式不一而足，有的直接考 此句话，有的是先让你求解遍历序列然后回答这个问题。v树一章，处处是重点，道道是考题，大家务必个个过关。回顾：树和二叉树（五）v如果说，从线性结构向树形结构研究的转变，是数据结构 学科对数据组织形式研究的一次升华，那么从树形结构的 研究转到图形结构的研究，则进一步让我们看到了数据结 构对于解决实际问题的重大推动作用。v图这一章的特点是：概念繁多，与离散数学中图的概

15、念联 系紧密，算法复杂，极易被考到，且容易出大题，尤其是 名校，作为考研课程，如果不考查树与图两章的知识，几 乎是不可想像的。回顾：图（一）下面我们看一下图这一章的主要考点以及这些考点的考查方 式：v1.考查有关图的基本概念问题：q这些概念是进行图一章学习的基础，这一章的概念包括：图的定义 和特点，无向图，有向图，入度，出度，完全图，生成子图，路径 长度，回路，（强）连通图，（强）连通分量等概念。与这些概念 相联系的相关计算题也应该掌握。v2.考查图的几种存储形式：q图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多 重表。在考查时，有的学校是给出一种存储形式，要求考生用算法 或手写出

16、与给定的结构相对应的该图的另一种存储形式。回顾：图（二）v3.考查图的两种遍历算法：深度遍历和广度遍历q深度遍历和广度遍历是图的两种基本的遍历算法，这两个算法对图 一章的重要性等同于“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是基于这两种基本的遍 历算法而设计的，比如：“求最长的最短路径问题”和“判断两顶点 间是否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。v4.生成树、最小生成树的概念以及最小生成树的构造： PRIM算法和KRUSKAL算法。q考查时，一般不要求写出算法源码，而是要求根据这两种最小生成 树的算法思想写出其构造过程及最终生成的最小生成树。另外，也 经常考最小生成树的性质、PRIM算法和KRUSKAL算法可靠性的证明。回顾：图（三）v5.拓扑排序问题：q拓扑排序过程。q值得注意的是，可利用拓扑排序算法来确定有向图是否有环。v6.关键路径问题：q这个问题是图一章的难点问题。理解关键路径的关键有三个方面：一 是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间 是什么意思、如何求。简单地说，