数据结构第七章习题课(共9页).doc

《数据结构第七章习题课(共9页).doc》由会员分享，可在线阅读，更多相关《数据结构第七章习题课(共9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上1、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（ ）。 A、求关键路径的方法 B、求最短路径的Dijkstra方法 C、宽度优先遍历算法 D、深度优先遍历算法2图中有关路径的定义是（ ）。A 由顶点和相邻顶点序偶构成的边所形成的序列 B 由不同顶点所形成的序列C 由不同边所形成的序列 D 上述定义都不是3一个n个顶点的连通无向图，其边的个数至少为（ ）。An-1 Bn Cn+1 Dnlogn；4当一个有N个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是（ ）。A B C D+ 5. 下列说法不正确的是（ ）。 A 图的遍历是从给定的源点出发每一个顶

2、点仅被访问一次 B 遍历的基本算法有两种：深度遍历和广度遍历C 图的深度遍历不适用于有向图D 图的深度遍历是一个递归过程6无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b7. 设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）a e b d f c a c f d e b a e d f c b a e f d c b a e

3、 f d b cA5个 B4个 C3个 D2个 8. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。A. O(n) B. O(n+e) C. O(n2) D. O(n3)9已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（ ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V710若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ ）。 A存在 B不存在11一个有向无环图的拓

4、扑排序序列（ ）是唯一的。A一定 B不一定12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 AG中有弧 BG中有一条从Vi到Vj的路径 CG中没有弧 DG中有一条从Vj到Vi的路径 13下列关于AOE网的叙述中，不正确的是（ ）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成14.判断一个无向图是一棵树的条件是_。答：有n个顶点，n-1条边的无向连通图15有向图G的强连通分量是指_。答：有向图的极大强连通

5、子图16. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1=i=n），则e=_ 答：（d1+d2+dn）/217. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_条弧。答：n18在有n个顶点的有向图中，每个顶点的度最大可达_。答：2(n-1)19右图中的强连通分量的个数为（ ）个。答：320N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_个非零元素。答：2（N-1）21. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_。答：第I列非零元素个数22. 已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(

6、d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_遍历方法。答：深度优先23. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_存放被访问的结点以实现遍历。答：队列24. 有一个用于n个顶点连通带权无向图的算法描述如下：（1）设集合T1与T2，初始均为空；（2）在连通图上任选一点加入T1；（3）以下步骤重复n-1次：a.在i属于T1，j不属于T1的边中选最小权的边；b.该边加入T2。上述算法完成后，T2中共有_条边，该算法称_算法，T2中的边构成图的_。答：(1)n-1 (2)普里姆 (3)最小生成树25. 有向图G可拓扑排

7、序的判别条件是_。答：不存在环26.有向图G=(V,E),其中 V(G)=0,1,2,3,4,5，用三元组表示弧及弧上的权d.E(G)为,，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_。答：50，经过中间顶点427. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为_。答：7528AOV网中，结点表示_，边表示_。AOE网中，结点表示_，边表示_。答：(1)活动 （2）活动间的优先关系 （3）事件 （4）活动，边上的权代表活动持续时间29. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。（1）查邻接表中入度为_的顶点，并进栈；（2）若栈不空，则输出栈顶元素Vj，

8、并退栈；查Vj的直接后继Vk，对Vk入度处理，处理方法是_；（3）若栈空时，输出顶点数小于图的顶点数，说明有_，否则拓扑排序完成。答：（1）零 （2）Vk度减1，若Vk入度己减到零，则Vk顶点入栈 （3）环36758942130首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。 31已知某图的邻接表为（1）写出此邻接表对应的邻接矩阵；（2）写出由v1开始的深度优先遍历的序列；（3）写出由v1开始的深度优先的生成树；（4）写出由v1开始的广度优先遍历的序列；（5）写出由v1开始的广度优先的生成树；（6）写出将无向图的邻接表转换成邻接矩阵的算法。

9、EABGCDF53614132532考虑右图：(1)从顶点A出发，求它的深度优先生成树(2)从顶点E出发，求它的广度优先生成树（3）根据普利姆(Prim) 算法，从顶点A出发，求它的最小生成树答：设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列(1)ABGFDEC (2)EACFBDG223ADADF132GAFD1323BGFDA123 4DFACGBE1234DFACGB133(3) 126543201011661810145933已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以为起点，试画出构造过程）。143529287564434G=(V,E

10、)是一个带有权的连通图,则：（1）请回答什么是G的最小生成树； （2）G为下图所示,请找出G的所有最小生成树。 35一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。 36请看下边的无向加权图。 （1）写出它的邻接矩阵（2）按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。辅助数组内各分量值： iClosedge2345678 U V.-UadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcost37下图所示是一

11、带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：（1）该带权有向图的图形；（2）从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）；（3）以顶点V1为起点的深度优先周游生成树；（4）由顶点V1到顶点V3的最短路径。 38对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。 39已知图的邻接矩阵为：V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V4000001101

12、0V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：（1）以顶点V1为出发点的唯一的深度优先遍历；（2）以顶点V1为出发点的唯一的广度优先遍历；（3）该图唯一的拓扑有序序列。40对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。41设有向G图有n个点(用1,2,n表示),e条边,写一算法根据其邻接表生成其反向邻接表,要求算法复杂性为O(n+e)。

13、void InvertAdjList(AdjList gin,gout）/将有向图的出度邻接表改为按入度建立的逆邻接表 for (i=1;i=n;i+)/设有向图有n个顶点，建逆邻接表的顶点向量。 gini.vertex=gouti.vertex; gin.firstarc=null; for (i=1;iadjvex; s=(ArcNode *)malloc(sizeof(ArcNode);/申请结点空间。 s-adjvex=i; s-next=ginj.firstarc; ginj.firstarc=s; p=p-next;/下一个邻接点。 /while /for 42写出从图的邻接表表示

14、转换成邻接矩阵表示的算法。void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)/将图的邻接表表示转换为邻接矩阵表示。for (i=1;i=n;i+) /设图有n个顶点，邻接矩阵初始化。 for (j=1;j=n;j+) gmij=0; for (i=1;iadjvex=1;p=p-next; /下一个邻接点 /for /算法结束43设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表。void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )/将图的邻接矩阵表示法转换为邻接表表示法。for (i=1;i=n;

15、i+) /邻接表表头向量初始化。 scanf(&gli.vertex); gli.firstarc=null; for (i=1;i=n;i+) for (j=1;jadjvex=j;/顶点I的邻接点是jp-next=gli.firstarc; gli.firstarc=p; /链入顶点i的邻接点链表中 /end算法讨论 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。44假设有向图以邻接表存储，试编写算法删除弧的算法。void DeleteArc（AdjList g,vertype vi,vj） /删除以邻接表存储的有向图g的一条弧，假定顶点vi和vj存在i=GraphLoca

16、teVertex(g,vi); j=GraphLocateVertex(g,vj); /顶点定位 p=gi.firstarc; pre=null;while (p) if (p-adjvex=j) if(pre=null) gi.firstarc=p-next;else pre-next=p-next;free(p);/释放结点空间。 else pre=p; p=p-next;/结束45已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 void DeletEdge(AdjList g,int i,j) /在用邻接表方式存储的无向图g中，删除边(i,j)p=gi.firstarc;

17、pre=null; /删顶点i 的边结点(i,j),pre是前驱指针while (p) if (p-adjvex=j) if(pre=null)gi.firstarc=p-next;else pre-next=p-next;free(p); /释放结点空间。 else pre=p; p=p-next; /沿链表继续查找p=gj.firstarc; pre=null; /删顶点j 的边结点(j,i)while (p) if (p-adjvex=i) if(pre=null)gj.firstarc=p-next;else pre-next=p-next;free(p); /释放结点空间。 else

18、 pre=p; p=p-next; /沿链表继续查找 / DeletEdge算法讨论 算法中假定给的i，j 均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。46设有向图用邻接表表示,图有n个顶点,表示为1至n,试写一个算法求顶点k的入度(1kn)。题目分析在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。 int count (AdjList g , int k )/在n个顶点以邻接表表示的有向图g中，求指定顶点k(1=k=n)的入度。 int count

19、=0; for (i=1;iadjvex=k) count+; p=p-next;/while/if return(count); /顶点k的入度.47写出图的深度优先搜索DFS算法的非递归算法。 void Traver(AdjList g,vertype v) /图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。struct arc *stack; visitedv=1；printf(v); /输出顶点v top=0; p=gv.firstarc; stack+top=p; while(top0 | p!=null) while (p) if (p & visitedp-adjvex) p=p-next; else printf(p-adjvex); visitedp-adjvex=1; stack+top=p; p=gp-adjvex.firstarc; /else if (top0) p=stacktop-; p=p-next; /while /算法结束。算法讨论 以上算法适合连通图，若是非连通图，则再增加一个主调算法,其核心语句是for (vi=1;vi=n;vi+) if (!visitedvi) Traver(g,vi);专心-专注-专业