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

第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、已知有向图的邻接表如图所示,

(1) 写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列;

(2) 画出该有向图的逆邻接表。 ．

(1)

(2)

33、设有向图邻接表定义如下；

typedef struct{

VertexNode adjlist[Max VertexNum];

int n,e; //图的当前顶点数和弧数

} ALGraph;

其中顶点表结点VertexNode边表结点EdegNode结构为：

阅读下列算法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;w<G->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;

为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。

题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)

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中，写出执行f32(&G)的输出；

(2)简述算法f32的功能。

int visited[ MaxNum ];

void DFS(ALGraph * G, int i) {

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 -> adjvex) ;

p = p->next;

}

}

}

void f32 ( ALGraph * G) {

int i;

for (i = 0; i < G->n; i ++)

visited [ i ] = FALSE;

for (i = 0; i < G->n; i++)

if ( ! visited[i] ) DFS(G, i) ;

}

(1)

(2)

（2009年10月）

11、若非连通无向图G含有21条边，则G的顶点个数至少为（ ） ．

A、7 B、8

C、21 D、22

12、如图所示的有向图的拓扑序列是（ ）

A、c，d，b，a，e

B、c，a，d，b，e

C、c，d，e，a，b

D、c，a，b，d，e

22、求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中________的数目正相关。

28、已知无向图G的邻接表如图所示，

(1)画出该无向图；

(2)画出该图的广度优先生成森林。

30、阅读下列算法，并回答问题：

(1)无向图G如图所示，写出算法f30(&G)的返回值；

(2)简述算法f30的功能。

#define MaxNum

20

int visited[MaxNum]；

void DFS(Graph *g，int i)；

/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visited[j]为1*/

int f30(Graph *g)

{ int i，k；

for (i=0； i<g->n； i++)／*g->n为图g的顶点数目*／

visited[i]=0；

for (i=k=0； i<g->n; i++)

if (visited[i]= =0)

{ k++；

DFS(g，i)；

}

return k；

}

（2010年1月）

11、对下面有向图给出了四种可能的拓扑序列，其中错误的是（ ）

．．

A、1，5，2，6，3，4 B、1，5，6，2，3，4

C、5，1，6，3，4，2 D、5，1，2，6，4，3

12、以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）

A、v1，v2，v3，v4，v5，v6，v7 B、v1，v2，v5，v4，v3，v7，v6

C、v1，v2，v3，v4，v7，v5，v6 D、v1，v2，v5，v6，v7，v3，v4

22、已知有向图如下所示，其中顶点A到顶点C的最短路径长度是_________。

27、已知一个无向图G=(V，E)，其中V={A，B，C，D，E，F}，邻接矩阵表示如下所示。

请回答下列问题：

(1)请画出对应的图G。

(2)画出图G的邻接表存储结构。

（2010年10月）

9、在图G中求两个结点之间的最短路径可以采用的算法是( )

A、迪杰斯特拉（Dijkstra）算法 B、克鲁斯卡尔（Kruskal）算法

C、普里姆(Prim)算法 D、广度优先遍历(BFS)算法

10、下图G=(V,E)是一个带权连通图，G的最小生成树的权为( )

A、15