《数据结构》复习大纲

1、第一章绪论1. 数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活 动的描述。凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。2. 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素的组成：一个数据元素通常由一个或若干数据项组成。数据项：指具有独立含义的最小标识单位。3. 数据对象：性质相同的数据元素的集合，是数据的一个子集。4. 数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所 定义的算法在计算机上运行的学科。5. 算法：是对待定冋题求解步骤的一种描述，是指令的有限序列。算法应满足以下性质：1) 输入性：具有零个

2、或若干个输入量；2) 输出性：至少产生一个输出；3) 有穷性：每条指令的执行次数是有限的；4) 确定性：每条指令的含义明确，无二义性；5) 可行性：每条指令都应在有限的时间内完成。6. 评价算法优劣的主要指标：1) 执行算法后，计算机运行所消耗的时间，即所需的机器时间；2) 执行算法时，计算机所占存储量的大小，即所需的存储空间；3) 所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。7. 会估算某一算法的总执行时间和 时间复杂度。8. 熟悉习题 P32:3(5)-(9)、4(2)(3)第二章线性表1. 线性表(P7):是性质相同的一组数据元素序列。线性表的特性：1) 数据元素在线

3、性表中是连续的，表中数据元素的个数可以增加或减少，但调整后 数据元素仍必须是连续的，即线性表是一种线性结构。2) 数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。3) 线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。 线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储 单元，这种存储方法叫做顺序分配，又称顺序映像。其 特点：逻辑上相邻的数据元素， 它们的物理次序也是相邻的。)，存储地址的计算方式(Loc(a J=Loc(a °

4、)+i*s)。2. 线性表的查找、插入和删除熟悉线性表的查找算法(P38)、插入算法(P39)和删除算法(P40)。3. 理解线性表的顺序存储结构的优缺点。4. 熟悉线性链表的存储结构(P43)线性链表(由若干结点链接而成的一种存储结构。)、结点(由存放数据元素值的部 分一数据域和存放另一元素存储地址的部分一指针域或链域两部分信息组成的存储结 构。)、单链表(线性链表)的概念。5. 熟悉线性链表的 建立(P45-47)、查找(P47-48)、插入(P49-50)和删除(P50-51) 的算法；6. 明了什么是循环链表(链表中最后一个结点指针域回指向链表的第一个结点，使得整个链表通过链指针成为一

5、个环形，这种形式的链表称为循环链表。)？7. 明了双向链表的结构(链表中的每个结点有两个指针域，一个是向前链接的左指 针(Lnext或prior)，另一个是向后链接的右指针(Rnext或next)，同时还有一个数据 域(Data)。)； 了解双向链表的插入和删除的算法。8. 理解链表的优缺点(P48)。9. 熟悉习题P68: 1、2第三章限定性线性表-栈和队列1. 栈和队列明确什么是栈及其特点(只允许在一端进行插入和删除的线性表。允许插入和删除 的一端称为栈顶，不允许插入和删除的一端称为 栈底。栈的插入为进栈，称栈的删除为 出栈。栈的特性：后进先出，所以又称后进先出表，简称 LIFO表。）。2

6、. 明了什么是顺序栈（用顺序存储结构表示的栈），熟悉顺序栈进栈算法和出栈算 法（栈空，栈满判定条件，指针移动）。3. 明了什么是链栈（用链表表示的栈。），熟悉链栈（进栈；出栈）的算法。4. 明确什么是队列及其特点（所有的插入（进队）均限制在表的一端进行，所有的删 除（出队）被限制在表的另一端。允许插入的一端称为 队尾（rear），允许删除的一端称为 队头（front）。队列结构特点：先进队的兀素先出队，故也称为 先进先出表，简称FIFO 表。）。5. 了解循环队列及其进队和出队的算法 （循环队列队空队满判定条件，指针移动）。6. 明了什么是链队列（采用链表表示队列。）？熟悉链队列（进队、出队）

7、的算法。7. 熟悉习题P102 1、3、12第四章串1. 掌握串的基本概念：串（是由零个或多个字符组成的有限序列。一般记为：s="ClC2.c n"（n>=0）。）、串的长度（串中字符的数目n。）、空串（零个字符的串，其长度为零。）、空格串（仅含有空 格字符的串，它的长度为串中空格符的个数。）、子串（串中任意个连续的字符组成的子 序列）、主串（包含子串的串）、字符在串中的位置（字符在序列中的序号）、子串在主串 的位置（以子串第一个字符在主串中的位置来表示）、两个串相等（当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各对应位置的字符都相等时才相等。）2

8、. 熟悉串的基本运算：串的赋值运算（assign（a ，b）、串的联接运算（concat（a ，b）、求串长（length（s）、求子串（substr（s ，start ， len）、判断两个串是否相等 （equal（a ，b） ; 了解求子串在主串中的序号（index（a ，b）、替换运算（replace（a ，b，c）、插入运算（insert（a,i,b） 、删除运算（delete（a,i,k） 的功能。3. 明了串的存储结构（P81）:串的静态存储结构（是将串定义成字符型数组，从串名可直接访问到串值，串的存储空间分配是在编译时完成的，不能更改）、串的动态存储结构（是串的存储空间分配是在程

9、序运行时动态分配的）；串的静态存储结构采用顺序存储结构；串的动态存储结构有两种方式：一种是采用链式存储结构，另一种是堆结构 的存储方式。4. 熟悉子串定位函数的算法（P112）。5. 熟悉习题（P119）1。第五章数组和广义表1. 数组（P125）:一维数组、二维数组 存储地址的计算（一维P125公式，或Loc（ai）=Loc（a 0）+i*s ;二维 P125公式，或 Loc（aj ）= Loc（a 0°）+（i*n+j） *s）。2. 上三角矩阵、下三角矩阵、带状矩阵的压缩存储，会求任意元素aj在一维数组中的位置。3. 稀疏矩阵：指大部分元素为零的矩阵。稀疏矩阵的表示方法一三元组

10、表中各元素 所表示的意义。4. 了解广义表的概念，广义表的长度，广义表的表头，广义表的表尾。5. 熟悉习题（P145） 1、3、9。第六章树1. 掌握一般树的概念：一般树的定义（树是n（n>=0）个结点的有限集合。当n=0时称为空树，否则，在任一 棵非空树中：有一个且仅有一个称为该树根（Root）的结点；其余结点可分为m（m>=0） 个互不相交的有限集合T1, T2,，Tm且每个集合本身又是一棵树，并称之为根的子 树（Subtree）。树的定义是一种递归定义）；树的结点（指一个数据元素及若干指向其子 树的分支。）、结点的度（指结点拥有子树的数目。）、叶子结点（指度为零的结点。）、

11、分支结点（指度不为零的结点。）、树的度（指树中各结点度的最大值。）、有序树（将树 中结点的各子树看成从左到右是有次序的，称为有序树，否则称为无序树。）、森林（m（m>=0）棵互不相交的树的集合。）树的存储结构：多重链表表示法（每个结点由一个数据域和若干指针域组成。每个 指针域将指向该结点的一个孩子。），多重链表又分为：定长结点的多重链表和不定长 结点的多重链表；二重链表示法（即孩子兄弟表示法，树中每个结点设置三个域：数据域、长子指针域和次弟指针域。）2. 掌握二叉树的概念二叉树（结点的有限集合，它或者是空集，或者由一个根结点和两个互不相交的该 根的左子树和右子树组成，左右子树也是一棵二叉

12、树，显然这也是一个递归定义。）；二叉树是有序的（二叉树中的结点即使只有一棵子树，也要区分它是左子树还是右子 树）；两种特殊形态的二叉树：满二叉树（如果一棵深度为K的二叉树，共有2k-1结点， 则称为满二叉树。）、完全二叉树（如果深度为k,有n个结点的二叉树，能够与深度为 k的顺序编号满二叉从1到n标号的结点相对应。）了解二叉树的性质，会灵活运用性质：性质1在二叉树的第i层上最多有2'-1个结点（i>=1）。性质2高度为h的二叉树最多有2h-1个结点（h>=1）。（可用图5-7a）解释）性质3对任何二叉树T,设n。、ni、住分别表示度数为0、1、2的结点数，则有 no= n

13、2+1。（叶子结点数与度数为2的结点数的关系）性质4具有n个结点的完全二叉树的深度为logzn +1 0 （注符号x表示不大于 x的最大整数，x则表示不小于x的最小整数）性质5如果将一棵有n个结点的完全二叉树，则对任一结点（1v=iv二n）有：1）若'=1 ,则'是根结点无双亲；若i>1，则'的双亲结点是i/2 o2）若2i<=n，贝U i的左孩子是2i ；若2i>n，贝U i无左孩子。3）若2i+1<=n，贝U i的右孩子是2i+1 ；若2i+1>n，贝U i无右孩子。了解二叉树的存储：二叉树通常有两类存储结构：顺序存储结构和链式存储结构

14、。3. 掌握二叉树的先序遍历的算法；了解中序遍历、后序遍历的算法。 给出一棵树，会写出树的先序中序后序序列。4. 明了结点间的路径长度（从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支个数即是结点间的路径长度）、树的路径长度（从树根到每一个结点的路径长度之和称为树的路径长度，一般记作pl。）、带权路径长度（若给二叉树的每个终端结点赋以权值，从而构成的带权路径长度。其计算方法为：wpl=Wili）、哈夫曼树（带权路径长度wpl最小的树称做最优二叉树或哈夫曼树）；熟悉哈夫曼树的算 法，给出数据序列，会构造哈夫曼树05. 了解一般树转化为二叉树和二叉还原为一般树 。6. 熟

15、悉习题（P194） 2、3、4、7、9、11第七章 图1. 熟悉图的基本术语：图（G由顶点的集合V（G）和边的E（G）集合组成，记做：G = （V，E），其中V（G）是图 中顶点的非空有限集合，E（G）是图中边的有限集合。）、有向图（如果图中每条边都是有 方向的，即在图示时每条边都用箭头表示方向，则称此图为有向图。 ）、无向图（如果图 中每条边都是顶点无序对，则称为无向图。）、无向完全图（若一个无向图有n个顶点， 而每一个顶点与其它 n-1个顶点之间都有边，这样的图称为无向完全图，即共有 n（n-1）/2条边。）、有向完全图（在有n个顶点的有向图中，若有n（n-1）条弧，即任意 两顶点之间都有

16、双向相反的两条弧连接，则称为有向完全图。）、子图（设有两个图G=（V,E）和G'=（V'，E'），如果V V且EE,则称G为G的子图。）、路径（在图G中,从顶点Vp到Vq的一条路径是顶点序列（Vp, V1, V2，V，乂）且（Vp, V1） , （Vi1 , V2）， （Vin, Vq）是E（G）中的边，路径上边的数目称之为该路径长度。）、连通图（在无向图G中， 若从V到V有路径，则称V和V是连通的。若图G中任意两个顶点都连通，则称 G为 连通图，否则称为非连通图。）、强连通图（在有向图G中，若任意两个顶点V和V都连 通的，即从V到V和从V到V都存在路径，则称G是强连通

17、图。）、度（就是依附于该 顶点的边数。）、入度和出度（在有向图中，以某顶点为头，即终止于该结点的弧的数目 称为该顶点的人度；以某顶点为尾，即起始该顶点的弧的数目称为该顶点的出度。顶点 的入度和出度之和称为顶点的度。）2. 熟悉图的存储结构（邻接矩阵和邻接链表），了解建立邻接矩阵或邻接链表的算 法：邻接矩阵（是用一个二维数组来表示图中顶点的相邻关系。设图G=V,E有n1个顶点，贝U G的邻接矩阵是按如下定义的 rB阶方阵：costij= 0反之）、邻接链表（由邻接矩阵改进而来的一种 链接结构，它包含两个部分，一部分是向量，另一部分是链表。链表部分共有n个链表， 即每个顶点一个链表。每个链表由一个

18、表头结点和若干个表结点组成。向量部分为一个 数组，用来存储n个表头结点，向量的下标指示了顶点的序号。）3. 熟悉遍历图的算法：深度优先搜索法和广度优先搜索法。4. 了解最小生成树、最短路径、拓扑排序和关键路径的概念和用途。5. 给出一个无向图，会用普利姆算法和克鲁斯卡尔算法手工构造最小生成树。6. 给出一个有向图，会用迪杰斯特拉算法 求某一顶点到其余各顶点的最短路径，用 弗洛伊德算法求任意一对顶点间的最短路径。7. 熟悉习题（P244）1、4、14、15第八章查找1. 熟悉查找表（由同一数据类型的数据元素（或记录）构成的集合。）、关键字（数据 元素（或记录）中某个数据项的值，用它可标识（识别）

19、一个数据元素（或记录）。若此关键 字可以唯一地标识，则称此关键字为主关键字。）、查找（根据给定的某个关键字的值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。）的概念。2. 熟悉顺序查找（P249）、折半查找（P250-251）的算法，及其平均查找长度。3. 了解分块查找的原理。4. 明了二叉排序树的概念（二叉排序树的定义：它或者是一个空树，或者是一个具 有如下性质的二叉树：（1）若它有左子树，则左子树上有所有结点的数据均小于根结点的数据；（2）若它有右子树，则右子树上所有结点的数据均大于根结点的数据；（3）左，右子树本身又各是一棵二叉树排序树。）；熟悉二叉排序树的算法， 给出数据

20、序列，会 构造二叉排序树。5. 了解什么是哈希法、哈希表和哈希函数 （存取过程中需要在记录存储位置和它的关键字之间建立一个确定的对应关系H,使每个关键字与结构中一个唯一的存储位置相对应。查找时，只要根据这个对应关系 H,就可以找到需要的关键字及其对应的记录。 这种方法称为哈希法（也称为散列法、杂凑法），其存储空间称为哈希表（或散列表），其 对应关系H称为哈希函数。），了解哈希函数的构造方法（构造哈希函数时应遵循的基本 原则：1）算法简单，运算最小；2）均匀分布，减少冲突。直接定址法、（熟悉）除留余数 法、平方取中法、折迭法、数字分析法），了解解决冲突的方法（开放地址法和链地址法）6. 熟悉习题（P295）1、5（1）、12第九章排序1. 明了排序的分类（根据待排序记录数量的不