数据结构习题课课件.ppt

《数据结构习题课课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构习题第5章吉林大学计算机科学与技术学院谷方明第5章作业5-1，5-7，5-12，5-13，5-14，5-15，5-165-1给出下图所示的邻接矩阵和邻接表EDCBA参考答案EDCBA00110001100000100000100101234512345参考答案：注意头指针数组ABCDΛECDΛCDΛEΛAEΛ5-7用邻接矩阵存储一个包含1000个顶点和1000条边的图，则该图的邻接矩阵中有多少元素？有多少非零元素？该矩阵是否为稀疏矩阵？参考答案１）矩阵中元素个数：1000000２）若图为有向图：非零元素的个数：100

2、0若图为无向图：非零元素的个数：2000３）该矩阵是稀疏矩阵5-12设计一个算法，检测采用邻接表方法存储、具有n个顶点的有向图中是否存在从顶点v到顶点u的路径，若存在路径，算法给出信息TRUE，否则，给出信息FALSE.参考答案算法Path(v,u.flag)/*判断v到u是否有路.有,flag为TRUE,否则FALSE.vis全局，记录结点访问状态*/P1[递归出口]IF(v=u)THEN(flagTRUE.RETURN.)P2[依次判断v的邻接顶点是否有到u的路]vis[v]=1.pHead[v].WHILE(p<>

3、NULL)DO(IF(vis[VerAdj(p)]=0)(Path(VerAdj(p),u,flag).IF(flag=TRUE)THENRETURN.)pLink(p).).P3[不存在路]flag=FALSE.▌时间复杂度O(n)，空间复杂度O(n)其它方法调用DFS或BFS，检查vis数组，判断是否在一个连通分支。Warshall，判断v、u之间是否连通5-13设G＝（V,E）是有向图，请给出算法，判断G中是否有回路，并要求算法的复杂性为O（n+e）。方法一：深度优先搜索思想：深搜时，每个结点有两个状态，标记是否被访

4、问过（0未访问，1已访问过）。判环时，多引入一个状态，标记结点正在访问中（-1正在访问中）。如果一个结点正在访问中，又遍历到该接点，那个存在环路。这种状况是由于出现了反向边，即后代指向祖先的边。如果图中有多个连通分支，需要对每个连通分支都判断。算法Cycle(v.flag)/*判断以v为起点的连通分支是否有环，若有，flag为TRUE,否则FALSE.vis全局，记录每个点的访问状态*/C1[标记v正在访问中]vis[v]=-1.C2[深度优先遍历]pHead[v].WHILE(p<>NULL)DO(if(VerAdj(p

5、)=-1)(flag=TRUE.RETURN)if(VerAdj(p)=0)(Cycle(VerAdj(p),flag).IF(flag=TRUE)THENRETURN.)pLink(p).)C3[不存在路]vis[v]=1.flag=FALSE.▌方法二：拓扑排序voidGraph::TopoOrder(){inttop=-1;for(inti=0;i

6、out<<"Thereisacycleinnetwork!"<VerAdj;if(--count[k]==0){count[k]=top;top=k;}p=p->link;}}}思考无向图如何判环？5-14对于下图所示的非负有向网络，给出Dijkstra算法产生的由源点2到图

7、中其它顶点的最短路径长度以及路径所经历的顶点，并写出生成过程。2012345650101031515203530参考答案S2123456初始化∞0∞∞∞∞2∞01015∞∞23∞0101540∞234350101530∞2345350101530∞23451350101530∞234516350101530∞2012345650101031515203530参考答案2012345650101031515203530最短路径最短路径长度2→3102→4152→4→5302→4→1352→6∞123456dis350101530

8、∞path4-1224-1s1111105-15试求出下图中所有顶点之间的最短路径参考答案A(-1)A(0)A(1)A(2)A(3)01230123012301230123009¥309¥3091430914305731¥05¥¥05¥¥05¥6059605921¥0¥1100411004