2022年数据结构复习成果收集 .pdf

《2022年数据结构复习成果收集 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构复习成果收集 .pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章图基本概念:1).无向图:在一个图中,如果任意两个顶点构成(vi,vj)属于 E 是无序的,即顶点之间的连线是没有方向的,则称该图是无向图.v1v2;v1,v2称为邻接点2).有向图:v1 v2:其中 v1 是弧尾;为弧;v2为弧头3).无向完全图:在一个无向图中,如果任意两顶点都有一条线直接相连,则称该图为无向完全图;在一个含有n 个顶点的无向完全图中,有 n(n-1)/2条边4).有向完全图:任意两顶点之间都有方向相反的两条弧相连接,有 n(n-1)条弧5).顶点的度:无向:指附于某顶点的边数.有向:入度 ID:出去的弧出度 OD:进去的弧6).简单路径:序列中除起点和重点外其余顶点

2、不重复出现的路径称为简单路径.7).子图:对于图 G=(V,E),G=(V,E),若存在 V是 V的子集,E是 E 的子集,且 E中的边所关联的顶点均为V中,则称图 G 是 G的一个子图.连通的:在无向图中,如果从一个顶点vi 到另一个顶点vj(i!=j)有路径,则称顶点 vi 到 vj 是连通的,8)(无向).连通图:如果图中任意两顶点都是连通的,则称该图是连通图.一个连通图的生成树是一个极小连通子图,它含有图中全部的顶点,但只有足以构成一棵树的n-1 条边。连通分量:无向图的极大连通子图称为连通分量名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 21 页 -9(有向).强连通

3、图:对于有向图来说,若图中任意一对顶点vi 和 vj(i!=j)均有从一个顶点vi 到另一个顶点vj 有路径,也有从 vj 到 vi 的路径,则称该有向图是强连通的.强连通分量:有向图中的极大强连通子图称做有向图的强连通分量/选择题1设无向图的顶点个数为n，则该图最多有（B）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En2 分析:无向图中顶点数确定,边数最多的是完全无向图.根据概念 3 完全无向图的性质得:有有 n(n-1)/2条边2一个 n 个顶点的连通无向图，其边的个数至少为（A ）。An-1 Bn Cn+1 Dnlogn；分析:根据连通图的定义:任意两顶点都是连通的

4、；可知连通无向图的边个数至少为n-1,3一个有 n 个结点的图，最少有（B）个连通分量，最多有（D ）个连通分量。A0 B1 Cn-1 Dn 分析:连通分量:无向图的极大连通子图称为连通分量,若这 n 个结点都是连通的,则此时连通分量是最少的,为 1 个(n 个顶点构成一个连通分量).当这 n个顶点没有一条边连接,则此时连通分量是最多的,为 n 个(n 个顶点各自组成一个连通分量)4在一个无向图中，所有顶点的度数之和等于所有边数（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A1/2 B2 C1 D4 分析:名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，

5、共 21 页 -无向图中,一条边连接了两个顶点,对于这两个顶点来说,由于这条边的存在,所以这两个顶点的度都自增1,总度数增加2,所以无向图中,一条边可以创造两个度.所以边永远是度的两倍.有向图中,一条弧连接两个顶点,对于指向的顶点来说,入度加 1,对于指出的顶点来说,出度加 1,所以有向图中,一条弧可以增加1 个入度,增加 1 个出度,所以有向图中,入度之和和出度之和和弧数是1:1:1的关系;5下列哪一种图的邻接矩阵是对称矩阵？（B ）A有向图 B无向图 CAOV网 DAOE 网分析:/c7-1.h 图的数组(邻接矩阵)存储结构(见图 7_1)#define INFINITY INT_MAX/

6、用整型最大值代替#define MAX_VERTEX_NUM 26/最大顶点个数enum GraphKindDG,DN,UDG,UDN;/有向图,有向网,无向图,无向网 typedef struct VRType adj;/顶点关系类型。对无权图，/用 1(是)或 0(否)表示相邻否；/对带权图，则为权值InfoType*info;/该弧相关信息的指针(可无)ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/二维数组struct MGraph VertexType vexsMAX_VERTEX_NUM;/顶点向量名师资料总结-精品资料欢迎下载-名师精

7、心整理-第 3 页，共 21 页 -AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/图的当前顶点数和弧数GraphKind kind;/图的种类标志;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 21 页 -1)如图 7-2 所示,无向图邻接矩阵中,第 i行的值为1 表示有由vi发出的弧,比如01这个点为 1 表示 v1 和 v2 是有边相连的,由于无向图中发向和被发向是相对的,所以10这个点得值肯定也为1,所以就会出现以对角线对称的情况,但图7-210并不是1,这是由于无向图的邻接矩阵的对称性,则可采用压缩存储的方式只存入矩阵的下三角(或上三角)

8、元素.这里就只是存入了上三角.2)借助于邻接矩阵容易判断任意两个顶点之间是否有边(或弧)相连,并容易求得各个顶点的度.对于无向图,顶点 vi 的度是邻接矩阵中第i 行(或第 i 列)的元素之和,即:n-1 TD(vi)=Aij(n=MAX_VERTEX_NUM)j=0 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 21 页 -3)对于有向图，第i 行的元素之和为顶点vi的出度OD(vi)，第 j 列的元素之和为顶点vj的入度ID(vj)。网的邻接矩阵可定义为AOV-网:用顶点表示活动,用弧表示活动间的优先关系的有向图称为顶点表示活动的图,简称 AOV-网.(用于拓扑排序)AOE

9、-网:AOE-网是一个带权的有向无环图,其中,顶点表示事件,弧表示活动,权表示活动持续的时间,通常,AOE-网可用来评估工程的完成时间(关键路径)6当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi 的度是（B）。A B C D+分析:邻接矩阵请查看选择题第4 题;个人觉得问的是顶点vi的度;说明应该是个无向图(有向图应该问出度和入度),而无向图的度数为第i 行非零元的个数或第i 列非零元的个数,无向图的度数:第 i 行非零元的个数或第i 列非零元的个数.有向图的度数:出度:第 i 行非零元个数,入度:第 i 列非零元的个数.7下面哪一方法可以判断出一个有向图是否有环（回路）：(B)A深度优先遍

10、历 B.拓扑排序 C.求最短路径 D.广度优先遍历分析:拓扑排序的 作用:判断能不能顺利完工,有没有环.拓扑排序:简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义：nijiA1,n1jj,iAniijA1,nijiA1,n1ji,jA名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 21 页 -偏序关系:若集合 X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。全序关系:设 R是集合 X上的偏序,如果对每个x,y 属于 X必有 xRy 或 yRx，则称 R是集合 X 上的全序关系。注意：若将图中顶点按

11、拓扑次序排成一行，则图中所有的有向边均是从左指向右的。若图中存在有向环，则不可能使顶点满足拓扑次序。一个 DAG 的拓扑序列通常表示某种方案切实可行。拓扑排序的步骤:1).在有向图中选一个没有前驱的顶点且输出之.2).从图中删除该顶点和所有以它为尾的弧.重复上述两步,直到全部顶点均已输出,或者当前图中不存在无前驱的顶点为止,后一种情况则说明有向图中存在环.8.在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为(B )。A.O(n)B.O(n+e)C.O(n2)D.O(n3)分析:只要记住如果用邻接矩阵,那么时间复杂度就是0(n2),如果用邻接表,时间复杂度就是0(n+e);邻接

12、表:邻接表是图的一种链式存储结构;具体请看书163 页/c7-2.h 图的邻接表存储结构(见图7_16)#define MAX_VERTEX_NUM 20 enum GraphKindDG,DN,UDG,UDN;/有向图,有向网,无向图,无向网 struct ArcNode 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 21 页 -int adjvex;/该弧所指向的顶点的位置ArcNode*nextarc;/指向下一条弧的指针InfoType*info;/网的权值指针;/表结点typedef struct VertexType data;/顶点信息ArcNode*firsta

13、rc;/第一个表结点的地址，指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;/头结点struct ALGraph AdjList vertices;/顶点表int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志;用我的话来说:ALGraph 是用来存放图的总信息,比如顶点数和弧数和图的种类并且指向顶点表(AdjListMAX_VERTEX_NUM),而 VNode是用来存放顶点的信息;并用*firstarc指向第一条依附于该顶点的弧的指针,而 ArcNode 是用来存放依附于某个顶点的弧所指向的顶点的位置并且能够指向下一

14、个弧的指针.具体请看下面这张图和上面代码中的注释.名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 21 页 -最小生成树:构造连通网的最小代价生成树.求最小生成树的 普里姆算法 (效率不高,但应试解题快):假设 N=(V,E)是连接网,TE 是 N上最小生成树中边的集合,算法从 U=u0(u0属于 V),TE=开始,重复执行下列操作,在所有 u属于 U,v 属于 V-U 的边(u,v)属于 E 中查找一条代价最小的边(u0,v0)并入集合 TE,同时 v0 并入 U,直到U=V 为止.此时 TE中必有 n-1 条边,则 T=(V,TE)为 N的最小生成树.个人理解:就是先找到一条

15、最短的边,把这条边的两个顶点连起来,再找 与这两个顶点相连 的边中最短的一条,再把他们连接起来(这样就找到了3 个顶点),再找与这 3 个顶点相连的边中最短的一条,再把他们连起来,直到所有顶点都被连起来为止.只要注意不要连成环就行.9.求解最短路径的Floyd 算法的时间复杂度为(D )。AO（n）B.O（n+c）C.O（n*n）D.O（n*n*n）分析:求解最短路径有两个算法:一个是迪杰斯算法,另一个就是Floyd 弗洛伊德算法;两者的时间复杂度都是O(n3)名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 21 页 -10若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该

16、图的拓扑有序序列（A）。A存在 B 不存在分析:主对角线以下的元素均为零,说明这个有向图图没有环(如果下面有元素,且以主对角线对称的位置也有元素,则表示有环),没有环则说明拓扑有序序列存在,拓扑排序的内容请查看选择题第7 题;11一个有向无环图的拓扑排序序列（B ）是唯一的。A一定 B不一定分析:拓扑排序的性质请看选择题第7 题;同一时刻没有前驱的结点数可能不止一个,这是拓扑排序的序列解释不唯一的了.12.在有向图 G的拓扑序列中，若顶点Vi 在顶点 Vj 之前，则下列情形不可能出现的是（D ）。AG中有弧 BG中有一条从Vi 到 Vj 的路径CG中没有弧 DG中有一条从Vj 到 Vi 的路径

17、分析:若 G中有一条从Vj 到 Vi 的路径,那么就会构成一个环了,那就不是拓扑序列了.13.在用邻接表 表示图时，拓扑排序算法时间复杂度为(B )。A.O(n)B.O(ne)C.O(n*n)D.O(n*n*n)分析:只要记住如果用邻接矩阵,那么时间复杂度就是0(n2),如果用邻接表,时间复杂度就是0(n+e);邻接表的具体信息请查看选择题第8 题14.关键路径是事件结点网络中（A ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 21 页 -C最长回路 D最短回路分析:关键路径:由于 AOE-网中又些活动可以并行地进行,所以

18、完成工程的最短时间是从开始点到完成点的最大路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目),路径长度最长的路径叫做关键路径15下列关于AOE网的叙述中，不正确的是（B ）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成分析:关键路径可能有多条，所以不是任何一个关键活动提前完成，那么整个工程将会提前完成判断题1.有 e 条边的无向图，在邻接表中有e 个结点。（错）分析:无向图在邻接表中有2e 个结点(a 指向 b,同

19、时 b也会指向a);有向图中有 e 个结点(弧是单向的);2.有向图的邻接矩阵是对称的。（错）分析:无向图的邻接矩阵才是对称的.1 任何无向图都存在生成树。（错）分析:名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 21 页 -生成树:生成树是一个连通图G的一个 极小的连通子图.包含图 G的所有顶点,但只有 n-1 条边,并且是连通的.生成树可由遍历过程中所经过的边组成,深度优先遍历得到的生成树称为深度优先生成树；广度优先遍历得到的生成树称为广度优先生成树。连通图得到的是生成树;不连通图得到的是生成森林;4.不同的求最小生成树的方法最后得到的生成树是相同的.（错）分析:请查看选

20、择题第8 题;最小生成树并不是唯一的,所以即使是同一种求最小生成树的方法最后得到的生成树也是不同的;5.有环图也能进行拓扑排序。（错）6.关键路径是AOE网中从源点到终点的最长路径。（对）填空题1 具有 10 个顶点的无向图，边的总数最多为 45 。分析:无向图:n(n-1)/2 有向图:n(n-1)2.在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 n 条弧。分析:构成一个环;3.n 个顶点的 连通无向图，其边的条数至少为 n-1 。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 21 页 -分析:连通图:如果图中任意两顶点都是连通的,则称该图是连通图.

21、至少 n-1 条边2 N 个顶点的 连通图 用邻接矩阵表示时,该矩阵至少有无向图：2(n-1)；有向图：n 个非零元素。分析:这题就是问N个顶点的连通图有多少条边的问题:无向图至少有n-1 条边;有向图至少有n 条边而邻接矩阵中无向图是对称的,所以矩阵中非零元素:无向图至少有2(n-1)个;有向图至少有n 个5构造连通网最小生成树的两个典型算法是普里姆算法、克鲁斯卡尔算法。分析:求最小生成树的普里姆算法请查看选择题第8 题6.有一个用于n 个顶点连通带权无向图的算法描述如下：（1）设集合T1 与 T2，初始均为空；（2）在连通图上任选一点加入T1；（3）以下步骤重复n-1 次：a.在 i 属于

22、 T1，j 不属于 T1 的边中选最小权的边；b.该边加入 T2。上述算法完成后，T2中共有 n-1 条边，该算法称普里姆算法算法，T2 中的边构成图的最小生成树。分析:求最小生成树的普里姆算法请查看选择题第8 题a.在 i 属于 T1，j 不属于 T1 的边中选最小权的边；指的是与T1相连的边中权值最小的那条边7AOV网中,顶点表示活动 ,弧表示活动间的优先关系。AOE网中,顶点表示事件 ,弧表示活动。8.当一个 AOV网用邻接表表示时，可按下列方法进行拓扑排序。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 21 页 -（1）查邻接表中入度为零的顶点，并进栈；（2）若栈不空

23、，则输出栈顶元素Vj，并退栈；查Vj 的直接后继 Vk，对 Vk入度处理，处理方法是 Vk 的入度减1，如为零则进栈；（3）若栈空时，输出顶点数小于图的顶点数，说明有环路，否则拓扑排序完成。分析:拓扑排序的步骤 请查看选择题第7 题算法应用题1、对 n 个顶点的 无向图，采用 邻接矩阵 表示，如何判别下列有关问题 1）图中有多少条边？2）任意两个顶点i 和 j 是否有边相连？3）任意一个顶点的度是多少？分析:邻接矩阵请查看选择题第5 题1).矩阵中非零元的个数除以2(无向图是对称的);2).查看第 i 行 j 列或则第 j 行 i 列是否为 1(有边相连则为1,没有则为 0);3).该顶点所在

24、行或列所有非零元的个数;2设 G=(V,E)以邻接表存储，试写出深度优先和广度优先序列。123451341241232423455名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 21 页 -分析:第一步:如果邻接表中 顺序是按从小到大排的,可以先化成邻接矩阵清楚些:顶点v1 v2 v3 v4 v5 v1 0 1 1 1 0 v2 1 0 1 1 1 v3 1 1 0 1 0 v4 1 1 1 0 1 v5 0 1 0 1 0 第二步:深度优先遍历:从 v1 这一行开始从左到右找第一个 非零元;这里找到了v2;v1 就不继续查找了;再到 v2 这一行查找找到了v1,但是 v1 已

25、经遍历过了;所以继续找,这里找到了 v3;v2就不继续查找了;再到 v3 行查找,同理找到了v4;再查找找到了v5 所以深度优先遍历序列:v1,v2,v3,v4,v5;广度优先遍历:从 v1 这一行开始从左到右找非零元;这里找到了 v2,v3,v4;再到v2 这一行查找非零元;找到了 v1,但是 v1 已经遍历过了;直到查到 v5 位置;再到v3,v4行查找非零元;所以广度优先遍历序列:v1,v2,v3,v4,v5;名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 21 页 -136542192116566111418333、已知一无向图的邻接矩阵如下，求该图从顶点V1出发的广度

26、优先遍历和深度优先遍历序列。0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 分析:分析方法同上;广度优先遍历:v1,v3,v6,v4,v7,v2,v5;深度优先遍历:v1,v3,v4,v2,v7,v6,v5;4下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1 条线路，画出所有可能的选择。名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 21 页 -分析:最小生

27、成树的 普里姆算法 (解答题中最方便的方法):请查看选择题第8题;个人理解:就是先找到一条最短的边,把这条边的两个顶点连起来,再找 与这两个顶点相连 的边中最短的一条,再把他们连接起来(这样就找到了3 个顶点),再找与这 3个顶点相连的边中最短的一条,再把他们连起来,直到所有顶点都被连起来为止.只要注意不要连成环就行.这里就是先找到最短的是5 这条边,所以把 2,3连接起来;再找与 2,3相连的边中最短的,找到了 6,把 2,6或则 3,6连接起来;再找与 2,3,6相连的边中最短的;找到了 11,把 2 和 4 连接起来 5、对下面的有向图，试利用DIJKSTRA 算法从顶点1 到其它顶点的

28、最短路径，并写出执行该算法过程中每次循环的状态。名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 21 页 -分析:先从 v1 连接各点,找到一条最短的,这条就是 v1 到该点的最短路径;再从这一点开始连接其他各点,该点到其他点得距离加上v1 到该点的距离和v1 到各点的距离比较;如果比原来短了,就消掉原来的线,画上新的线,再到这些线中找一条最短的,即为最短路径 6、对下面的AOE 网，求出各项活动的最早开始时间e(i)和最迟开始时间l(i)，并回答：工程完成的最短时间是多少？哪些是关键活动？v4 v2 v6 v5 v1 v310 10 10 15 4 30 4 20 2 15

29、名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 21 页 -分析:e(i)表示从前面到i 弧尾(弧表示活动)得最长路径;l(i)表示总的最长路径减去从后面到 i 弧尾(弧表示活动)的最长路径,当 e(i)=l(i)时,e(i)即为关键活动最长路径为:v1-v3-v4-v7-v9-v10 最短时间是24,e(1)=0;l(1)=1;e(2)=0;l(2)=0;e(3)=5;l(3)=9;e(4)=6;l(4)=6;e(5)=6;l(5)=13;e(6)=12;l(6)=16;e(7)=12;l(7)=12;e(8)=12;l(8)=13;e(9)=15;l(9)=16;e(10)

30、=15;l(10)=16;e(11)=17;l(11)=17;e(12)=19;l(12)=20;e(13)=16;l(13)=20;e(14)=22;l(14)=22;所以关键活动为:a2,a4,a7,a11,a14 7下图是带权的有向图G的邻接表表示法，求：（1）以结点V1出发深度遍历图G所得的结点序列；（2）以结点V1出发广度遍历图G所得的结点序列；（3）从结点V1到结点 V8 的最短路径；（4）从结点V1到结点 V8 的关键路径。v1 V3 V2 V5 V4 V7 V8 V9 V6 v10 a1=5 a2=6 a4=6 a5=3 a8=3 a3=3 a6=4 a7=5 a11=5 a1

31、3=4 a13=2 a12=2 a10=4 a9=1 名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 21 页 -分析:这里不可以化成邻接矩阵:因为 v2 中的顺序不是从小到大的,他是 3,5,4的顺序;所以如果化成邻接矩阵的话两种遍历和邻接表的遍历都会不一样.(1).深度优先遍历:v1,v2,v3,v8,v5,v7,v4,v6(2).广度优先遍历:v1,v2,v4,v6,v3,v5,v7,v8(3).画出每一步的Di(红色为确定的路径)v1 v2 v3 v4 v5 v6 v7 v8 所以 v1 到 v8 的最短路径为56 0 6 49 1 12 50 0 6 1 13 50

32、0 6 1 50 0 6 49 1 12 50 36 56 0 6 49 1 12 50 36 56 0 6 49 1 12 50 36 56 0 6 49 1 12 50 36 名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 21 页 -(4).这里求的是关键路径(顶点)就用 ve(i)=vl(i)来判断(顶点用 vi 表示),如果求的是关键活动(弧)就用 e(i)=l(i)来判断(弧用 ai 表示)第一步:画出 AOE-网图第二步:求 ve(i),vl(i),先有 ve 求出 ve(v8)求出最短时间,在逆推 vl(i)ve(v1)=0;ve(v2)=6;ve(v3)=89;ve(v4)=17;ve(v5)=51;ve(v6)=50;ve(v7)=75;ve(v8)=97;vl(v1)=0;vl(v2)=28;vl(v3)=89;vl(v4)=39;vl(v5)=51;vl(v6)=50;vl(v7)=77;vl(v8)=97;所以关键路径为:v1-v6-v5-v3-v8 名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 21 页 -