《数据结构》考前复习大纲

1、数据结构考前复习大纲本复习大纲按章分别叙述三方面的内容：1、考试大纲要求，2、复习考试知识点，3、应用举例。为了方便考生复习， 知识点还给出较详细的描述内容， 举例题型也给出具体的分析过程和完整的参考答案。第一章 绪论考纲要求：1.数据的四种逻辑结构与四种存储结构(理解)2. 时间复杂度的估算及比较(掌握)知识点：1 、 数据结构： 研究是是数据元素之间抽象化的相互关系和这种关系在计算机中的存贮表示， 并对每种结构定义各自的运算， 设计出相应的算法， 而且经过运算后所得的新结构一般仍然是原来的结构类型。2、数据的四类基本组成形式：集合中任何两个结点之间都没有逻辑关系，组 成形式松散。线性结构中

2、结点按逻辑关系一次排列形成一条“锁链”。树形 结构具有分支、层次特性，其形态有点像自然界中的树。图状结构最复杂，其 中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。算法：是执行特定计算的有穷过程。特点：动态有穷确定性输入输出可行性。1、以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的最坏时间复杂性或最坏时间复杂度。2、以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的平均时间复杂性或者平均时间复杂度。3. 时间复杂度从好到坏的级别依次是:常量阶0(1),对数阶O(log2n),线性阶O(n),优化的平方阶O(n*log2n),平方阶0(

3、N2),立方阶0(n3),指数阶0(2),阶乘阶0(n!)4、数据结构的基本任务可以概括为数据结构的设计和实现。应用举例：设 n 为正整数，利用大"0"记号，将下列程序段的执行时间表示为 n 的函数。(1) i=1; k=0;while(i<n) k=k+10*i;i+;分析 ：i=1; /1k=0; /1 while(i<n) n k=k+10*i;/n-1 i+; /n-1由以上列出的各语句的频度，可得该程序段的时间消耗:T(n)=1+1+n+(n-1)+(n-1)=3n可表示为T(n)=O(n)第二章线性表：考纲要求：1线性表的顺序存储、链式存储的各种算法

4、(掌握)2线性表的插入、删除算法(掌握)，3双向链表及循环链表的插入、删除过程(掌握)知识点：1、线性结构是n(n>=0)个结点的有穷序列。线性表:n(n > 0)个结点组成的有限序列线性结构中的元素是有序的，元素个数可以为0 空表元素的个数是有限的同一线性表中的元素的类型，长度相同.2、每个结点至多只有一个之间前趋和一个直接后趋，在线性结构中这种关系是1对1的。3、线性表的逻辑结构是线性结构。所含结点的个数称为线性表的长度(简称表长)。表长为0的线性表为空表。4、顺序表是线性表的顺序存储结构，即按顺序存储方式构造的线性表的存储结 构。5、第i个结点a的存储地址为b+ (i 1)

5、x L (L为内存所占单元/表长。b 是顺序表的第一个存储结点的第一个单元的内存地址。)6、线性表采用链式存储结构时，要求内存中可用存储单元的地址连不连续都可 以。7、求表长和读表元算法的时间复杂性为O (1),从量级上来说已经达到最低水平即最高效率。8、顺序表要求占用连续的空间，为克服顺序表的这一缺点，可采用链接方式来 存储线性表，通常我们将链接方式存储的线性表称为链表。9、线性表的常见链式存储结构有单链表、循环表和双链表，最简单的是单链表。10、定位运算在顺序表和单链表上的实现算法的时间复杂性是同量级的，均为 O(n)。11 .线性结构的逻辑表示如下：L1=() L1是一个空的线性结构;L

6、2=(a,b,c,d,e) L2线性结构中有5个元素,a是起始元素,e是终端元素，c的直接前驱元素是b,c的直接后继元素是d,a元素的序号是1,c元素的序号是3.L1=() L1线性表的长度为零L2=(a,b,c,d,e) L2线性表的长度为512 链表中的元素顺序用结点中的指针给出 ,即用指针表示结点间的逻辑关系 , 元 素顺序与逻辑顺序一致.采用顺序存取方式. 链表的长度是可变的应用举例：1 、下述算法的功能是什么 ?LinkList Demo(LinkList L) / L 是无头结点单链表ListNode *Q,*P;if(L&&L->next)Q=L;L=L-&

7、gt;next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;return L; / Demo该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2 . 设顺序表 L 是一个递增有序表，试写一算法，将x 插入 L 中，并使 L 仍是一个有序表。因已知顺序表L 是递增有序表， 所以只要从顺序表终端结点 (设为 i 位置元素)开始向前寻找到第一个小于或等于 x 的元素位置i 后插入该位置即可。在寻找过程中， 由于大于 x 的元素都应放在 x 之

8、后， 所以可边寻找， 边后移 元素，当找到第一个小于或等于 x 的元素位置i 时，该位置也空出来了。算法如下：/顺序表存储结构如题2.7void InsertIncreaseList( Seqlist *L , Datatype x ) int i;if ( L->length>=ListSize)Error( “ overflow");for ( i=L -> length ; i>0 && L->data i-1 > x ; i-)L->data i =L->data i ; / 比较并移动元素L->data

9、i =x;L -> length+;第三章 栈与队列 :考纲要求：1 栈的存储及运算实现(掌握) ,2 栈的应用：表达式求值(理解)3 栈与递归的实现(理解) ,4 队列的定义及存储实现(掌握)知识点：1. 栈 : 栈是限定仅在一端进行插入, 删除的特殊线性表.， 栈属于加了限定条件的线性结构，栈是后进先出的线性表(1) 进栈和出栈端称为栈顶,另一端称为栈底(2) 栈中元素个数为 0 时为空栈 .(3) 栈中的元素个数为有限多个(4) 同一个栈中的元素的类型,长度相同新进栈的元素称为栈顶元素(5)栈的顺序实现：使用一个数组data栈底元素存放在data(0)中,top值为栈内元素个数及位

10、置,空栈时top=-1(6)使用一个结构体变量表示一个栈元素：其中一个域为数组data另一个为top(7) 栈的链接实现:使用链表实现栈的存储(8) 链栈 :链表的首元素定为栈顶元素,尾元素为栈底.2、队列也可以看成是一种运算受限的线性表，在这种线性表中允许插入的一端称为队尾，允许删除的一端称为队头。队列又称为先进先出线性表。(1)、 队满的条件为： (队尾指针 +1)%长度 = =队内指针 如： (sq.rear+1 )%maxsize)= =sq.front队空的条件为： sq.rear= =sq.front(2) .队列 :限定仅能在一端进队,另一端出队的特殊线性表(3) 加限制的线性结

11、构，先进先出表(4) 进队在队尾,出队在队首(头)，可以是空队(5) 队列中的元素个数是有限的 ,可变的，元素的类型,长度相同应用举例：1、指出下述程序段的功能是什么 ?(4)void Demo3( CirQueue *Q) / 设 DataType 为 int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3功能是：程序段的功

12、能是将一个循环队列 Q 经过 S 栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。2. 设将整数 1， 2， 3， 4 依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请分析1， 2 ， 3 ， 4 的 24 种排列中，哪些序列是可以通过相应的入出栈操作得到的。答： 在 1， 2 ， 3 ， 4 的 24 种排列中，可通过相应入出栈操作得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：1423,2413,3124,3142,3412,4123,41

13、32,4213,4231,4312第四章 串 ,考纲要求：1. 串的模式匹配算法(理解)知识点：1、串是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用 ? 表 示。2. 串(又称字符串)是一种特殊的线性表，它的每个结点仅由一个字符组成。用(String )是零个或多个字符组成的有限序列。一般记为S="aia2an"将串值括起来的双引号本身不属于串 , 它的作用是避免串与常数或与标识符混淆。3. 长度为零的串称为 空串 ( Empty String ) ，它不包含任何字符。仅由一个或多个空格组成的串称为 空白串 ( Blank String ) 。 和分别表示长度

14、为1的空白用和长度为0的空用。4. 串中任意个连续字符组成的子序列称为该串的 子串 。包含子串的串相应地称为 主串 。空串是任意串的子串 任意串是其自身的子串。5. 通常在程序中使用的串可分为：串变量和串常量。串变量和其它类型的变量一样，其取值是可以改变的。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。6.对于某一个i,0 i n-m,将目标用的子用Ti.i+m-1和模式用P0.m-1进行比较,若相等 ,则称匹配成功位置 i 称为位移举例：4.2 假设有如下的串说明： char s130="Stocktom,CA", s230="M

15、arch 51999", s330, *p;(1) 在执行如下的每个语句后 p 的值是什么 ?p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');(2) 在执行下列语句后， s3 的值是什么 ? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);解：(1) stchr(*s,c) 函数的功能是查找字符c 在串 s 中的位置，若找到，则返回该位置，否则返回NULL。因此 :执行 p=stchr(s1,'t');

16、后 p 的值是指向第一个字符t 的位置 , 也就是p=&s11 。执行 p=strchr(s2,'9'); 后 p 的值是指向 s2 串中第一个9所在的位置, 也就是 p=&s29 。' 执行p=strchr(s2,6);之后，p的返回值是NULL(2)strcpy 函数功能是串拷贝， strcat 函数的功能是串联接。所以 :在执行 strcpy(s3,s1); 后， s3 的值是 "Stocktom,CA"在执行 strcat(s3,","); 后， s3 的值变成 "Stocktom,Ca,&quo

17、t;在执行完 strcat(s3,s2); 后， s3 的值就成了 "Stocktom,Ca,March 5,1999"第五章 多维数组与广义表(理解) , 本 章 内 容 安 排 学 生自学。第六章 树与二叉树,考纲要求：1. 树的基本概念(理解) ,2. 树的存储结构与遍历(理解)3. 二叉树的定义及链式存储结构(掌握) , 4 二叉树的遍历算法， 掌握递 归算法(掌握) ， 5. 树与二叉树的转换(掌握) ,6. 哈夫曼树的应用 (掌握)知识点：1、树：是一个或多个结点的有穷集合T,且满足以下条件：(1) 、有且仅有一个指定的称作树根的结点；(2)、除根以外的其余结点

18、被分成m个不相交的集合，这些集合的每一个又 都是树，并且称为根的子树。2、树的术语结点的度：结点 N 的子树数称为结点的度。(1) 、树的度：树T 中各结点的度的最大值称的树T 的度。(2) 、叶子：树中度为 0 的结点称为叶子(终端结点)。(3) 、分枝结点：树中度不为 0 的结点称为分枝结点(非终端结点)。、双亲和孩子：若树中结点P的一棵子树的根是结点C,则我们称P是C的 双亲或父母，反之称C 是 P 的孩子。(5) 、结点的层数：树的层数为 1，其余任一结点的层数等于它的双亲的层数加 1.(6) 、树的深度：树中各结点的层数的最大值称为 T 的深度(高度)。(7) 、兄弟和堂兄弟：同一双

19、亲的孩子之间互称为兄弟，其双亲在同一层的结点互为堂兄弟。(8) 、祖先和子孙：一个点的祖先是指从树的根到该结点所经分枝上的所有结点。一个结点的子树的所有结点都称为该结点的子孙。(9) 、有序树和无序树：如果树中结点各棵子树规定从左至右是有次序的，则称树为有序树，否则为无序树。(10)、森林：N棵互不相交的树的集合称为森林。3. 树的存贮表示：(1) 、双亲数组表示：记录型一维数组： data ， parent(2) 、孩子链表表示法：多重链表表示法：data , degree, linkl , link2 单链表表示法：data , likn(3) 、左孩子右兄弟链表示法： lchild ，

20、data ， rsibling除树根结点外若一个结点的编号为i,则它的双亲结点的编号为i/2,也就是说:当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子.当i为奇数时，其双亲结点编号为(i-1)/2，它是双亲结点的右孩子.4. 二叉树：概念： 是有限个结点的集合， 它或者为空集， 或者是由一个根结点以及两棵互不相交的且分别称为根的左子树和右子树的二叉树组成。五种形态：空，根，左，右，左右2 、性质：位于二叉树第I层上的结点，最多为2I-1 ； (I) =1深度为K的二叉树的结点总数，最多为2K-1 (K)=1- N0=N2+1满二叉树：一棵深度为 K 的具有 2K-1 个结点的二叉

21、树完全二叉树：在一棵二叉树中，若所有结点的度为 0 或为 2 的二叉树顺序二叉树：如果深度为K的具有N个结点的二叉树，它的每一个结点都与深度为K的满二叉树中顺序编号是1到N的结点相对应的二叉树。5. 二叉树的存贮表示：顺序存贮：链表表示： lchild ， data ， rchlid遍历：前序：根一左一右-中序：左一根一右右后序：左右根6. 二叉树的遍历先序遍历,先根遍历访问根结点,遍历左子树,遍历右子树中序遍历后序遍历按层遍历算法有递归方式和非递归方式两种三种遍历的命名，根据访问结点操作发生位置命名： NLR ： 前序遍历（亦称 （先序遍历） 访问结点的操作发生在遍历其左右子树之前。 LNR

22、 ：中序遍历访问结点的操作发生在遍历其左右子树之中（间）。 LRN ：后序遍历访问结点的操作发生在遍历其左右子树之后。由于被访问的结点必是某子树的根，所以N（Node）、L（Left subtlee刑R（Rightsubtree区可解释为根、根的左子树和根的右子树。 NLR、LNR和LRN分别又称 为先根遍历、中根遍历和后根遍历。. 遍历算法 : .中序遍历的递归算法定义：（1）遍历左子树；（2）访问根结点；（3）遍历右子 树。 .先序遍历的递归算法定义：（1）访问根结点；（2）遍历左子树；（3）遍历右子 树。 .后序遍历得递归算 法定义：（1）遍历左子树；（2）遍历右子树；（3）访问根 结点

23、。7 .二叉树的线索化线索链表结点结构为 :ltag=0:lchild 是指向结点左孩子的指针ltag=1:lchild 是指向结点前驱的左线索rtag=0:rchild 是指向结点右孩子的指针rtag=1:rchild 是指向结点后继的右线索lchild ltag data rtag rchild8 . 树的二叉树表示，森林与二叉树的转换。树,森林与二叉树之间存在一一对应关系.树 二叉树（1） 先在所有兄弟结点之间加一连线（2） 对于每一结点 ,保留与其长子连线 ,其余去掉 .森林二叉树（1） 先将森林中的每一棵树变成二叉树（2） 将二叉树的根结点作为兄弟 ,从左到右连接 9. 哈夫曼树最优

24、二叉树（1） 路径长度：树中一个结点到另一个结点之关的路径由这两个结点之间的分枝所构成，路径上的分枝数目称为它的路径长度。（2）n 个带权叶子结点构成的所有二叉树中,带权路径长度WPL 最小的树 .（3）权值最大的叶子结点离根越近的二叉树.(4)满二叉树或完全二叉树不一定是最优二叉树.(5) 哈夫曼编码最优二叉树中左孩子为 0,右孩子为1,叶子结点路径的编码哈夫曼树：WPL哈夫曼码应用举例：1、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树， 但由前序序列和后序序列却(1) 已知一棵二叉树的前序序列和中序序列分别为 请画出此二叉树

25、。(2) 已知一棵二叉树的在序序列和后序序列分别为 画出此二叉树。(3) 已知一棵二叉树的前序序列和后序序列分别为 同的二叉树。不一定能唯一地确定一棵二叉树。ABDGHCEFffi GDHBAEC|FBDCEAFHG DECBHGFA青AB和BA请画出这两棵不解：(1)已知二叉树的前序序列为ABDGHCEFffi中序序歹1GDHBAECIF则可以根据 前序序列找到根结点为A,由此，通过中序序列可知它的两棵子树包分别含有 GDH国口 ECIF结点，又由前序序列可知 B和C分别为两棵子树的根结点 以此 类推可画出所有结点：/OEOFOd/ OG Oh(2) 以同样的方法可画出该二叉树：(3) 这两

26、棵不同的二叉树为：第七章 图 ,考纲要求：1. 有向图，连通图，连通分量，强连通分量等(理解) , 2. 图的存 储结构(理解)3. 图的遍历过程(理解)知识点：1 .概念：一个图G由两个集合V和E组成，V是有限的非空顶点集，E是用顶点 对表示的边集。无向图，有向图；2 . 有向图 :图 G 中的每条边都是有方向的有向边也称为弧,是有两个顶点组成的有序对有向图的顶点集表示为：V1,V2,V3,V4,边集表示为：<V1,V2 >, <V1,V3>, <V1,V4>, <V2,V3 >, <V3,V4>,3 . 无向图 :图 G 中的每条

27、边都是无方向的无向完全图 :有 n*(n-1)/2 条边的无向图无向图的顶点集表示为:V1,V2,V3,V4,边集表示为：(V1,V2),(V1,V3),(V1,V4), (V2,V3),(V3,V4),称边(Vi,Vj)的顶点Vi和Vj互为邻接点(相邻接，相关联)，边(Vi,Vj)依附或关联于顶点 Vi 和 Vj4 .无向图中，顶点v的度(Degreee足关联于该顶点的边的数目，记为D(v). 有向图中，以顶点v为终点的边的数目，称为v的入度;以顶点v为始点而应的数目,称为 v 的出度 ;顶点 v 的度为入度与出度之和 .5 .路径:在无向图G中，若存在一个顶点序列，Vp,Vi1,Vi2,

28、Vim,Vq使得无向边 (Vp,Vi1),(Vi1,Vi2),(Vim,Vq)均属于E(G),则称顶点Vp到Vq存在一条路径.路径中边的数目称为路径长度除 Vp 和 Vq 外 ,其余顶点均不相同 ,称其为简单路径.顶点的度：图G 中关联于顶点V 的边的数目称为 V 的度。所有顶点的度等于边的两倍。完全图： 每对顶点之间都有一条边相连的图。 在有向图中， 每对顶点之间都有两条有向边相互关联的图。在无向完全图中，边的总数为Cn2=n( n-1 ) /2在有向完全图中，边的总数为Pn2=n( n-1 )路径：由边组成。连通图： 对于无向图， 如果图中任何两顶点都是可达的， 则称此图为连能图。对于有向

29、图，如果图中任何两个顶点都是相互可达的， 则此有向图是强连通 的，如果图中任何两顶点至少有一个顶点另一个顶点可达， 则称此有向图是单向 连通的。强连通分量：有向图的最大强连通子图称为它的强连通分量。树图：其本质特征是连通性和无圈性，把不含圈的无向连通图称为树图。网络：是每条边上带有数量指标的连通图。应用举例:1在图7.23所示的各无向图中:14(1)找出所有的简单环。(2)哪些图是连通图？对非连通图给出其连通分量。(1)所有的简单环：(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无连通图：(a)、(c)、(d)是连通图,第八章查找表，分查找算法

30、(掌握)考纲要求：1 二叉排序树概念、插入、删除算法(掌握)，2知识点：1、查找是所有数据处理中最基本、 最常用的操作。特别当查找的对象是一个庞 大数量的数据集合中的元素时，查找的方法和效率就显得格外重要。查找：就是确定一个已给的数据是否出现在某个数据表中。域(字段)：组成记录的每个数据项。关键字： 通常记录中总存在某个或某组数据项， 它们的值能唯一标识一个记录，这个(组)数据项称为关键字。2 . 查找方法：(1) 顺序 ;(2) 二分， 线性插值，分区3 .顺序查找:从表的一端开始,顺序扫描.，平均查找次数:ASLsq=(n+1)/2顺序查找算法的平均查找长度为：ASLs=n+1/2 (n表

31、示第n个元素)顺序查找 :从表的一端开始,顺序扫描.平均查找次数:ASLsq=(n+1)/24 . 二分查找 :在有序表中进行,先确定表的中点位置,再通过比较确定下一步在哪一个半区查找.平均查找次数：利用二分查找的判定树，当n足够大时，有：ASLbnMg(n+1)-1最大查找次数为判定树的高度h,平均查找次数约为h-1.、二分查找的时间复杂度为：O (log 2n)、二分查找的时间性能比顺序查找好，但二分查找要求以有序表作为存储表示。应用举例：. 设有序表为 (a,b,c,e,f,g,i,j,k,p,q), 请分别画出对给定值b,g 和 n 进行折半查找的过程。解：(1) 查找 b 的过程如下

32、 ( 其中方括号表示当前查找区间， 圆括号表示当前比较的关键字 )下标： 123456第一次比较：789 10 11 12 13a b c d e f (g) h i j k p q 第二次比较： a b (c) d e f g h i 第三次比较： a(b)c d e f g h i j k p q 经过三次比较，查找成功。(2)g 的查找过程如下：a b c d e f (g) h i j k p q 一次比较成功。(3)n 的查找过程如下：89 10 11下标： 12345671213第一次比较： ah i (j) k p qh i j k (p) q(g) h i j k p q第二次

33、比较：abc第三次比较：abc第四次比较： a b c d e f g h i j k p q 经过四次比较，查找失败。第九章排序,考纲要求：1直接插入排序、冒泡排序、快速排序、直接选择排序（掌握）2. 快速排序的数据变化过程（理解）知识点：1 .排序是将一批（组）任意次序的记录重新排列成按关键字有序的记录序列的过程 关键字:用来作为排序运算的依据就地排序：排序算法所需的辅助空间不依赖于问题的规模，即辅助空间复杂度为0（1），非就地排序的辅助空间复杂度为O（n）.2 .直接插入排序：将当前未排序部分的第一个记录插入到已排序部分中的适当位 置.R0为哨兵，保存要插入的记录.R1.i-1为已排序部

34、分，Ri.n为未排序部分.当Ri.key<RI-1.KEY 时，确定RI 为要插入的记录.将大于Ri.key的记录后移，当R0.key >Rj.key时，确定Rj+1为插入位置.3 .快速排序一一通过一趟排序，将待排序记录分割成独立的两部分，其中一部分 记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序。三，各排序法的比较稳定排序:直接插入排序，冒泡排序，归并排序，基数排序.元素较小:直接插入排序，直接选择排序元素较大快速排序，堆排序，归并排序稳定排序：如果在排序期间具有相同关键字的记录相对位置不变，则称此排序方法是稳定的.派2、排序要求掌握各种排序方法的同时记住以下这张表:内#序方法的性能比较排序方法最好时间 复杂度平均时间 复杂度最坏时间 复杂度空间 复杂度稳定性适用场合直接插入0 (n)(n2)O (n2)。(1)稳定n较小 冒泡排序0 (n)O (n2)O (n2)