数据结构单元8练习参考答案.doc

单元练习8

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（√）（1）图可以没有边，但不能没有顶点。
（ㄨ）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。
（ㄨ）（3）邻接表只能用于有向图的存储。
（√）（4）一个图的邻接矩阵表示是唯一的。
（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。
（ㄨ）（6）有向图不能进行广度优先遍历。
（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。
（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。
（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。
（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。

二．填空题
（1） 图常用的存储方式有邻接矩阵和 邻接表 等。
（2） 图的遍历有： 深度优先搜 和广度优先搜等方法。
（3） 有n条边的无向图邻接矩阵中，1的个数是 _2n____。
（4） 有向图的边也称为 _ 弧___ 。
（5） 图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。
（6） 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。
（7） n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： O（n2） 。
（8） n个顶点e条边的图若采用邻接表存储，则空间复杂度为： O（n+e） 。
（9） 设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。
（10） 设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。
（11） 图的逆邻接表存储结构只适用于 __有向____图。
（12） n个顶点的完全无向图有 n(n-1)/2_ 条边。
（13） 有向图的邻接表表示适于求顶点的 出度 。
（14） 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的 入度 。
（15） 对于具有n个顶点的图，其生成树有且仅有 n-1 条边。
（16） 对n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结点。
（17） 从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图
的 遍历 。
（18） 无向图的邻接矩阵一定是 对称 矩阵。
（19） 一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。
（20） 若要求一个稠密图G的最小生成树，最好用 Prim 算法来求解。

三．选择题
（1）在一个图中，所有顶点的度数之和等于图的边数的( C )倍。
A．1/2 B. 1 C. 2 D. 4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。
A．1/2 B. 1 C. 2 D. 4
（3）对于一个具有n个顶点的有向图的边数最多有（ B ）。
A．n B．n(n-1) C．n(n-1)/2 D．2n
（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。
A．n B．n+1 C． n-1 D．n/2
（5）有8个结点的有向完全图有( C )条边。
A．14 B. 28 C. 56 D. 112
（6）深度优先遍历类似于二叉树的( A )。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历
（7）广度优先遍历类似于二叉树的( D )。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历
（8）任何一个无向连通图的最小生成树( A )。
A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在
（9）无向图顶点v的度是关联于该顶点（ B ）的数目。
A．顶点 B．边 C．序号 D．下标
（10）有n个顶点的无向图的邻接矩阵是用（ B ）数组存储。
A．一维 B．n行n列 C．任意行n列 D．n行任意列
（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ C ）。
A．n-1 B．n+1 C．n D．n+e
（12）在图的表示法中，表示形式唯一的是（ A ）。
A．邻接矩阵表示法 B．邻接表表示法
C．逆邻接表表示法 D．邻接表和逆邻接表表示法
（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（ C ）。
A．n B．e C． 2n D．2e
（14）下列图中，度为3的结点是（ B ）。
1
2
3
5
4

A．V1 B. V2 C. V3 D. V4
1
2
3
5
4
（15）下列图是（ A ）。

A．连通图 B. 强连通图 C. 生成树 D. 无环图

（16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（ D ）。
a
b
c
f
d
e

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）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（ A ）。
a
b
c
f
d
e

A. a，b，e，c，d，f
B. a，b，e，c，f，d
C. a，e，b，c，f，d
D. a，e，d，f，c，b

（18）最小生成树的构造可使用（ A ）算法。
A．prim算法 B．卡尔算法 C．哈夫曼算法 D．迪杰斯特拉算法
（19）下面关于图的存储结构的叙述中正确的是（ A ）。
A． 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关
B． 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关
C． 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关
D． 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关
（20）连通分量是（ C ）的极大连通子图。
A．树 B．图 C．无向图 D．有向图

四．应用题（30分）
1．有向图如下图所示，画出邻接矩阵和邻接表
①
②②②②
③②②②
④②②②
⑤②②②

解：
（1）邻接矩阵
1 2 3 4 5

（2）邻接表
1

2

3

5
∧
2

4
∧

3

5
∧

4

1
∧

5

4
∧

2． 已知一个无向图有6个结点，9条边，这9条边依次为（0，1）,（0，2）,（0，4）,（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。（5分）
2
3
1D
0

4
5
解：

从顶点0出发的深度优先搜索遍历的结点序列：0 1 2 3 4 5（答案不唯一）
从顶点0出发的广度优先搜索遍历的结点序列：0 1 2 4 5 3（答案不唯一）

3． 已知一个无向图的顶点集为：{a，b，c，d，e}，其邻接矩阵如下，画出草图，写出顶点a出发按深度优先搜索进行遍历的结点序列。（5分）

解：
a
c
b
e
d

（1） （2）深度优先搜索：
a b d c e （答案不唯一）
广度优先搜索：
a b e d c （答案不唯一）

4．网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

2
5
4
3
1

2
5
4
3
1

解： 最小生成树：
8 11
10 8
3 4
13 7 3 4
7

5. 已知某图G的邻接矩阵如图，

（1）画出相应的图；
（2）要使此图为完全图需要增加几条边。

解：
1
3
4
2
4
2D
3
1

（1）

（2） 完全无向图应具有的边数为：n*(n-1)1/2=4*(4-1)/2=6，所以还要增加2条边（如右图）。
6．已知如图所示的有向图，请给出该图的:

（1） 每个顶点的入/出度；
（2） 邻接表；
（3） 邻接矩阵。

解：
（1） （2）
顶点
1
2
3
4
5
6
入度
3
2
1
1
2
2
出度
0
2
2
3
1
3

（3）

7．如图，请完成以下操作：
（2） 写出无向带权图的邻接矩阵；
（3） 设起点为a，求其最小生成树。

解：
（1）邻接矩阵为： （2）起点为a，可以直接由原始图画出最小生成树

8．给定下列网G:

（1） 画出网G的邻接矩阵；
（2） 画出网G的最小生成树。

解：
（1）邻接矩阵 （2）最小生成树
F
B
ED
A

C
G
D

五．程序题填空题
图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边(v,w)的操作：DeleteArc(G,v,w)。若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并返回“OK”。
（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0 ）
解：
Status DeleteArc(MGraph &G,char v,char w) //在邻接矩阵表示的图G上删除边(v,w)
{ if ((i=LocateVex(G,v))<0) return ERROR ;
if ((j=LocateVex(G,w))<0) return ERROR ;
if (G.arcs[i][j].adj)
{ G.arcs[i][j].adj= 0 ;
G.arcnum -- ; （或 G.arcnum=G.arcnum-1 ）
}
return OK ;
}

六．算法题
1． 编写一个无向图的邻接矩阵转换成邻接表的算法。
2． 以知有n个顶点的有向图邻接表，设计算法分别实现以下功能：
（1）求出图G中每个顶点的出度、入度。
（2）求出G中出度最大的一个顶点，输出其顶点序号。
（3）计算图中度为0的顶点数。

1． 解：本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接表的第i个单链表上增加一个j结点。
void trans(int edges[n][n],Adjlist adj)
{ int i,j;
edgenode *p;
for (i=0;i<n;i++)
{ adj[i].data=i;
adj[i].link=NULL;
}
for (i=0;i<n;i++)
for (j=0;j<n;j++)
{ if(edges[i][j]==1)
{ p=(edgenode *) malloc (sizeof(edgenode));
p->adjvex=j;
p->next=adj[i].link;
adj[i].link=p;
}
}
}
2．
（1）求出度的思想：计算出邻接表中第i个单链表的结点数即可。
int outdegree(adjlist adj,int v)
{ int degree=0;
edgenode *p;
p=adj[v].link;
while (p!=NULL)
{ degree++;
p=p->next;
}
return degree;
}
void printout(adjlist adj,int n)
{ int i,degree;
printf("The Outdegree are:\n");
for(i=0;i<n;i++)
{ degree=outdegree(adj,i);
printf("(%d,%d)",i,degree);
}
}
求入度的思想：计算出邻接表中结点i的结点数即可。
int indegree(adjlist adj,int n,int v)
{ int i,j,degree=0;
edgenode *p;
for (i=0;i<n;i++)
{ p=adj[i].link;
while (p!=NULL)
{ if (p->adjvex==v)
degree++;
p=p->next;
}
}
return degree;
}
void printin(adjlist adj,int n)
{ int i,degree;
printf("The Indegree are:\n");
for (i=0;i<n;i++)
{ degree=Indegree(adj,n,i);
printf("(%d,%d)",i,degree);
}
}
（2）求最大度的算法
void maxoutdegree(adjlist adj,int n)
{ int maxdegree=0,maxv=0,degree,i;
for (i=0;i<n;i++)
{ degree=outdegree(adj,i);
if (degree>maxdegree)
{ maxdegree=degree;
maxv=i;
}
}
printf("maxoutdegree %d,maxvertex=%d",maxdegree,maxv);
}

（3）求度为0的顶点数的算法
int outzero(adjlist adj,int n)
{ int num=0,i;
for (i=0;i<n;i++)
{ if (outdegree(adj,i)==0)
num++;
}
return num;
}

模拟考题
1． 已知如图所示的有向图，请给出该图的:

（1） 每个顶点的入度和出度；
（2） 逆邻接表。

解：
（1） （2）
顶点
1
2
3
4
5
6
入度
3
2
1
1
2
2
出度
0
2
2
3
1
3

2． 给定下列网G:

（1） 写出网G以B为顶点的广度优先遍历的序列；
（2） 画出网G的最小生成树。
解：（1）以B为顶点的广度优先遍历的序列： （2）最小生成树
F
B
ED
A

C
G
D
B A E F C G D

3． 无向图G如图所示，（1）试画出邻接矩阵；（2）写出从A出发的深度优先遍历的序列。
D
C
AD
B

G
E
F

解：（1） 邻接矩阵 （2）从A出发的深度优先遍历的序列：
A B D C E G F（不唯一）

3． 已知图G的邻接表如下，以顶点1为出发点，完成下列问题：

1

2

5

4
∧

2

3

1
∧

3

5

2
∧

4

1

5
∧

5

4

1

3
∧
（1）写出以顶点1为出发点的广度优先遍历序列；
（2）画出以顶点1为出发点的深度优先搜索得到的一棵二叉树。
解：（1）广度优先遍历序列：1，2，5，4，3
（2）深度优先搜索得到的一棵二叉树：
5
3
2D
1

4
5
3
2D
1

4

5． 试填空完成深度优先搜索的递归函数。
#define MAXVEX 100 // 定义图的最大顶点数
struct vertex
{ int num; // 顶点编号
char data; // 顶点的信息
};
typedef struct graph
{ struct vertex vexs[MAXVEX]; // 顶点集合
int edges[MAXVEX][ MAXVEX]; // 边的集合
}sdjmax;
int visited[MAXVEX];
void dfs(adjlist adj,int v) // 深度优先搜索的递归函数
{ int i;
struct edgenode *p;
for (i=1;i<=n;i++)
visited[i]=0; // 给visited数组赋初值0
visited[v]=1;
cin v; // 取v的边的表头指针
p= adj[v]->link ;
while ( p!=NULL )
{ if (visited[p->adjvex]== 0 ) // 从v的未访问过的邻接点出发进行深度优先搜索
dfs(adjlist, p->adjvex );
p= p->next ; // 找v的下一个邻接点
}
}

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！