图历试题及参考答案.docVIP

第7章 图 （2008年1月） 9、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（　　　） A、n B、e C、2e D、n·e 10、如图所示的有向无环图可以得到的不同拓扑序列的个数为（　　　） A、1 B、2 C、3 D、4 22、已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为___________。 28、已知有向图的邻接表如图所示, 写出从顶点A出发,对该图进行广度优先有哪些信誉好的足球投注网站遍历的顶点序列; 画出该有向图的逆邻接表。 (1) (2) 33、设有向图邻接表定义如下； typedef struct{ VertexNode adjlist[Max VertexNum]; int n,e; //图的当前顶点数和弧数 } ALGraph; //邻接表类型 vertex firstedge 其中顶点表结点VertexNode结构为： 边表结点EdegNode结构为： adjvex next 阅读下列算法f33，并回答问题： (1)已知有向图G的邻接表如图所示, 写出算法f33的输出结果; (2)简述算法f33的功能。 void dfs (ALGraph *G,int v) { EdgeNode * p; visited[v]=TRUE; printf(%c,G-adjlist[v].vertex); for(p=(G-adjlist[v]).firstedge; p; p=p-next) if(! visited[p-adjvex]) dfs (G, p-adjvex); } void f33(ALGraph *G) { int v,w; for(v=0; v G-n; v ++) { for(w=0;wG-n; w++) visited[w]= FALSE; printf(%d:,v); dfs(G,v); printf(\n); } } （1） （2） （2008年10月） 8、在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ） A、 Dout B、 Dout-1 C、 Dout+1 D、 n 9、如图所示的有向无环图可以得到的拓扑序列的个数是（ ） A、 3 B、 4 C、 5 D、 6 10、如图所示的带权无向图的最小生成树的权为（ ） A、 51 B、 52 C、 54 D、 56 22、n个顶点且含有环路的无向连通图中，至少含有 条边。 27、图的邻接表的类型定义如下所示： #define MaxVertexNum 50 typedef struct node { int adjvex; struct node *next; }EdgeNode; typedef struct { VertexType vertex; EdgeNode *firstedge; }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; typedef struct { AdjList adjlist; int n, e; }ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。 （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) C、(v0，v1，v5，v2，v3，v4) D、(v0，v1，v4，v5，v2，v3) 11、如图所示有向图的一个拓扑序列是( ) A、ABCDEF B、FCBEAD C、FEDCBA D、DAEBCF 22、若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中_________。 32、设有向图邻接表定义如下： typedef struct { VertexNode adjlist[ MaxVertexNum ] ; int n，e； ／／图的当前顶点数和弧数 }ALGraph； ／／邻接表类型 其中顶点表结点VertexNode 边表结点EdgeNode结构为： 阅读下列算法，并回答问题： (1)已知某有向图存储在如图所示的邻接 表G中