软考辅导——数据结构与算法(“结点”文档)共134张.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,数据结构与算法,软考辅导,数据结构与算法概述,算法知识点复习,模拟练习,考点分析,主 要 内 容,数据结构知识点复习,考 点 分 析,数据结构与算法基础,常用数据结构：,57%,数据结构基础与线性表：,7,树和二叉树：,14,图：,11,算法基础：,43%,算法的描述与分析,常用数值计算算法,常用非数值计算算法,排序算法,查找算法,数据结构与算法概述,数据结构的概念：,数据结构研究的内容：,数据结构的主要逻辑结构,数据结构：,(Data Structure),数据结构是带,“,结构,”,的数据元素的集合。,“,结构,”,即指,数据元素之间存在的联系,。所以数据结构又可以定义为有联系的数据元素的集合。,数据结构主要研究几种常用的数据结构的逻辑特点、存储结构的实现、常用的操作的具体实现方法、各种结构的具体应用等问题。,线性结构：线性表、栈、队列、数组、广义表,非线性结构：树、图,常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法,算法,第一部分 线性表,分值：,0 1,分 （每年）,分数比重：,0%10%,重要知识点：,1,、顺序表的结构特点,2,、单链表的结构特点,3,、双向链表的插入删除,4,、循环链表的结构特点,第一部分 线性表,顺序表,特点：,利用物理存储位置的相邻关系反应元素之间的次序关系,优点：,1.,无需为表示结点间的逻辑关系而增加额外的存储空间；,2.,可方便地随机存取表中的任一元素。,缺点：,1.,插入或删除运算不方便，需要移动大量的结点，其效率较低；,2.,需要预先确定顺序表的最大表长，由于顺序表要求占用连续的存储,空间，存储分配只能预先进行静态分配。因此当表长变化较大时，,难以确定合适的存储规模。,第一部分 线性表,单链表,list,a,1,d,1,a,2,d,2,a,3,d,3,a,4,d,4,物理状态,逻辑状态,d,2,d,1,d,3,d,4,a,2,a,3,a,4,a,1,d,3,d,4,d,2,优点：,1.,链表动态存储分配的结构，能有效利用存储空间；。,2.,插入或删除时只需要修改指针，而不需要进行大量元素的移动。,缺点：,1.,必需为表示结点间的逻辑关系而增加额外的存储空间；,2.,不能随机存取、访问数据元素。,特点：,单链表中逻辑上相邻的数据元素在物理上不一定相邻。数据元素之间的逻辑关系通过链指针间接地反映出来。,第一部分 线性表,双向链表,特点：,双向链表中查找某结点的直接前驱结点和直接后继结点的运算的,时间复杂度均为,O(1),e,s,b,p,a,s-prior=p-prior;,p-prior-next=s;,s-next=p;,p-prior=s;,p-prior-next=p-next;,p-next-prior=p-prior;,a,b,c,插入：,删除：,p,第一部分 线性表,循环链表,循环链表,(Circular Linked List),：链表中最后一个结点的指针域指向整,个链表的头结点，从而使链表形成一个首尾相接的环形链表。,特点：,从链表尾部到链表头部比较方便。从表中任一结点出发均可找到,表中其它结点。,判空：,表尾判断：,L,a,1,L,a,n,L-next=L;,p-next=L;,rear,a,1,a,i,a,i-1,a,n,采用尾指针的循环单链表,开始结点的存储位置：,rear-next-next,终端结点的存储位置：,rear,第一部分 线性表,真题,200505,循环链表的主要优点是,(38),（,38,）,A.,不再需要头指针了,B.,已知某个结点的位置后，能很容易找到它的直接,前驱结点,C.,在进行删除操作后，能保证链表不断开,D.,从表中任一结点出发都能遍历整个链,200605,给定,个有,n,个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动（,54,）个元素。,（,54,）,A,(n+1)/2,B,n/2,C,(n-1)/2,D,1,第一部分 线性表,真题,200611,某双向链表中的结点如下图所示，删除,t,所指结点的操,作为（,54,）。,(54)A.t-prior-next=t-next;t-next-prior=t-prior;,B.t-prior-prior=t-prior;t-next-next=t-next;,C.t-prior-next=t-prior;t-next-prior=t-next;,D.t-prior-prior=t-next;t-next-prior=t-prior;,第一部分 线性表,真题,200711,对于,n,（,n0,）个元素构成的线性序列,L,，在 （,60,）,时适合采用链式存储结构。,（,60,）,A.,需要频繁修改中元素的值,B.,需要频繁地对进行随机查找,C.,需要频繁地对进行删除和插入操作,D.,要求,L,存储密度高,第一部分 线性表,真题,2009.11,单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是,(60),。,(60)A,若在头结点中存入链表长度值，则求链表长度运算的时间,复杂度为,O(1),B,在链表的任何一个元素前后进行插入和删除操作可用一致,的方式进行处理,C,加入头结点后，代表链表的头指针不因为链表为空而改变,D,加入头结点后，在链表中进行查找运算的时间复杂度为,O(1),分值：,0 1,分 （每年）,分数比重：,0%10%,重要知识点：,1,、栈的结构特点,2,、队列的结构特点,3,、双端队列与循环队列,4,、串的存储结构、基本操作和模式匹配,第二部分,栈、队列和字符串,栈,特点：,后进先出的线性表,双向栈：,使两个栈共享一维数组,SMAXNUM,，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为,0,和,MAXNUM-1,，而它们的栈顶都往中间方向延伸的栈称为双向栈。,在一端进行插入和删除操作的线性表。,栈顶：允许插入和删除的一端。,栈底：不允许插入和删除的一端。,a,1,a,2,a,3,a,n-1,a,n,入栈,出栈,栈顶元素,栈底元素,概念：,第二部分,栈、队列和字符串,自由区,0,MAXNUM-1,lefttop,righttop,队列,特点：,先进先出的线性表,队列是只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。,队尾,(rear),：允许插入的一端叫做队尾。,队头,(front),：允许删除的一端叫做队头。,第二部分,栈、队列和字符串,a,1,a,2,a,3,a,n-1,a,n,入队列,出队列,队尾元素,队头元素,概念：,循环队列,特点：,1,、循环队列只针对,顺序队列,而言,2,、入队,rear=(rear+1)%MAXSIZE;,3,、出队,front=(front+1)%MAXSIZE;,4,、判队满：,front=(rear+1)%MAXSIZE,5,、判队空：,rear=front,6,、元素个数：,(rear-front+MAXSIZE)%MAXSIZE,(,采用,少用一个存储单元,的方法区分队空和队满,),第二部分,栈、队列和字符串,7,0,1,2,a,2,front,3,4,5,a,6,a,5,a,4,a,3,rear,6,把顺序队列所使用的存储空间臆造成一个逻辑上首尾相连的循环队列。,双端队列,分类：,1,、输出受限的双端队列（即一个端点允许插入和删除，另一个端点只,允许插入）；,2,、输入受限的双端队列（即一个端点允许插入和删除，另一个端点只,允许删除）。,3,、限定双端队列从某个端点插入的元素只能从该端点删除，则双端队,列就蜕变为两个栈底相邻接的栈了。,第二部分,栈、队列和字符串,想象自己在邮局里排队,当最终轮到自己时,邮局工作人员要求填写一张表格,于是自己站在旁边填表,工作人员为队列中下一个人服务,.,在填表后,工作人员将继续为自己服务,实质上自己又回到了队列的前端,.,有时可能会排在一个队列后面,随即因嫌队伍太长而离去,.,a,1,a,2,a,i,a,0,a,n-1,端,1,端,2,串的存储结构,第二部分,栈、队列和字符串,（1）,定长顺序串：,按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区,（2）,堆串：,可用函数malloc（）和函数free（）完成动态存储管,（3）,块链串：,用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,例：串值为,abcdef,的结点大小为,4,的链串,块链串注意事项：,为了提高存储密度，可使每个结点存放多个字符。,当结点大小大于,1,时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。,会给串的连接操作带来一定的方便，对模式匹配操作不方便。,虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。,a b c d,e f#,S,串的基本操作,难掌握的部分,第二部分,栈、队列和字符串,（1）,串比较：,StrCompare(S,T),若,S,T,，则返回值,0,；若,S,T,，则返回值,0,；若,S,T,，则返回值,0,。,例如：,StrCompare(data,state)0,（2）,串联接：,Concat(&T,S1,S2),用,T,返回由,S1,和,S2,联接而成的新串。,例如：,Concate(T,man,kind,),求得,T=,mankind,（3）,求子串,:,SubString(&Sub,S,pos,len),用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。,例如：SubString(sub,commander,4,3)求得 sub=,man,；,（,4,）串定位：,Index(S,T,pos),若主串 S 中存在和串 T 值相同的子串,则返回它在主串 S 中第pos个字符之后第一次出现的位置；否则函数值为0。,假设 S=,abcaabcaaabc,T=,bca,Index(S,T,1)=2；Index(S,T,3)=6；,（,5,）串替换：,Replace(&S,T,V),用V替换主串S中出现的所有与（模式串）T 相等的不重叠的子串,假设 S=,abcaabcaaabca,，T=,bca,，,若 V=,x,，,则经置换后得到,S=,axaxaax,串的模式匹配,第二部分,栈、队列和字符串,（1）,BF,算法：,从主串,S,的第一个字符开始和模式,T,的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串,S,的第二个字符开始和模式,T,的第一个字符进行比较；重复上述过程，直到,T,中的字符全部比较完毕，则说明本趟匹配成功；或,S,中字符全部比较完，则说明匹配失败。,（2）,KMP,算法：,从主串,S,的第一个字符开始和模式,T,的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，主串当前位置字符和模式,T,的上次匹配失败的字符的,next,数组值所对应的字符开始进行比较；重复上述过程，直到,T,中的字符全部比较完毕，则说明本趟匹配成功；或,S,中字符全部比较完，则说明匹配失败。,串的模式匹配,第二部分,栈、队列和字符串,KMP,算法的重点,（1）,next,数组：,（2）,nextval,数组：,0 1 0 2 0 1 0 4 2 2,nextvalj,0 1 1 2 1 2 3 4 2 2,nextj,a b a c a b a a a d,T,串,1 2 3 4 5 6 7 8 9,10,j,真题,200705,输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有,8,、,1,、,4,、,2,依次进入输入受限的双端队列，则得不到输出序列（,57,）。,（,57,）,A.2,、,8,、,1,、,4,B.1,、,4,、,8,、,2,C.4,、,2,、,1,、,8,D.2,、,1,、,4,、,8,第二部分,栈、队列和字符串,真题,200711,设栈,S,和队列,Q,的初始状态为空，元素按照,a,、,b,、,c,、,d,、,e,的次序进入栈,S,，当一个元素从栈中出来后立即进入队列,Q,。若队列的输出元素序列是,c,、,d,、,b,、,a,、,e,，则元素的出栈顺序是（,58,），栈,S,的容量至少为（,59,）。,（,58,）,A.a,、,b,、,c,、,d,、,e B.e,、,d,、,c,、,b,、,a,C.c,、,d,、,b,、,a,、,e D.e,、,a,、,b,、,d,、,c,（,59,）,A.2 B.3 C.4 D.5,第二部分,栈、队列和字符串,真题,200905,下面关于栈和队列的叙述，错误的是（,60,）。,（,60,）,A.,栈和队列都是操作受限的线性表,B.,队列采用单循环链表存储时，只需设置队尾指针,就可使入队和出队操作的时间复杂度都为,O(1),C.,若队列的数据规模,n,可以确定，则采用顺序存储,结构比链式存储结构效率更高,D.,利用两个栈可以模拟一个队列的操作，反之亦可,第二部分,栈、队列和字符串,真题,200911,对于长度为,m,（,m1,）的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是（,61,）。,(61)A,若入栈和入队的序列相同，则出栈序列和出队序,列可能相同,B,若入栈和入队的序列相同，则出栈序列和出队序,列可以互为逆序,C,入队序列与出队序列关系为,1:1,，而入栈序列与出,栈序列关系是,l:n(n1),D,入栈序列与出栈序列关系为,1:1,，而入队序列与出,队序列关系是,l:n(n1),第二部分,栈、队列和字符串,真题,200911,字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则串比较、求子串、串连接、串替换等串的基本运算中，（,62,）。,（,62,）,A,进行串的比较运算最不方便,B,进行求子串运算最不方便,C,进行串连接最不方便,D,进行串替换最不方便,第二部分,栈、队列和字符串,分值：,0 1,分 （每年）,分数比重：,0%10%,重要知识点：,1,、数组的地址计算,2,、数组的压缩存储,3,、广义表的表示,4,、广义表的表头、表尾,第三部分,数组与广义表,数组,特点：,1.,数组中的数据元素具有相同的数据类型。,2.,数组是一种随机存取结构，只要给定一组下标，就可以访问与其对应的数组元素。,3.,数组中的元素个数是固定的。,基本操作,存取、修改,对于数组,A,，一旦给定其维数,n,及各维长度,bi,（,1in,），则该数组中元素的个数和元素之间的关系就不再发生变化了，既不可以对数组做插入和删除操作，也不涉及移动元素操作。,第三部分,数组与广义表,多维数组和广义表是对线性表的扩展,线性表中的数据元素本身又是一个多层次的线性表。,数组的地址计算,第三部分,数组与广义表,Loc,a,ij,=,Loc,a,00,+(,n,i,+,j,),size,a,00,a,02,a,03,a,0j,a,0,n-1,a,10,a,11,a,12,a,1j,a,1,n-1,a,20,a,21,a,22,a,2j,a,2,n-1,Amn=,a,i,0,a,i,1,a,ij,a,m-1,0,a,m-1,1,a,m-1,2,a,m-1,n-1,Loca,ij,=,Loca,00,+(m,j+i),size,行序为主序：,列序为主序：,a,11,a,21,a,22,.,a,ij,.,a,nn,Loci,j=,1,2,3,.,n*(n+1)/2,a,11,a,12,a,13,a,1n,a,21,a,22,a,23,a,2n,a,31,a,32,a,33,a,3n,A=,a,n1,a,n2,a,n3,a,nn,Loc i,j=,Loc1,1,+,i,(i-1)/2+j-1,当,i,j,时,Loc1,1+j,(j-1)/2+i-1,当,i j,时,对于对称矩阵，因其元素满足,a,ij,=a,ji,，我们可以为每一对相等的元素分配一个存储空间，即只存下三角（或上三角）矩阵，从而将,n,2,个元素压缩到,n(n+1)/2,个空间中。,一维数组,A,中对应的下标为：,数组的压缩存储,第三部分,数组与广义表,对称矩阵：,a,ij,=a,ji,带状矩阵：,在矩阵,A,中，所有的非零元素都集中在以主对角线为中心的带状区域中。最常见的是三对角带状矩阵。,特点,:,i=1,j=1,2;,当,1i1,则,i,的双亲结点为,i/2,(2),若,2*i n,则,i,无左孩子,若,2*in,则,i,结点的左孩子结点为,2*i,(3),若,2*i+1 n,则,i,无右孩子,若,2*i+1n,则,i,的右孩子结点为,2*i+1,第四部分,树与二叉树,（53）,它是根据问题中的条件将可能的情况一一列举应用：顺序查找、简单选择排序、冒泡排序,1、循环队列只针对顺序队列而言,_(47)_排序是稳定的。,4、树与二叉树的转换,ai,0 ai,1 aij,第六部分 排序与查找,折半插入排序：以折半查找和直接插入排序两种方法结合起来实现排序；,由权值为 29、12、15、6、23 的五个叶子结点构造的哈夫曼树为（64），其带权路径长度为（65）。,从表中任一结点出发都能遍历整个链,第二部分 栈、队列和字符串,以 A 为根的子二叉树变为不平衡,插入或删除运算不方便，需要移动大量的结点，其效率较低；,二叉树的遍历,第四部分,树与二叉树,A,B,C,D,K,F,G,I,J,E,H,前序遍历序列,:,A,B,D,K,J,G,C,F,I,E,H,中序遍历序列,:,D,B,G,J,K,A,F,I,E,C,H,后序遍历序列,:,D,G,J,K,B,E,I,F,H,C,A,按层次遍历序列,:,A,B,C,D,K,F,H,J,I,G,E,例：,已知结点的先序序列和中序序列,先序序列：,A B D E J C F I G,中序序列：,D B J E A F I C G,则可按上述分解求得整棵二叉树。,A,D,C,I,F,G,J,B,E,第四部分,树与二叉树,例：,已知结点的中序序列和后序序列,中序序列：,A B C E F G H D,后序序列：,A B F H G E D C,则可按上述分解求得整棵二叉树。,C,A,D,G,E,H,F,B,线索二叉树,第四部分,树与二叉树,一,.,什么是线索二叉树,二,.,线索二叉树的构造,利用二叉链表中空的指针域指出,结点在,遍历序列,中的直接前驱和直接后继,;,这些指向前驱和后继的指针称为线索,加了线索的二叉树称为线索二叉树,.,利用结点的空的左指针域存放该结点的直接前驱的地址,空的右指针域存放该结点直接后继的地址,;,而非空的指针域仍然存放结点的左孩子或右孩子的地址,.,注：每棵二叉树都可以构造先序、中序和后序三种线索二叉树。,树、森林与二叉树的转换,第四部分,树与二叉树,树转换成二叉树：,1,、,树中所有相邻兄弟之间加一条连线。,2,、,对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。,森林转换为二叉树的方法为：,1,、将森林中的每棵树转换成相应的二叉树。,2,、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，即为由森林转换得到的二叉树。,A,B,E,C,D,F,G,H,A,B,C,D,E,F,I,J,G,H,带权路径长度：,设二叉树有,n,个带权值的叶子结点，定义从二叉树的,根结点,到二叉树中所有,叶子结点,的路径长度,l,i,与相应叶子结点权值,w,i,的乘积之和称作该二叉树的带权路径长度。,T,WPL(T)=72+52+23+43+92=60,7,5,2,4,9,A,C,B,I,G,F,D,E,H,WPL=,哈夫曼树,第四部分,树与二叉树,5,2,3,10,5,15,7,8,25,1,1,1,1,0,0,0,0,(011),(010),(10),(11),(00),字符：,s t a e c,字符出现的次数：,3 8 7 5 2,c:010,s:011,e:00,a:10,t:11,哈夫曼编码,第四部分,树与二叉树,真题,200505,表达式a*(b+c)-d的后缀表达形式为_(39)_。,（39）A.abcd*+-B.abc+*d-,C.abc*+d-D.-+*abcd,若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为_(40)_。,（40）A.DEBAFC B.DEFBCA,C.DEBCFA D.DEBFCA,第四部分,树与二叉树,真题,200511,已知某二叉树的中序、层序序列分别为,DBAFCE,、,FDEBCA,，则该二叉树的后序序列为,_(38)_,。,(38)A.BCDEAF,B.ABDCEF,C.DBACEF,D.DABECF,在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有,n,个结点，采用三叉链表存储时，每个结点的数据域需要,d,个字节，每个指针域占用,4,个字节，若采用顺序存储，则最后一个结点下标为,k,（起始下标为,1,）,那么,_(39)_,时采用顺序存储更节省空间。,(39)A.d12n/(k-n),C.d12n/(k+n),第四部分,树与二叉树,真题,200605,与逆波兰式,ab+-c*d-,对应的中缀表达式是（,45,）。,（,45,）,A,a-b-c*d,B,-(a+b)*c-d,C,-a+b*c-d,D,(a+b)*(-c-d),为便于存储和处理一般树结构形式的信息，常采用孩子兄弟表示法将其转换成二叉树（左子关系表示父子、右子关系表示兄弟），与下图所示的树对应的二叉树是（,53,）。,（,53,）,第四部分,树与二叉树,真题,200612,“X=(A+B)(C-D/E)”,的后缀式表示为（,20,）,（,20,）,A.XAB+CDE/-=B.XAB+C-DE/=,C.XAB+CDE-/=D.XAB+CD-E/=,200705,已知某二叉树的中序序列为,CBDAEFI,、先序序列为,ABCDEFI,，则该二叉树的高度为（,58,）。,（,58,）,A.2 B.3 C.4 D.5,第四部分,树与二叉树,真题,200705,由权值为 29、12、15、6、23 的五个叶子结点构造的哈夫曼树为（64），其带权路径长度为（65）。,第四部分,树与二叉树,真题,200805,若将某有序树,T,转换为二叉树,T1,，则,T,中结点的后,(,根,),序序列就是,T1,中结点的,_(59)_,遍历序列。例如，下图,(a),所示的有序树转化为二叉树后如图,(b),所示。,(59)A.,先序,B.,中序,C.,后序,D.,层序,第四部分,树与二叉树,真题,200811,一个具有,m,个结点的二叉树，其二叉链表结点（左、右孩子指针分别用,left,和,right,表示）中的空指针总数必定为（,57,）个。为形成中序（先序、后序）线索二叉树，现对该二叉链表所有结点进行如下操作：若结点,p,的左孩子指针为空，则将该左指针改为指向,p,在中序（先序、后序）遍历序列的前驱结点；若,p,的右孩子指针为空，则将该右指针改为指向,p,在中序（先序、后序）遍历序列的后继结点。假设指针,s,指向中序（先序、后序）线索二叉树中的某结点，则（,58,）。,（,57,）,A.m+2 B.m+1 C.m D.m-1,（,58,）,A.s,right,指向的结点一定是,s,所指结点的直接后继结点,B.s,left,指向的结点一定是,s,所指结点的直接前驱结点,C.,从,s,所指结点出发的,right,链可能构成环,D.s,所指结点的,left,和,right,指针一定指向不同的结点,第四部分,树与二叉树,真题,200905,下面关于二叉树的叙述，正确的是（,61,）。,（,61,）,A.,完全二叉树的高度,h,与其结点数,n,之间存在确定,的关系,B.,在二叉树的顺序存储和链式存储结构中，完全,二叉树更适合采用链式存储结构,C.,完全二叉树中一定不存在度为,1,的结点,D.,完全二叉树中必定有偶数个叶子结点,第四部分,树与二叉树,真题,200911,已知一个二叉树的先序遍历序列为、，中序遍历序列为、，则该二叉树的后序遍历序列为（57）。对于任意一棵二叉树，叙述错误的是（58）。,（57）A、B、,C、D、,（58）,A由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列,B由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列,C由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列,D由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列,第四部分,树与二叉树,分值：,0 5,分 （每年）,分数比重：,6%,重要知识点：,1,、图的基本概念和存储结构,2,、图的遍历,3,、拓扑排序和最小生成树,4,、关键路径,5,、最短路径,第五部分,图,图的基本概念和存储结构,图的基本概念：,无向图、有向图、无向完全图、有向完全图、稀疏图、稠密图、子图、有向图与无向图的顶点的度、网、回路和环、路径长度、简单路径、简单回路、连通图、连通分量、强连通图、强连通分量。,图的存储结构,邻接矩阵(数组)表示法；邻接表；十字链表；,第五部分,图,B,A,C,D,G1,B,A,D,E,G2,C,图的遍历,深度优先搜索：,是指按照深度方向搜索，它类似于树的先根遍历。,广度优先搜索,：,是指按照广度方向搜索，它类似于树的按层次遍历。,第五部分,图,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,v,1,v,2,v,4,v,7,v,9,v,5,v,3,v,6,v,8,B,A,E,D,C,A B C D E,v,1,v,2,v,3,v,4,v,5,v,9,v,6,v,8,v,7,A B C E D,拓扑排序,拓扑排序,将一个有向图中的所有结点排成一个序列，使得图中所有结点应存在的前驱和后继关系都能在队列中体现（前驱在前，后继在后）。,过程,从AOV网中选择一个没有前驱的顶点并且输出；,从AOV网中删去该顶点并且删去所有以该顶点为尾的弧；,重复上述两步，直到全部顶点都被输出;,第五部分,图,C,1,C,2,C,3,C,4,C,6,C,5,C,7,拓扑序列：,C,1,C,2,C,3,C,4,C,5,C,6,C,7,最小生成树,概念,生成树是连通图上的一个极小连通子图。最小生成树是一个连通网中所有生成树中各边权值之和最小的生成树。,最小生成树的算法：,1,、普里姆算法,2,、克鲁斯卡尔算法,第五部分,图,a,b,d,c,e,f,6,1,5,5,5,4,2,6,6,3,a,b,d,c,e,f,1,5,3,4,2,a,b,d,c,e,f,1,5,3,2,5,5,4,关键路径,概念,从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键路径上的活动叫关键活动。,关键路径的求法：,事件的最早发生时间,vek,事件的最迟发生时间,vlk,活动的最早开始时间,ei,活动的最晚开始时间,li,第五部分,图,v,2,v,1,v,3,v,4,v,5,v,8,v,6,v,7,v,9,a,1,=6,a,4,=1,a,7,=9,a,10,=2,a,11,=4,a,8,=7,a,9,=4,a,5,=1,a,6,=2,a,3,=5,a,2,=4,第五部分,图,v,2,v,1,v,3,v,4,v,5,v,8,v,6,v,7,v,9,a,1,=6,a,4,=1,a,7,=9,a,10,=2,a,11,=4,a,8,=7,a,9,=4,a,5,=1,a,6,=2,a,3,=5,a,2,=4,vek,v,2,v,7,v,6,v,5,v,4,v,1,v,3,v,9,v,8,0,6,4,5,7,7,16,14,18,a,2,a,7,a,6,a,5,a,4,a,1,a,3,a,9,a,8,ei,0,0,0,6,4,5,7,7,7,a,10,a,11,16,14,依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树,对于n个元素的关键字序列k1,k 2,.,递归,第二部分 栈、队列和字符串,（3）求子串:SubString(&Sub,S,pos,len),例如:D=(E,F)=(a,(b,c)，F),B快速排序算法在最坏情况下的时间复杂度为O(nlgn),1、树和二叉树的定义,例如：Concate(T,man,kind)求得 T=mankind ,表示广义表F长度为2，两个元素分别是原子项a和子表F。,以下关于单链表头结点的叙述中，错误的是(60)。,必需为表示结点间的逻辑关系而增加额外的存储空间；,B进行广度优先遍历运算所消耗的时间与采用哪一种,若2*in,则 i 结点的左孩子结点为2*i,5，设每个元素占 1 个存储单元，且以列为主序存储，则元素 a2,2相对于数组空间起始地址的偏移量是（55）。,(61)A若入栈和入队的序列相同，则出栈序列和出队序,第五部分,图,v,2,v,1,v,3,v,4,v,5,v,8,v,6,v,7,v,9,a,1,=6,a,4,=1,a,7,=9,a,10,=2,a,11,=4,a,8,=7,a,9,=4,a,5,=1,a,6,=2,a,3,=5,a,2,=4,li,10,7,7,8,6,6,3,2,0,16,14,a,2,a,7,a,6,a,5,a,4,a,1,a,3,a,9,a,8,a,10,a,11,v,2,v,7,v,6,v,5,v,4,v,1,v,3,v,9,v,8,vlk,18,14,16,10,7,8,6,6,0,最短路径,分类,1、求图中的一个结点到其他结点的最短路径。,2、求图中任意两点间的最短路径。,最短路径的求法：,迪杰斯特拉,(Dijkstra),算法,Floyd,算法,第五部分,图,B,A,E,D,C,10,50,30,10,100,20,60,S=A,B,D,C,E,AB:(A,B)10,AC,:(A,D,C)50,AD:,(A,D)30,AE:,(A,D,C,E)60,B,A,E,D,C,10,50,30,10,100,20,60,最短路径,分类,1、求图中的一个结点到其他结点的最短路径。,2、求图中任意两点间的最短路径。,最短路径的求法：,迪杰斯特拉,(Dijkstra),算法,Floyd,算法,第五部分,图,a,b,d,5,3,8,6,3,c,1,2,2,真题,200505,无向图中一个顶点的度是指图中,_(41)_,。,（,41,）,A.,通过该顶点的简单路径数,B.,通过该顶点的回路数,C.,与该顶点相邻的顶点数,D.,与该顶点连通的顶点数,一个具有,n(n0),个顶点的连通无向图至少有,(49),条边。,（,49,）,A.n+1,B.n,C.n+2,D.n-1,第五部分,图,真题,200511,在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从,A,到,J,的关键路径是,(16),，关键路径长度是,(17),，从,E,开始的活动启动的最早时间是,(18),。,(16)A.ABEGJ,B.ADFHJ,C.ACFGJ,D.ADFIJ,(17)A.22,B.49,C.19,D.35,(18)A.10,B.12,C.13,D.15,第五部分,图,真题,200511,简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个节点。若无向图G有n个节点，其邻接矩阵为A1.n,1.n,且压缩存储在B1.k中，则k的值至少为_(40)_。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B_(41)_中。,(40)A.n(n+1)/2 B.n,2,/2,C.(n-1)(n+1)/2 D.n(n-1)/2,(41)A.18 B.19 C.20D.21,第五部分,图,真题,200605,拓扑序列是无环有向图中所有项点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，（,52,）为下图所示有向图的一个拓扑序列。,（,52,）,A,1 2 3 4 5 6 7,B,1 5 2 6 3 7 4,C,5 1 2 6 3 4 7,D,5 1 2 3 7 6 4,第五部分,图,真题,200611,求单源点最短路径的迪杰斯特拉（Dijkstra）算法是按（57）的顺序求源点到各顶点的最短路径的。,（57）A.路径长度递减 B.路径长度递增,C.顶点编号递减 D.顶点编号递增,第五部分,图,真题,200705,某工程计划如下图所示，各个作业所需的天数如下表所示，设该工程从第 0 天开工，则该工程的最短工期是（59）天，作业 J 最迟应在第（60）天开工。,第五部分,图,真题,200711,拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点,vi,到,vj,有一条路径，则在该线性序列中，顶点,vi,必然在顶点,vj,之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定（,57,）。,（,57,）,A.,包含回路,B.,是强连通图,C.,是完全图,D.,是有向树,200805,设一个包含,N,个顶点、,E,条边的简单有向图采用邻接矩阵存储结构,(,矩阵元素,Aij,等于,1/0,分别表示顶点,i,与顶点,j,之间有,/,无弧,),，则该矩阵的元素数目为,_(60)_,，其中非零元素数目为,_(61)_,。,(60)A.E2 B.N2 C.N2-E2 D.N2+E2,(61)A.N B.N+E C.E D.NE,第五部分,图,真题,200811,（59）的邻接矩阵是一个对称矩阵。,（59）A.无向图 B.AOV 网 C.AOE 网 D.有向图,具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（63）。,（63）A.O(n,2,)B.O(e,2,)C.O(n*e)D.O(n+e),第五部分,图,真题,200905,下面关于图（网）的叙述，正确的是（58）。,（58）A.连通无向网的最小生成树中，顶点数恰好比边,数多1,B.若有向图是强连通的，则其边数至少是顶点数,的2倍,C.可以采用AOV 网估算工程的工期,D.关键路径是AOE 网中源点至汇点的最短路径,第五部分,图,真题,200911,邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有n个顶点、e条边的图，（59）。,（59）A进行深度优先遍历运算所消耗的时间与采用哪一种,存储结构无关,B进行广度优先遍历运算所消耗的时间与采用哪一种,存储结构无关,C采用邻接表表示图时，查找所有顶点的邻接顶点的,时间复杂度为O(n*e),D采用邻接矩阵表示图时，查找所有顶点的邻接顶点,的时间复杂度为O(n,2,),第五部分,图,分值：,5 15,分 （每年）,分数比重：,10%,重要知识点：,1,、静态表查找,顺序查找、折半查找,2,、动态表查找,二叉排序树、平衡二叉树,3,、哈希表,4,、插入类排序,5,、交换类排序,6,、选择类排序,7,、分配类排序,第六部分,排序与查找,查找,基本概念：,静态查找：不涉及插入和删除操作的查找。,动态查找：涉及插入和删除操作的查找。,平均查找长度：将查找算法进行的关键码的比较次数的数学期望,值定义为平均查找长度。计算公式为：,其中：n：问题规模，查找集合中的记录个数；,p,i,：查找第i