数据结构与算法试卷B

----------------1|10202|2|1035|3|315|4|2051110|5|15113|6|2103|--------------------------(b)adjacencylist:(3scores)1->2(10)->4(20)->6(2)->\2->1(10)->3(3)->4(5)->\3->2(3)->5(15)->\4->1(20)->2(5)->5(11)->6(10)->\5->3(15)->4(11)->6(3)->\6->1(2)->4(10)->5(3)->\(c)(2scores)Spaceofadjacencymatrix:2*36=72(bytes)Spaceofadjacencylist4*6+(2+2+4)*16=152(bytes)Soadjacencylistrequiresmorespaceforthisgraph.(2)65312410252015101133653124101011315《DataStructureandAlgorithms》试卷B第6页共6页OrderthatVertexsareprocessed:12354610.(7scores)(1)UseDijkstra’sAlgorithmtofindtheshortestpathsfromCtoallothervertices.(4scores)(2)UseKruskal’salgorithmtofindtheminimum-costspanningtree.(3scores)Answer:(1)CtoA:4(C,A);CF:5(C,F);CD:6(C,A,D);CB:12(C,A,D,B);CG:11(C,F,G);CE:13(C,A,D,B,E)(2)ORABCFGDE4913662578AECDFG632154BACDBFG632154E