第7章课练答案.doc

第7章图自测卷解答姓名班级题号一二三四五总分题分1620241030100得分三、简答题(每题6分,共24分)1.【①】已知如图所示的有向图,请给出该图的:顶点123456入度出度每个顶点的入/出度;邻接矩阵;邻接表;逆邻接表。答案:2.【②】请对下图的无向带权图:写出它的邻接矩阵,并按普里姆算法求其最小生成树;写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。解:设起点为a。可以直接由原始图画出最小生成树,而且最小生成树只有一种(类)!邻接矩阵为:最小生成树→PRIM算法(横向变化):VbcdefghUV-UVexlowcosta4a3a∞a∞a∞a∞a∞{a}{b,c,d,e,f,g,h}Vexlowcosta40c5a∞a∞a∞c5{a,c}{b,d,e,f,g,h}Vexlowcost00c5b9a∞a∞c5{a,c,b}{d,e,f,g,h}Vexlowcost000d7d6d5d4{a,c,b,d}{e,f,g,h}Vexlowcost000d7d6d50{a,c,b,d,h}{e,f,g}Vexlowcost000d7g200{a,c,b,d,h,g}{f,e}Vexlowcost000f3000{a,c,b,d,h,g,f}{e}Vexlowcost0000000{a,c,b,d,h,g,f,e}{}邻接表为:a→b4→c3b→a4→c5→d5→e9^c→a3→b5→d5→h5^d→b5→c5→e7→f6→g5→h4^e→b9→d7→f3^f→d6→e3→g2^g→d5→f2→h6^h→c5→d4→g6^克鲁斯卡尔算法步骤(按边归并,堆排序):先罗列:f---2---ga—3--cf—3—ea—4---bd—4—h(a,b,c)(e,f,g)(d,h)取b—5—d,g—5--d就把三个连通分量连接起来了。3.【②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。4.【②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。解:最短路径为:(a,c,f,e,d,g,b)四、【2001年计考研题】给定下列网G:(10分)1试着找出网G的最小生成树,画出其逻辑结构图;2用两种不同的表示法画出网G的存储结构图;3用C语言(或其他算法语言)定义其中一种表示法(存储结构)的数据类型。AB———————CE————FG————D解:,如右图所示。:描述存储结构的数据类型可参见教材或电子教案:注