《数据结构》考前复习大纲_第1页
《数据结构》考前复习大纲_第2页
《数据结构》考前复习大纲_第3页
《数据结构》考前复习大纲_第4页
《数据结构》考前复习大纲_第5页
已阅读5页,还剩9页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

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

3、阶O(n3),指数阶O(2),阶乘阶O(n!)4、数据结构的基本任务可以概括为数据结构的设计和实现。应用举例: 设n为正整数,利用大O记号,将下列程序段的执行时间表示为n的函数。(1) i=1; k=0;while(in) k=k+10*i;i+;分析:i=1; /1k=0; /1 while(i=0)个结点的有穷序列。线性表:n(n0)个结点组成的有限序列线性结构中的元素是有序的,元素个数可以为0 空表元素的个数是有限的同一线性表中的元素的类型,长度相同.2、每个结点至多只有一个之间前趋和一个直接后趋,在线性结构中这种关系是1对1的。3、线性表的逻辑结构是线性结构。所含结点的个数称为线性表的

4、长度(简称表长)。表长为0的线性表为空表。4、顺序表是线性表的顺序存储结构,即按顺序存储方式构造的线性表的存储结构。5、第i个结点ai的存储地址为b+(i1)L (L为内存所占单元/表长。b是顺序表的第一个存储结点的第一个单元的内存地址。)6、线性表采用链式存储结构时,要求内存中可用存储单元的地址连不连续都可以。7、求表长和读表元算法的时间复杂性为O(1),从量级上来说已经达到最低水平即最高效率。8、顺序表要求占用连续的空间,为克服顺序表的这一缺点,可采用链接方式来存储线性表,通常我们将链接方式存储的线性表称为链表。9、线性表的常见链式存储结构有单链表、循环表和双链表,最简单的是单链表。10、

5、定位运算在顺序表和单链表上的实现算法的时间复杂性是同量级的,均为O(n)。11. 线性结构的逻辑表示如下:L1=() L1是一个空的线性结构;L2=(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(LinkL

6、ist L) / L 是无头结点单链表ListNode *Q,*P;if(L&L-next)Q=L;L=L-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后插入该位置即可。在寻找过

7、程中,由于大于x的元素都应放在x之后,所以可边寻找,边后移元素,当找到第一个小于或等于x的元素位置i时,该位置也空出来了。算法如下:/顺序表存储结构如题2.7void InsertIncreaseList( Seqlist *L , Datatype x )int i;if ( L-length=ListSize)Error(“overflow);for ( i=L - length ; i0 & L-data i-1 x ; i-)L-data i =L-data i ; / 比较并移动元素L-data i =x;L - length+;第三章 栈与队列: 考纲要求:1栈的存储及运算实现(掌

8、握) ,2栈的应用:表达式求值(理解)3栈与递归的实现(理解) ,4队列的定义及存储实现(掌握)知识点:1. 栈:栈是限定仅在一端进行插入,删除的特殊线性表.,栈属于加了限定条件的线性结构,栈是后进先出的线性表(1) 进栈和出栈端称为栈顶,另一端称为栈底(2) 栈中元素个数为0时为空栈.(3) 栈中的元素个数为有限多个(4) 同一个栈中的元素的类型,长度相同新进栈的元素称为栈顶元素(5) 栈的顺序实现:使用一个数组data,栈底元素存放在data(0)中,top值为栈内元素个数及位置,空栈时top=-1(6) 使用一个结构体变量表示一个栈元素:其中一个域为数组data,另一个为top(7) 栈

9、的链接实现:使用链表实现栈的存储 (8) 链栈:链表的首元素定为栈顶元素,尾元素为栈底.2、队列也可以看成是一种运算受限的线性表,在这种线性表中允许插入的一端称为队尾,允许删除的一端称为队头。队列又称为先进先出线性表。(1)、队满的条件为:(队尾指针+1)%长度= =队内指针 如:(sq.rear+1)%maxsize)= =sq.front 队空的条件为:sq.rear= =sq.front(2).队列:限定仅能在一端进队,另一端出队的特殊线性表(3) 加限制的线性结构,先进先出表(4) 进队在队尾,出队在队首(头),可以是空队(5) 队列中的元素个数是有限的,可变的,元素的类型,长度相同应

10、用举例: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功能是:程序段的功能是将一个循环队列Q经过S栈的处理,反向排列,原来的队头变成队尾,原来的队尾变成队头。2. 设将整数1,2,3,4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次

11、序夹入其中,请分析 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,4132,4213,4231,4312第四章 串, 考纲要求:1串的模式匹配算法(理解)知识点:1、串是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用表示。2. 串(又称字符串)是一种特殊的线

12、性表,它的每个结点仅由一个字符组成。串(String)是零个或多个字符组成的有限序列。一般记为S=a1a2an将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。3. 长度为零的串称为空串(Empty String),它不包含任何字符。 仅由一个或多个空格组成的串称为空白串(Blank String)。 和分别表示长度为1的空白串和长度为0的空串。4. 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。空串是任意串的子串 任意串是其自身的子串。5. 通常在程序中使用的串可分为:串变量和串常量。串变量和其它类型的变量一样,其取值是可以改变的。串常量和整

13、常数、实常数一样,在程序中只能被引用但不能改变其值。即只能读不能写。6. 对于某一个i,0 i n-m,将目标串的子串Ti.i+m-1和模式串P0.m-1进行比较,若相等,则称匹配成功 位置i 称为位移举例:4.2 假设有如下的串说明:char s130=Stocktom,CA, s230=March 5 1999, 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);解:

14、(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置,若找到,则返回该位置,否则返回NULL。因此:执行p=stchr(s1,t);后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,在执行完strcat

15、(s3,s2);后,s3的值就成了Stocktom,Ca,March 5,1999第五章 多维数组与广义表(理解),本章内容安排学生自学。第六章 树与二叉树, 考纲要求:1.树的基本概念(理解) ,2.树的存储结构与遍历(理解)3.二叉树的定义及链式存储结构(掌握), 4二叉树的遍历算法,掌握递归算法(掌握),5.树与二叉树的转换(掌握), 6.哈夫曼树的应用(掌握)知识点:1、树:是一个或多个结点的有穷集合T,且满足以下条件:(1)、有且仅有一个指定的称作树根的结点;(2)、除根以外的其余结点被分成m个不相交的集合,这些集合的每一个又都是树,并且称为根的子树。2、树的术语结点的度:结点N的子

16、树数称为结点的度。(1)、树的度:树T中各结点的度的最大值称的树T的度。(2)、叶子:树中度为0的结点称为叶子(终端结点)。(3)、分枝结点:树中度不为0的结点称为分枝结点(非终端结点)。(4)、双亲和孩子:若树中结点P的一棵子树的根是结点C,则我们称P是C的双亲或父母,反之称C是P的孩子。(5)、结点的层数:树的层数为1,其余任一结点的层数等于它的双亲的层数加1.(6)、树的深度:树中各结点的层数的最大值称为T的深度(高度)。(7)、兄弟和堂兄弟:同一双亲的孩子之间互称为兄弟,其双亲在同一层的结点互为堂兄弟。(8)、祖先和子孙:一个点的祖先是指从树的根到该结点所经分枝上的所有结点。一个结点的

17、子树的所有结点都称为该结点的子孙。(9)、有序树和无序树:如果树中结点各棵子树规定从左至右是有次序的,则称树为有序树,否则为无序树。(10)、森林:N棵互不相交的树的集合称为森林。3.树的存贮表示:(1)、双亲数组表示:记录型一维数组:data,parent(2)、孩子链表表示法:多重链表表示法: data,degree,link1,link2单链表表示法:data,likn(3)、左孩子右兄弟链表示法:lchild,data,rsibling除树根结点外,若一个结点的编号为i,则它的双亲结点的编号为i/2,也就是说:当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子.当i为奇数时,

18、其双亲结点编号为(i-1)/2,它是双亲结点的右孩子.4.二叉树:概念:是有限个结点的集合,它或者为空集,或者是由一个根结点以及两棵互不相交的且分别称为根的左子树和右子树的二叉树组成。五种形态:空,根,左,右,左右 2、性质:位于二叉树第I层上的结点,最多为2I-1;(I)=1深度为K的二叉树的结点总数,最多为2K-1(K)=1N0=N2+1满二叉树:一棵深度为K的具有2K-1个结点的二叉树完全二叉树:在一棵二叉树中,若所有结点的度为0或为2的二叉树顺序二叉树:如果深度为K的具有N个结点的二叉树,它的每一个结点都与深度为K的满二叉树中顺序编号是1到N的结点相对应的二叉树。5.二叉树的存贮表示:

19、顺序存贮:链表表示:lchild,data,rchlid遍历:前序:根左右中序:左根右后序:左右根6.二叉树的遍历先序遍历,先根遍历访问根结点,遍历左子树,遍历右子树中序遍历后序遍历按层遍历算法有递归方式和非递归方式两种三种遍历的命名,根据访问结点操作发生位置命名: NLR:前序遍历(亦称(先序遍历) 访问结点的操作发生在遍历其左右子树之前。 LNR:中序遍历访问结点的操作发生在遍历其左右子树之中(间)。 LRN:后序遍历访问结点的操作发生在遍历其左右子树之后。由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的

20、左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。. 遍历算法:中序遍历的递归算法定义:(1)遍历左子树; (2)访问根结点; (3)遍历右子树。先序遍历的递归算法定义:(1)访问根结点; (2)遍历左子树; (3)遍历右子树。后序遍历得递归算法定义:(1)遍历左子树; (2)遍历右子树; (3)访问根结点。7.二叉树的线索化线索链表结点结构为:ltag=0:lchild是指向结点左孩子的指针ltag=1:lchild是指向结点前驱的左线索rtag=0:rchild是指向结点右孩子的指针rtag=1:rchild是指向结点后继的右线索lchild ltag da

21、ta rtag rchild8.树的二叉树表示,森林与二叉树的转换。树,森林与二叉树之间存在一一对应关系.树 二叉树(1) 先在所有兄弟结点之间加一连线(2) 对于每一结点,保留与其长子连线,其余去掉.森林 二叉树(1) 先将森林中的每一棵树变成二叉树(2) 将二叉树的根结点作为兄弟,从左到右连接9.哈夫曼树最优二叉树(1)路径长度:树中一个结点到另一个结点之关的路径由这两个结点之间的分枝所构成,路径上的分枝数目称为它的路径长度。(2)n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的树.(3)权值最大的叶子结点离根越近的二叉树.(4)满二叉树或完全二叉树不一定是最优二叉树.(5)

22、哈夫曼编码最优二叉树中左孩子为0,右孩子为1,叶子结点路径的编码.哈夫曼树:WPL,哈夫曼码应用举例:1、若二叉树中各结点的值均不相同,则由二叉树的前序序列和中序序列,或由其后序序列和中序序列均能唯一地确定一棵二叉树,但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF,请画出此二叉树。 (2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA,请画出此二叉树。 (3)已知一棵二叉树的前序序列和后序序列分别为AB和BA,请画出这两棵不同的二叉树。解: (1)已知二叉树的前序序列为AB

23、DGHCEFI和中序序列GDHBAECIF,则可以根据前序序列找到根结点为A,由此,通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点,又由前序序列可知B和C分别为两棵子树的根结点.以此类推可画出所有结点: A / B C / / D EF / / G H I (2)以同样的方法可画出该二叉树: A / B F C G / D E H (3)这两棵不同的二叉树为: A A / B B第七章 图, 考纲要求: 1.有向图,连通图,连通分量,强连通分量等(理解), 2.图的存储结构(理解)3.图的遍历过程(理解)知识点:1.概念:一个图G由两个集合V和E组成,V是有限的非空顶点集,E是用

24、顶点对表示的边集。无向图,有向图;2. 有向图:图G中的每条边都是有方向的有向边也称为弧,是有两个顶点组成的有序对 有向图的顶点集表示为:V1,V2,V3,V4,边集表示为:V1,V2,V1,V3,V1,V4,V2,V3,V3,V4,3. 无向图:图G中的每条边都是无方向的无向完全图:有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的度(Degr

25、eee)是关联于该顶点的边的数目,记为D(v).有向图中,以顶点v为终点的边的数目,称为v的入度;以顶点v为始点的边的数目,称为v的出度;顶点v的度为入度与出度之和.5. 路径:在无向图G中,若存在一个顶点序列, Vp,Vi1,Vi2,Vim,Vq使得无向边 (Vp,Vi1),(Vi1,Vi2),(Vim,Vq)均属于E(G),则称顶点Vp到Vq存在一条路径.路径中边的数目称为路径长度除Vp和Vq外,其余顶点均不相同,称其为简单路径.顶点的度:图G中关联于顶点V的边的数目称为V的度。所有顶点的度等于边的两倍。完全图:每对顶点之间都有一条边相连的图。在有向图中,每对顶点之间都有两条有向边相互关联

26、的图。在无向完全图中,边的总数为Cn2=n(n-1)/2在有向完全图中,边的总数为Pn2=n(n-1)路径:由边组成。连通图:对于无向图,如果图中任何两顶点都是可达的,则称此图为连能图。对于有向图,如果图中任何两个顶点都是相互可达的,则此有向图是强连通的,如果图中任何两顶点至少有一个顶点另一个顶点可达,则称此有向图是单向连通的。强连通分量:有向图的最大强连通子图称为它的强连通分量。 树图:其本质特征是连通性和无圈性,把不含圈的无向连通图称为树图。网络:是每条边上带有数量指标的连通图。应用举例:1 在图7.23所示的各无向图中:(1)找出所有的简单环。(2)哪些图是连通图?对非连通图给出其连通分

27、量。答:(1)所有的简单环:(同一个环可以任一顶点作为起点)(a)1231(b)无(c)1231、2342、12341(d)无(2)连通图:(a)、(c)、(d)是连通图,(b)不是连通图,因为从1到2没有路径。具体连通分量为:第八章 查找表 ,考纲要求:1二叉排序树概念、插入、删除算法(掌握), 2二分查找算法(掌握)知识点:、查找是所有数据处理中最基本、最常用的操作。特别当查找的对象是一个庞大数量的数据集合中的元素时,查找的方法和效率就显得格外重要。查找:就是确定一个已给的数据是否出现在某个数据表中。域(字段):组成记录的每个数据项。关键字:通常记录中总存在某个或某组数据项,它们的值能唯一

28、标识一个记录,这个(组)数据项称为关键字。2.查找方法:(1)顺序;(2)二分,线性插值,分区3.顺序查找:从表的一端开始,顺序扫描.,平均查找次数:ASLsq=(n+1)/2顺序查找算法的平均查找长度为:ASLs=n+1/2 (n表示第n个元素)顺序查找:从表的一端开始,顺序扫描.平均查找次数:ASLsq=(n+1)/24. 二分查找:在有序表中进行,先确定表的中点位置,再通过比较确定下一步在哪一个半区查找.平均查找次数:利用二分查找的判定树,当n足够大时,有: ASLbnlg(n+1)-1最大查找次数为判定树的高度h,平均查找次数约为h-1.、二分查找的时间复杂度为:O(2n)、二分查找的

29、时间性能比顺序查找好,但二分查找要求以有序表作为存储表示。应用举例:.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。解:(1)查找b的过程如下(其中方括号表示当前查找区间,圆括号表示当前比较的关键字)下标: 1 2 3 4 5 6 7 8 9 10 11 12 13第一次比较: a b c d e f (g) h i j k p q第二次比较: a b (c) d e f g h i j k p q第三次比较: a (b)c d e f g h i j k p q经过三次比较,查找成功。 (2)g的查找过程如下: a b c d e

30、f (g) h i j k p q 一次比较成功。 (3)n的查找过程如下: 下标: 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较: a b c d e f (g) h i j k p q 第二次比较: a b c d e f g h i (j) k p q 第三次比较: a b c d e f g h i j k (p) q 第四次比较: a b c d e f g h i j k p q 经过四次比较,查找失败。第九章 排序,考纲要求: 1直接插入排序、冒泡排序、快速排序、直接选择排序(掌握) 2.快速排序的数据变化过程(理解)知识点:1.排序是将一批(组)任意次

31、序的记录重新排列成按关键字有序的记录序列的过程关键字:用来作为排序运算的依据就地排序:排序算法所需的辅助空间不依赖于问题的规模,即辅助空间复杂度为O(1),非就地排序的辅助空间复杂度为O(n).2. 直接插入排序:将当前未排序部分的第一个记录插入到已排序部分中的适当位置.R0为哨兵,保存要插入的记录.R1.i-1为已排序部分,Ri.n为未排序部分.当Ri.keyRI-1.KEY时,确定RI为要插入的记录.将大于Ri.key的记录后移,当R0.key Rj.key时,确定Rj+1为插入位置.3.快速排序通过一趟排序,将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,再分别对这两部分记录进行下一趟排序,以达到整个序列有序。三,各排序法的比较稳定排序:直接插入排序,冒泡排序,归并排序,基数排序.元素较小:直接插入排序,直接选择排序元素较大:快速排序,堆排序,归并排序稳定排序:如果在排序期间具有相同关键字的记录相对位置不变,则称此排序方法是稳定的.2、排序要求掌握各种排序方法的同时记住以下这张表:内排序方法的性能比较排序方法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场合直接插入0(n)(n2)O(n2)O(1)稳定n较小冒泡排序0(n)O(n2)O(n2)O(1)稳定n较小快速排序O(n2n)O(n2

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论