数据结构第七章习题课

abedcf1、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）。A、求关键路径的方法B、求最短路径的Dijkstra方法C、宽度优先遍历算法D、深度优先遍历算法2．图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是3．一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；4．当一个有N个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是（）。A．nijiA1],[B．n1jj,iAC．niijA1],[D．nijiA1],[+n1ji,jA5.下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b7.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）aebdfcacfdebaedfcbaefdcbaefdbcA．5个B．4个C．3个D．2个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={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V710．若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。A．存在B．不存在11．一个有向无环图的拓扑排序序列（）是唯一的。A．一定B．不一定12.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径13．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成14.判断一个无向图是一棵树的条件是______。答：有n个顶点，n-1条边的无向连通图15．有向图G的强连通分量是指______。答：有向图的极大强连通子图16.设无向图G有n个顶点和e条边，每个顶点Vi的度为di（1=i=n），则e=______答：（d1+d2+……+dn）/217.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。答：n18．在有n个顶点的有向图中，每个顶点的度最大可达______。答：2(n-1)19．右图中的强连通分量的个数为（）个。答：320．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。答：2（N-1）21.在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。答：第I列非零元素个数22.已知一无向图G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(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可拓扑排序的判别条件是______。答：不存在环26.有向图G=(V,E),其中V(G)={0,1,2,3,4,5}，用a,b,d三元组表示弧a,b及弧上的权d.E(G)为{0,5,100,0,2,101,2,50,4,304,5,603,5,102,3,504,3,20}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。答：50，经过中间顶点427.上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。答：7528．AOV网中，结点表示______，边表示______。AOE网中，结点表示______，边表示______。答：(1)活动（2）活动间的优先关系（3）事件（4）活动，边上的权代表活动持续时间29.当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。（1）．查邻接表中入度为______的顶点，并进栈；（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______；（3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。答：（1）零（2）Vk度减1，若Vk入度己减到零，则Vk顶点入栈（3）环30．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。31．已知某图的邻接表为（1）．写出此邻接表对应的邻接矩阵；（2）．写出由v1开始的深度优先遍历的序列；（3）．写出由v1开始的深度优先的生成树；（4）．写出由v1开始的广度优先遍历的序列；（5）．写出由v1开始的广度优先的生成树；（6）．写出将无向图的邻接表转换成邻接矩阵的算法。32．考虑右图：(1)从顶点A出发，求它的深度优先生成树(2)从顶点E出发，求它的广度优先生成树（3）根据普利姆(Prim)算法，从顶点A出发，求它的最小生成树答：设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列(1)ABGFDEC(2)EACFBDG(3)367589421v1v2v3v4v5v6121124355634EABGCDF536141325223ADADF132GAFD1323BGFDA1234DFACGBE1234DFACGB13333．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。34．G=(V,E)是一个带有权的连通图,则：（1）．请回答什么是G的最小生成树；（2）．G为下图所示,请找出G的所有最小生成树。35．一带权无向图的邻接矩阵如下图，试画出它的一棵最小生成树。36．请看下边的无向加权图。（1）．写出它的邻接矩阵（2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。辅助数组内各分量值：iClosedge2345678UV.-UadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcostadjvexLowcost1265432010116618101459143529287564437．下图所示是一带权有向图的邻接表法存储表示。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：（1）．该带权有向图的图形；（2）．从顶点V1为起点的广度优先周游的顶点序列及对应的生成树（即支撑树）；（3）．以顶点V1为起点的深度优先周游生成树；（4）．由顶点V1到顶点V3的最短路径。38．对于如下的加权有向图，给出算法Dijkstra产生的最短路径的支撑树，设顶点A为源点，并写出生成过程。39．已知图的邻接矩阵为：V1V2V3V4V5V6V7V8V9V10V10111000000V20001100000V30001010000V40000011010V50000001000V60000000110V70000000010V80000000001V90000000001V100000000000当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：（1）．以顶点V1为出发点的唯一的深度优先遍历；（2）．以顶点V1为出发点的唯一的广度优先遍历；（3）．该图唯一的拓扑有序序列。V1V2V3V4V5V6233429625336230338542110618123456(顶点边)（出边表）ADCEB212034540353020201540．对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl(Vj)的函数值，列出各条关键路径。AWHGFEDCB16342751068211691312111741．设有向G图有n个点(用1,2,…,n表示),e条边,写一算法根据其邻接表生成其反向邻接表,要求算法复杂性为O(n+e)。voidInvertAdjList(AdjListgin,gout）//将有向图的出度邻接表改为按入度建立的逆邻接表{for(i=1;i=n;i++)//设有向图有n个顶点，建逆邻接表的顶点向量。{gin[i].vertex=gout[i].vertex;gin.firstarc=null;}for(i=1;i=n;i++)//邻接表转为逆邻接表。{p=gout[i].firstarc;//取指向邻接表的指针。while(p!=null){j=p-adjvex;s=(ArcNode*)malloc(sizeof(ArcNode));//申请结点空间。s-adjvex=i;s-next=gin[j].firstarc;gin[j].firstarc=s;p=p-next;//下一个邻接点。}//while}//for}42．写出从图的邻接表表示转换成邻接矩阵表示的算法。voidAdjListToAdjMatrix(AdjListgl,AdjMatrixgm)//将图的邻接表表示转换为邻接矩阵表示。{for(i=1;i=n;i++)//设图有n个顶点，邻接矩阵初始化。for(j=1;j=n;j++)gm[i][j]=0;for(i=1;i=n;i++){p=gl[i].firstarc;//取第一个邻接点。while(p!=null){gm[i][p-adjvex]=1;p=p-next;}//下一个邻接点}//for}//算法结束43．设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表。voidAdjMatrixToAdjList(AdjMatrixgm,AdjListgl)//将图的邻接矩阵表示法转换为邻接表表示法。{for(i=1;i=n;i++)//邻接表表头向量初始化。{scanf(&gl[i].vertex);gl[i].firstarc=null;}for(i=1;i=n;i++)for(j=1;j=n;j++)if(gm[i][j]==1){p=(ArcNode*)malloc(sizeof(ArcNode));//申请结点空间。p-adjvex=j;//顶点I的邻接点是jp-next=gl[i].firstarc;gl[i