第7章 图

第7章图

实验图的基本操作及应用

一、实验目的

1、熟悉图的基本概念，理解图的各种类型

2、掌握图的邻接矩阵、邻接表的表示方法

3、掌握图的两种遍历方法

4、加深理解图的最小生成树的基本思想。

5、掌握图的最小生成树的生成方法和实现算法

6、加深对图的理解，熟悉图的实际应用

二、实验内容

（一）验证实验

1、图的邻接矩阵表示

（二）设计实验

1、图的遍历问题

案例描述：已知8个城市的交通路线图如下图1所示，从沈阳出发，要到其他7个城市推销产品。给出到达每一个城市的一组城市顺序。

图1：8个城市的交通路线图

设计方案：图的遍历有深度优先遍历和广度优先遍历两种算法。在这里我们利用数据结构中图的邻接矩阵存储方式以及图的深度优先遍历的算法来解决该问题。

结构定义：

typedef char vextype[LEN];

typedef int edgetype;

typedef struct

{ vexntype vex[LEN];

edgetype arc[VEXN][VEXN];

int vexn,arcn;

}Mgraph;

2、某公司拟建一个局域网，需要连接6栋楼（0，1，2，3，4，5），其地理分布如下图2所示，各边上的权值代表楼宇间距离。

设计要求：根据下图中的楼宇分布，设计出布线造价最小的局域网络图，要求连接所有的顶点，并且总的布线费用最低。

实验提示：要想布线造价最小，可将图中各顶点间的距离看作其费用。这样就可以用Prim算法构造一棵最小生成树来解决问题。

图2 图2的邻接矩阵

运行时输入数据及运行结果显示如下：

Input vexnum,arcnum:6,10

V1,v2,w=0,1,6

V1,v2,w=0,2,5

V1,v2,w=0,5,1

V1,v2,w=1,5,5

V1,v2,w=1,3,3

V1,v2,w=2,5,5

V1,v2,w=2,4,2

V1,v2,w=3,5,6

V1,v2,w=3,4,6

V1,v2,w=4,5,4

输出最小生成树中的边及其权值如下：

（0，5）1

（5，4）4

（4，2）2

（5，1）5

（1，3）3

参考程序：

（一）验证实验

1、图的邻接矩阵表示

实验程序：

#include "Stdio.h"

#include "Conio.h"

#include"stdio.h"

#define MaxNum 50 //图的最大顶点数设为50

typedef char VexType[7]; //图的顶点类型设为字符数组，2个字符长度

typedef int EdgeType; //弧（边）的权值设为整型

typedef struct {

VexType V[MaxNum]; //一维数组存储顶点信息

EdgeType E[MaxNum][MaxNum]; //二维数组表示邻接矩阵，存储边的信息

int n,e; //顶点数和边数

}MGraph; //图类型定义

int Locate(MGraph *G,char vex[]) //确定顶点在图G中的位置，即在G->V中的序

{

int i;

for(i=0;in;i++)

if(strcmp(G->V[i],vex)==0)

return i;

}

void CreateGraph(MGraph *G)

{

int i,j,k;

char vex1[3],vex2[3];//保存输入的顶点

printf("\n输入图的顶点数和边数(用逗号分隔):");

scanf("%d,%d",&(G->n),&(G->e));//输入顶点数和边数

printf("输入图的顶点信息(最长2个字符):");

for (i=0;in;i++)

{/*G->V[i][0]=G->V[i][1]=0;*/

scanf("\n%s",G->V[i]); //输入n个顶点的标识信息，建立顶点数组

}

for (i=0;in;i++)

for (j=0;jn;j++)

G->E[i][j]=0; //对邻接矩阵元素进行初始化

printf("\n输入图中每条边所依附的两个顶点的标识信息:");

for (k=0;ke;k++) //输入e条边

{

printf("\n输入第%d条边的第1个顶点：",k+1);

scanf("%s",vex1);

printf("输入第%d条边的第2个顶点：",k+1);

scanf("%s",vex2);

// scanf("%s\n%s",vex1,vex2);

i=Locate(G,vex1);j=Locate(G,vex2);

// scanf("\n%d,%d",&i,&j); //输入每条边所依附的顶点在二维数组中的下标，建立邻接矩阵

G->E[i][j]=1; //如果同时输入G->E[j][i]=1;，则是建立无向图的邻接矩阵

}

}

void PrintGraph(MGraph *G)//打印图的顶点和边的信息

{

int i,j;

printf("\n图中顶点个数为：%d",G->n);

printf("\n图中边数为：%d",G->e);

printf("\n图中顶点为：");

for (i=0;in;i++)

printf("%c%c ",G->V[i][0],G->V[i][1]);

printf("\n图中边为：");

for(i=0;in;i++)

for(j=0;jn;j++)

if(G->E[i][j])

printf("[%c%c,%c%c] ",G->V[i][0], G->V[i][1], G->V[j][0], G->V[j][1]);

}

main()

{

MGraph mg;

CreateGraph(&mg);

PrintGraph(&mg);

}

（二）设计实验

1、图的遍历问题

案例描述：已知8个城市的交通路线图如下图1所示，从沈阳出发，要到其他7个城市推销产品。给出到达每一个城市的一组城市顺序。

#define NULL 0

#define VEXN 30 //顶点的最大个数

#define LEN 10 //城市名称的最大长度

#include

typedef char vexntype[LEN]; //顶点数据类型

typedef int edgetype; //边数据类型

typedef struct

{vexntype vex[VEXN];

edgetype arc[VEXN][VEXN];

int vexn,arcn; //顶点个数和边数

}Mgraph; //图的邻接矩阵表示结构

int visit[VEXN]; //遍历标志数组

Mgraph City_Graph()

{int i,j,k;

Mgraph G;

printf("\n input vex number");

scanf("%d",&G.vexn); //输入顶点数目

printf("input edge numbef:");

scanf("%d",&G.arcn); //输入总边数

printf("input %d vex information such as Shenyang Beijing and so on:\n",G.vexn); for(i=0;i

scanf("%s",&G.vex[i]);

for(i=0;i

for(j=0;j

G.arc[i][j]=0;

for(k=0;k

{printf("input edge %d such as i,j:",k+1);

scanf("%d,%d",&i,&j);

while(i<1||i>G.vexn||j<1||j>G.vexn) //输入各顶点距离

{printf("Error vexn Number,input(i,j)again:");

scanf("%d,%d",&i,&j);

}

G.arc[i-1][j-1]=1;

G.arc[j-1][i-1]=1;

}

return G;

}

void DFS_G(Mgraph G,int i) //输出深度优先遍历序列

{

int j;

printf("%s,",G.vex[i]);

visit[i]=1;

for(j=0;j

if((G.arc[i][j]==1)&&(!visit[j]))

DFS_G(G,j);

}

main()

{Mgraph G;

G=City_Graph(); //调用输入顶点和边的函数

printf("\nDFS:\n"); //调用查询最短路径函数

DFS_G(G,0);

}

运行测试：

<输入>

Input vex number:8

Input edge number:9

Input 8 vex information such as Shenyang Beijing and so on:

沈阳北京天津大连营口鞍山抚顺丹东（输入：每一个顶点回车）

Input edge1 such as i,j:1,2（在英文状态下输入）

Input edge1 such as i,j:1,3

Input edge1 such as i,j:2,3

Input edge1 such as i,j:4,5

Input edge1 such as i,j:5,6

Input edge1 such as i,j:6,7

Input edge1 such as i,j:7,8

Input edge1 such as i,j:1,6

Input edge1 such as i,j:1,7

<输出>

DFS：

沈阳北京天津鞍山营口大连抚顺丹东

2、某公司拟建一个局域网，需要连接6栋楼（0，1，2，3，4，5），其地理分布如下图2所示，各边上的权值代表楼宇间距离。

设计要求：根据下图中的楼宇分布，设计出布线造价最小的局域网络图，要求连接所有的顶点，并且总的布线费用最低。

实验提示：要想布线造价最小，可将图中各顶点间的距离看作其费用。这样就可以用Prim算法构造一棵最小生成树来解决问题。

#define MAX_VEX 50

int creatcost(cost)

int cost[][MAX_VEX];//cost这个二维数组用于表示带权图的邻接矩阵

{ int vexnum,arcnum,i,j,k,v1,v2,w;//输入图的顶点数和狐数或边数

printf("input vexnum,arcnum:");

scanf("%d,%d",&vexnum,&arcnum);

for(i=0;i

for(j=0;j

cost[i][j]=32767;

for(k=0;k

{printf("v1,v2,w=");

scanf("%d,%d,%d",&v1,&v2,&w);//输入所有狐或边的一对顶点v1,v2和权值

cost[v1][v2]=w;

cost[v2][v1]=w;

}

return(vexnum);

}

void prime(cost,vexnum)

int cost[][MAX_VEX],vexnum;//利用普里姆算法产生从顶点v0开始的最小生成树

{ int lowcost[MAX_VEX],closest[MAX_VEX],i,j,k,min;

for(i=0;i

{ lowcost[i]=cost[0][i];

closest[i]=0;

}

closest[0]=-1;

for(i=1;i

{min=32767;

k=0;

for(j=0;j

if(closest[j]!=-1&&lowcost[j]

{min=lowcost[j];

k=j;

}

if(k)

{printf("(%d,%d)%d\n",closest[k],k,lowcost[k]);//输出边及其权值

closest[k]=-1;

for(j=1;j

if(closest[j]!=-1&&cost[k][j]

{lowcost[j]=cost[k][j];

closest[j]=k;//k加入到U中

}

}

}

}

main()

{int vexnum;

int cost[MAX_VEX][MAX_VEX];

vexnum=creatcost(cost);//建立图的邻接矩阵

printf("bian quanzhi:\n");

prime(cost,vexnum);

}

数据结构第七章图练习及答案

1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧表示，持续时间记为dut，则有下式成立 e(i)=ve(j) l(i)=vl(k)-dut() （4）找出e(i)-l(i)=0的活动既是关键活动。 【答案】

关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）

第7章 图习题及答案

第7章图 一、选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（） A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（）条边。 A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2 【答案】B 3．连通分量指的是（） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 【答案】B 4．n个结点的完全有向图含有边的数目（） A）n*n B）n（n+1）C）n/2 D）n*（n-1） 【答案】D 5．关键路径是（） A） AOE网中从源点到汇点的最长路径 B） AOE网中从源点到汇点的最短路径 C） AOV网中从源点到汇点的最长路径 D） AOV网中从源点到汇点的最短路径 【答案】A 6．有向图中一个顶点的度是该顶点的（） A）入度 B）出度 C）入度与出度之和 D）（入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（）边结点。 A） e B） 2e C） e-1 D） 2(e-1)

【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（） A）栈 B）队列 C）二叉树 D）树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（） A）栈 B）队列 C）二叉树 D）树 【答案】A 10．存储无向图的邻接矩阵一定是一个（） A）上三角矩阵 B）稀疏矩阵 C）对称矩阵 D）对角矩阵【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍 A） 1/2 B）1 C） 2 D） 4 【答案】B 12．在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）A） O(n) B） O(n+e) C） O(n2) D） O(n3) 【答案】B 13．下列关于AOE网的叙述中，不正确的是（） A）关键活动不按期完成就会影响整个工程的完成时间 B）任何一个关键活动提前完成，那么整个工程将会提前完成 C）所有的关键活动提前完成，那么整个工程将会提前完成 D）某些关键活动提前完成，那么整个工程将会提前完成 【答案】B 14．具有10个顶点的无向图至少有多少条边才能保证连通（） A） 9 B）10 C） 11 D） 12 【答案】A 15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A） e B）2e C） n2-e D）n2-2e 【答案】D 16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表

第七章 图

第七章图 一、选择题 1．图中有关路径的定义是（ A ） A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ B ）条边。】 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（ D ）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A．1/2 B．2 C．1 D．4 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A)。 A．5 B．6 C．8 D．9 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(A )。 A．逆拓扑有序 B．拓扑有序 C．无序的 10．下面结构中最适于表示稀疏无向图的是（ C ），适于表示稀疏有向图的是（ BDE ）。 A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表 11．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网 12．从邻接阵矩可以看出，该图共有（B）个顶点；如果是有向图该图共有（B）条弧；如果是无向图，则共有（D）条边。 ①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查（ C ）的第i行第j列的元素是否为零即可。 A．mA B．A C．A m D．Am-1 15.下列说法不正确的是（ C ）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 17.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ D ） a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A．5个 B．4个 C．3个 D．2个 18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(C)，而进行广度优先遍历得到的顶点序列是（C）。 ①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确 ②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确 19．下面哪一方法可以判断出一个有向图是否有环（AB）： A．深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 20.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为( B )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 21.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ C），下面步骤重复n-1次: a：（ A）；b：（ B）；最后：（A）。 （1）．A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边 （2）．A.选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大

第七章 图

第七章 图 一、选择题 1．图中有关路径的定义是（ ）。 A ．由顶点和相邻顶点序偶构成的边所形成的序列 B ．由不同顶点所形成的序列 C ．由不同边所形成的序列 D ．上述定义都不是 2．设无向图的顶点个数为n ，则该图最多有（ ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 E ．n 2 3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。 A ．n-1 B ．n C ．n+1 D ．nlogn ； 4．要连通具有n 个顶点的有向图，至少需要（ ）条边。 A ．n-l B ．n C ．n+l D ．2n 5．n 个结点的完全有向图含有边的数目（ ）。【中山大学 1998 二、9 （2分）】 A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ） 7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学 2001 二、3 （2分）】 A ．1/2 B ．2 C ．1 D ．4 9．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A ．逆拓扑有序 B ．拓扑有序 C ．无序的 11．下列哪一种图的邻接矩阵是对称矩阵？（ ） A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 12． 从邻接矩阵 ????? ?????=01 101 010A 可以看出，该图共有（①）个顶点；如果是有向图该图共有 （②） 条弧；如果是无向图，则共有（③）条边。 ①．A ．9 B ．3 C ．6 D ．1 E ．以上答案均不正确 ②．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 ③．A ．5 B ．4 C ．3 D ．2 E ．以上答案均不正确 13．当一个有N 个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是（ ）。【南京理工大学1998一、4(2分）】 A ． ∑=n i j i A 1 ] ,[ B ． [] ∑=n 1 j j ,i A C ． ∑=n i i j A 1 ] ,[ D ． ∑=n i j i A 1 ],[+ [] ∑=n 1 j i ,j A 14．用相邻矩阵A 表示图，判定任意两个顶点Vi 和Vj 之间是否有长度为m 的路径相连，则只要检查（ ）的第i 行第j 列的元素是否为零即可。 A ．mA B ．A C ．A m D ．Am-1 15. 下列说法不正确的是（ ）。 A ．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C ．图的深度遍历不适用于有向图 B ．遍历的基本算法有两种：深度遍历和广度遍历 D ．图的深度遍历是一个递归过程 16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),

第7章 图单元测试(答案)

第七章 图 姓名： 学号： 一、选择题 1．设无向简单图的顶点个数为n ，则该图最多有（ B ）条边。 A ．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．n 2 2．一个n 个顶点的连通无向图，其边的个数至少为（ A ）。 A ．n-1 B ．n C ．n+1 D ．nlogn ； 3．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A ．1/2 B ．2 C ．1 D ．4 4．下列哪一种图的邻接矩阵是对称矩阵？（ ） A ．有向图 B ．无向图 C ．AOV 网 D ．AO E 网 5．下列有关图的遍历的说法中，不正确的是（ ）。 A ．用邻接表存储的图的深度优先搜索的时间复杂度为O(n ＋e) B ．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征，需要采用队列结构来实现 C ．非连通图不能用深度优先搜索法 D ．图的遍历要求每一顶点访问且仅被防问一次 6. 求解最短路径的Floyd 算法的时间复杂度为( )。 A ．O （n ） B. O （n+c ） C. O （n 2） D. O （n 3） 7. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。 A. O(n) B. O(n ＋e) C. O （n 2） D. O （n 3） 8.右图所示的无向网的最小生成树的权为( )。 A ．11 B ． 9 C ．14 D ．12 9. 关键路径是AOE 网中（ ）。 A ．从源点到汇点的最长路径 B ．从源点到汇点的最短路径 C ．最长回路 D ．最短回路 10．下列关于AOE 网的叙述中，不正确的是（ ）。 A ．关键活动不按期完成就会影响整个工程的完成时间 B ．任何一个关键活动提前完成，那么整个工程将会提前完成 C ．所有的关键活动提前完成，那么整个工程将会提前完成 D ．某些关键活动提前完成，那么整个工程将会提前完成 二、判断题 1. 有e 条边的无向图，在邻接表中有e 个结点。（ × ） 2. 强连通图的各顶点间均可达。（ √ ） 42

数据结构第7章 图习题

第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。

A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量

第7章 图练习题及答案

第七章 图 一、单选题 （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A ．1/2 B. 1 C. 2 D. 4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A ．14 B. 28 C. 56 D. 112 （ A ）一个n 个顶点的连通无向图，其边的个数至少为（ ）。 A ．n-1 B ．n C ．n+1 D ．nlogn ； （ C ）5. 有8个结点的有向完全图有 条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 8. 下面关于求关键路径的说法不正确的是（ C ）。 A ．求关键路径是以拓扑排序为基础的 B ．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C ．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D ．关键活动一定位于关键路径上 9. 已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历 的结点序列是（ D ） A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 ?????????? ????????????01000111011000 01011010110011 001000110010011011110

数据结构第7章 图习题

习题7 图 7.1 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 A. n B. (n-1)2 C. n-1 D. n2 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ①A. n B. n+1 C. n-1 D. n+e ②A. e/2 B. e C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ①A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b C. a,e,b,c,f,d D. a,c,f,d,e,b 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。

第7章 图(2)

第七章图 一、选择题 1．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序 B．拓扑有序 C．无序的【中科院软件所1998】 2．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学 2000 4、2（4分）】A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 3. 求解最短路径的Floyd算法的时间复杂度为( )。【合肥工业大学 1999 一、2 （2分）】 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 4．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={,,,,,,,,},G的拓扑序列是（）。 A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 【北京航空航天大学 2000 一、7 （2分）】 5．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。 A．存在 B．不存在【中科院计算所1998 二、6 (2分）】【中国科技大学 1998二、6（2分）】 6．一个有向无环图的拓扑排序序列（）是唯一的。【北京邮电大学 2001 一、3 （2分）】A．一定 B．不一定 7. 关键路径是事件结点网络中（）。【西安电子科技大学 2001应用一、4 （2分）】 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 8．下列关于AOE网的叙述中，不正确的是（）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 【北方交通大学 1999 一、7 （3分）】【北京工业大学 1999 一、1 (2分)】 二、判断题 1．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（）【上海交通大学1998 一、13】 2. 关键路径是AOE网中从源点到终点的最长路径。（）【青岛大学 2000 四、10（1分）】

第七章∶图练习题

第七章：图练习题 一、选择题 1、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 3、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4、具有4个顶点的无向完全图有（）条边。 A、6 B、12 C、16 D、20 5、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点 A、6 B、7 C、8 D、9 6、存储稀疏图的数据结构常用的是（）。 A、邻接矩阵 B、三元组 C、邻接表 D、十字链表 7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。 A、n B、(n-1)2 C、(n+1)2 D、n2 8、设连通图G的顶点数为n，则G的生成树的边数为（）。 A、n-1 B、n C、2n D、2n-1 9、n个顶点的无向图的邻接表中结点总数最多有（）个。 A、2n B、n C、n/2 D、n(n-1) 10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。 A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。 A、顶点v的度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数 12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（） （1）A、abecdf B、acfebd C、acebfd D、acfdeb （2）A、abcedf B、abcefd C、abedfc D、acfdeb 13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的 （）和（）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2

第七章+图

第七章图 一、判断题 （）1. 在每个AOE网络中只有一条关键路径。 （）2. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（）3．用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。 （）4．图的深度优先搜索序列和广度优先搜索序列不是唯一的。 （）5. 对AOV网进行拓扑排序时，如果存在从Vi到Vj的路径，则在拓朴序列中，结点Vi一定排在结点Vj的前面。 二、单项选择题 1. 在一个有向图的邻接矩阵表示中，删除一条边需要的时间复杂度为 ( )。 A) O(1) B) O(i) C) O(j) D) O(i+j) 2．一个有N个顶点的无向图最多有（）条边。 A) N B）N*(N?1) C）N*(N?1)/2 D）2*N 3．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：（）A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0 4．下面是三个关于有向图运算的叙述： （1）求有向图结点的拓扑序列，其结果必定是唯一的 （2）求两个指向结点间的最短路径，其结果必定是唯一的 （3）求AOE网的关键路径，其结果必定是唯一的 其中哪个（些）是正确的？ A) 只有（1）B) （1）和（2）C) 都正确D) 都不正确 5．已知一个无向图的邻接矩阵A[n][n]，要增加一条边( i, k )，应该： A）将A[i][k]置为1 B）将A[i][i]和A[k][k]同时置为1

C）将A[k][i]置为1 D）将A[i][k]和A[k][i]同时置为1 三、填空题（在横线处填写合适内容） 1. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________ 上，才会被加入到生成树中。 2．已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：将累加。 3．已知有向图的邻接矩阵，要计算i号结点的出度，计算方法是：将累加。 四、综合题 1.用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？ 2.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 3.有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。 4.对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？ 5.用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e)？或者是O(max(n,e))？ 6.设有一有向图为G=(V，E)。其中，V={v0, v1, v2, v3}，E={, , , , }。请画出该有向图。 7.已知如图所示的有向图，请给出该图的：

第7章-图习题及参考答案

第7章习题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在 图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 11.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（）。 A. 非零 B. 非整 C. 非负 D. 非正 12.设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 ? V2，E1 ? E2，则称（）。 A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量 13.有向图的一个顶点的度为该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. (入度﹢出度))／2 14.一个连通图的生成树是包含图中所有顶点的一个（）子图。 A. 极小 B. 连通 C. 极小连通 D. 无环 15.n (n＞1) 个顶点的强连通图中至少含有（）条有向边。 A. n-1 B. n n(n-1)/2 D. n(n-1) 16.在一个带权连通图G中，权值最小的边一定包含在G的（）生成树中。 A. 某个最小 B. 任何最小 C. 广度优先 D.深度优先 17.对于具有e条边的无向图，它的邻接表中有（）个结点。 A. e-1 B. e C. 2(e-1) D. 2e 18.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。 A.1, 4, 5 B. 1, 2, 3, 5 C. 1, 4, 3, 5 D. 1, 2, 4, 3, 5

第七章 图

第七章图 7.1 解：(1) ID(1)=3 OD(1)=0 ID(2)=2 OD(2)=2 ID(3)=1 OD(3)=2 ID(4)=1 OD(4)=3 ID(5)=2 OD(5)=1 ID(6)=2 OD(6)=3 (2) 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 1 1 0 0 1 0 (3) (4) (5) 有三个连通分量1、5、2346

7.7 请对下面的无向带权图， （1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁期卡尔算法求其最小生成树。 解：（1）图的邻接矩阵为

7.9试列出题7.9图中全部可能的拓扑有序序列,并指出应用7.5.1节中算法Topological Sort求得的是哪一个序列（注意：应先确定其存储结构）。 Status TopologicalSort(ALGraph G) FindIndegree(G,indegree);//对各顶点求入度 InitStack(S); For(i=0;inextarc){ k=p->adjvex; //对i号顶点的每个邻接点的入度减1 if（!(--indegree[k])）Push(S,k); //入度减为0，则入栈 }

第7章 图习题

第7章图 一、选择题 1．设无向图的顶点个数为n，则该图最多有( )条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n2 2．n个结点的完全有向图含有边的数目()。 A．n*n Ｂ．n(n＋１) C．n／2 D．n*(n－l) 3．在一个无向图中，所有顶点的度数之和等于所有边数( )倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。 A．1/2 B．2 C．1 D．4 4．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。 A．逆拓扑有序B．拓扑有序C．无序的 5．下面结构中最适于表示稀疏无向图的是( )，适于表示稀疏有向图的是( )。 A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表6．下列哪一种图的邻接矩阵是对称矩阵？( ) A．有向图B．无向图C．AOV网D．AOE网 7. 下列说法不正确的是( )。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向 D．图的深度遍历是一个递归过程 8.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是( ① )，而进行广度优先遍历得到的顶点序列是( ② )。 ①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确 ②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确 9．下面哪一方法可以判断出一个有向图是否有环(回路)： A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},G 的拓扑序列是( )。 A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 11. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。 A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 12. 关键路径是事件结点网络中( )。

第7章__图(1)

第七章图 一、选择题 1．一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学 1999 四、4 (4 分)】 A．n-1 B．n C．n+1 D．nlogn； 2．n个结点的完全有向图含有边的数目（）。【中山大学 1998 二、9 （2分）】 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 3．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学 2001 二、3 （2 分）】 A．1/2 B．2 C．1 D．4 4．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网 5. 下列说法不正确的是（）。【青岛大学 2002 二、9 （2分）】 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用 于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个 递归过程 二、判断题 1．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）【中科院软件所1997 一、4(1分）】 2. 有e条边的无向图，在邻接表中有e个结点。（）【南京理工大学 1998 二、5 （2 分）】 3．强连通图的各顶点间均可达。（）【北京邮电大学 2000 一、3 （1分）】 4．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（） 【东南大学 2001 一、4 （1分）】【中山大学 1994 一、3 （2分）】 5．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（） 【东南大学 2001 一、3 （1分）】【哈尔滨工业大学 1999 三、4】 6．需要借助于一个队列来实现DFS算法。（）【南京航空航天大学 1996 六、8 （1分）】 7. 最小代价生成树是唯一的。（）【山东大学 2001 一、5 （1分）】 8. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（） 【合肥工业大学 2000 二、7（1分）】 三、填空题 1．具有10个顶点的无向图，边的总数最多为_ ___。【华中理工大学 2000 一、7 （1分）】 2．G是一个非连通无向图，共有28条边，则该图至少有_____ _个顶点。 【西安电子科技大 2001软件一、8 （2分）】 3．N个顶点的连通图的生成树含有__ ____条边。【中山大学 1998 一、9 （1分）】 4．构造n个结点的强连通图，至少有__ ____条弧。【北京轻工业学院 2000 一、4（2分）】 5．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。【中科院计算所 1998 一、6（1分）】【中国科技大学1998 一、6（15/6分）】 6. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需___ __ _存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2分）】 四、应用题

数据结构第七章图练习及答案

一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、B、1C、2D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、B、1C、2D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、n D、n*n

11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1C、n-1D、n+e (2)A、e/2B、e C、2eD、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀罕图G，则G采用（邻接表）存储较省空间。 3、设有一粘稠图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I行）。

第7章 图(习题)

第7章图 习题 一、选择题 1、无向图G=(V,E),其中 V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 2、一个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn； 3、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 4、要连通具有n个顶点的有向图，至少需要（）条边。 A．n-l B．n C．n+l D．2n 5、求解最短路径的Floyd算法的时间复杂度为( )。 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 6、一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 7、在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 8、一个有向无环图的拓扑排序序列（）是唯一的。 A．一定 B．不一定 9、关键路径是事件结点网络中（）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 10、下列关于AOE网的叙述中，不正确的是（）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 二、填空题 1、克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。 2、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。 3、具有n个顶点e条边的有向图和无向图用邻接表表示，则邻接表的边结点个数分别为和条。 4、在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。 5、若n个顶点的连通图是一个环，则它有棵生成树。 6、N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。