《数据结构相关试题》由会员分享，可在线阅读，更多相关《数据结构相关试题（5页珍藏版）》请在装配图网上搜索。
1、1. 试基于图的广度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由 顶点片到顶点Vj的路径(iHj)。int findpath(Graph G,int i,int j)int v;int visitedG.vexnum-1;LinkQueue Q;InitQueue(Q;for(v=0;v=0;w=NextAdjVex(G,u,w) if(!visited(w) visitedw=1; EnQueue(Q,w);if(visitedj=1)return 1;elsereturn 0;思路：若i=j,则一定存在路。若i!=j，以顶点i为起始点，找到与i有路的所有顶点并让他们的vi
2、siedk=1，循 环结束后，看visitedU是否恒等于1。若是，则存在从i到j的路，否则不存在。2.请画出以下无向带权图的邻接矩阵和邻接表，并按普里姆算法求其最小生成树。邻接矩阵cdefh3OeiCo(559OOcoooD5ooDOoasi507654g7038OQ 1DO6302085g20654goo60邻接表PRIM 算法：试利用Dijks tra算法求图中从顶点 其他各顶点间的最短路径，写出执 算法过程中各步的状态。DIST终点1=1i=2k31*i=51-6B呱刖15a.c.f.t.d.b.g图中编著为红的的为 a 到各顶点的最短路径4试对下图所示的AOE网络，解答下列问题。注：活动可用点对表示，如=2, =15。(1) 这个工程最早可能在什么时间结束。答：最早可能在43后结束(2) 求每个事件的最早开始时间Vei和最迟开始时间Vli。答：123456Ve(i)01915293843V1(i)01915373843(3) 求每个活动的最早开始时间e()和最迟开始时间1()。答：e()001515191938291()170152719273837(4) 确定哪些活动是关键活动。答：e()=1()为关键活动,为关键活动
数据结构相关试题
