数据结构习题与解析07xitidaan.docVIP

第7章 图 一、单选题 01-10 CBBCC BAACB 11-20 DAADB ACACB 21-30 DCDAD BCBAD 二、填空题 01、入度 02、n-1 03、邻接矩阵、邻接表 04、深度、广度 04、出度 05、n 06、O(n2)、O(n+e) 07、有向 08、将邻接矩阵的第i行全部置0 09、矩阵第i列非0元素之和 10、第i行第j列的元素是否为0 11、O(n2)、O(elog2e) 12、克鲁斯卡尔(Kruskal)、普里姆(Prim) 13、递增 14、0 15、出度 16、n 17、0 18、错误 19、2(n-1) 20、存在 三、简答题 01、3个，分别是：a,bce,dfg 02、 03、普里姆算法产生边的序列：(1,3),(3,4),(4,6),(6,5),(5,2) 克鲁斯卡尔算法产生边的序列：(4,6),(1,3),(4,3),(6,5),(2,5) 04、v1,v2,v3,v4 v1,v3,v2,v4 v2,v1,v3,v4 v3,v2 05、(1) 每个顶点的入/出度 (2) 邻接矩阵 (3) 邻接表 (4) 逆邻接表 06、(1)邻接矩阵为： V b c d e f g h U V-U Vex lowcost a 4 a 3 a ∞ a ∞ a ∞ a ∞ a ∞ {a} {b,c,d,e,f,g,h} Vex lowcost a 4 0 c 5 a ∞ a ∞ a ∞ c 5 {a,c} {b,d,e,f,g,h} Vex lowcost 0 0 c 5 b 9 a ∞ a ∞ c 5 {a,c,b} {d,e,f,g,h} Vex lowcost 0 0 0 d 7 d 6 d 5 d 4 {a,c,b,d} {e,f,g,h} Vex lowcost 0 0 0 d 7 d 6 d 5 0 {a,c,b,d,h} {e,f,g} Vex lowcost 0 0 0 d 7 g 2 0 0 {a,c,b,d,h,g} {f,e} Vex lowcost 0 0 0 f 3 0 0 0 {a,c,b,d,h,g,f} {e} Vex lowcost 0 0 0 0 0 0 0 {a,c,b,d,h,g,f,e} { } 最小生成树 07、邻接表为： fg(2)(ac(3)(fe(3)(ab(4)(dh(4)(bd(5)(dg(5) 08、 09、 a(c：2(a,c) a(f：6(a,c,f) a(e：10(a,c,e) a(d：11(a,c,f,d) a(g：14(a,c,f,d,g) a(b：15(a,b) 10、和上题类似，求解过程略。 11、 1，2，3，6，5，4 1，3，2，6，5，4 1，3，6，2，5，4 12、 FALSE //初始化为未访问 DSFTree(G, p-adjvex) //从相邻结点往下继续深度有哪些信誉好的足球投注网站 p=p-next //下一个未访问的相邻结点 四、算法设计题 01、编写编历算法，完成对图的深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站。 深度优先有哪些信誉好的足球投注网站：课本P169算法7.4和算法7.5 广度优先有哪些信誉好的足球投注网站：课本P170算法7.6 02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 解：Status Build_AdjList(ALGraph G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf(%d,v); if(v0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(%d,a); if(a0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;mv;m++) G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m=a;m++) { t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))0) return ERROR; if((j=LocateVex(G,h))0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) G.ver