第7章 图 历年试题及参考答案(08)

《第7章 图 历年试题及参考答案(08)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图（2008年1月）9、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（　　　）A、nB、eC、2eD、n·e10、如图所示的有向无环图可以得到的不同拓扑序列的个数为（　　　）A、1B、2C、3D、422、已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为___________。28、已知有向图的邻接表如图所示,(1)写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;(2)画出该有向图的逆邻接表。(1)(2)33、设有向图邻接表定义如下；typedefstruct{VertexNodeadjlist

2、[MaxVertexNum];intn,e;//图的当前顶点数和弧数}ALGraph;//邻接表类型vertexfirstedge其中顶点表结点VertexNode结构为：边表结点EdegNode结构为：adjvexnext阅读下列算法f33，并回答问题：(1)已知有向图G的邻接表如图所示,写出算法f33的输出结果;(2)简述算法f33的功能。voiddfs(ALGraph*G,intv){EdgeNode*p;visited[v]=TRUE;printf("%c",G->adjlist[v].vertex);for(p=(G->adjl

3、ist[v]).firstedge;p;p=p->next)if(!visited[p->adjvex])dfs(G,p->adjvex);}voidf33(ALGraph*G){intv,w;for(v=0;vn;v++){for(w=0;wn;w++)visited[w]=FALSE;printf("%d:",v);dfs(G,v);printf("");}}（1）（2）（2008年10月）8、在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（）A、DoutB、Dout-1C、Do

4、ut+1D、n9、如图所示的有向无环图可以得到的拓扑序列的个数是（）A、3B、4C、5D、610、如图所示的带权无向图的最小生成树的权为（）A、51B、52C、54D、5622、n个顶点且含有环路的无向连通图中，至少含有条边。27、图的邻接表的类型定义如下所示：#defineMaxVertexNum50typedefstructnode{intadjvex;structnode*next;}EdgeNode;typedefstruct{VertexTypevertex;EdgeNode*firstedge;}VertexNode;type

5、defVertexNodeAdjList[MaxVertexNum];typedefstruct{AdjListadjlist;intn,e;}ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。题27图（2009年1月）10、已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为()A、(v0，v1，v2，v5，v4，v3)B、(v0，v1，v2，v3，v4，v5)

6、C、(v0，v1，v5，v2，v3，v4)D、(v0，v1，v4，v5，v2，v3)11、如图所示有向图的一个拓扑序列是()A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF22、若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_________。32、设有向图邻接表定义如下：typedefstruct{VertexNodeadjlist[MaxVertexNum];intn，e；／／图的当前顶点数和弧数}ALGraph；／／邻接表类型其中顶点表结点VertexNode边表结点EdgeNode结构为：阅读下列算法，并回答问题

7、：(1)已知某有向图存储在如图所示的邻接表G中，写出执行f32(&G)的输出；(2)简述算法f32的功能。intvisited[MaxNum];voidDFS(ALGraph*G,inti){EdgeNode*p;visited[i]=TRUE;if(G->adjlist[i].firstedge==NULL)printf("%c",G->adjlist[i].vertex);else{p=G->adjlist[i].firstedge;while(p!=NULL){if(!visited[p->adjvex])DFS(G,p->adjv

8、ex);p=p->next;}}}voidf32(ALGraph*G){inti;for(i=0;in;i++)visited[i]=FALSE;for(i=0;in;i++)