数据结构第五章图习题.doc

05　图
【单选题】
1. 设无向图G中有五个顶点，各顶点的度分别为2、4、3、1、2，则G中边数为（C）。
Ａ、4条　Ｂ、5条　Ｃ、6条　Ｄ、无法确定

2. 含n个顶点的无向完全图有（D）条边；含n个顶点的有向图最多有（C）条弧；含n个顶点的有向强连通图最多有（C）条弧；含n个顶点的有向强连通图最少有（Ｆ）条弧；设无向图中有n个顶点，则要接通全部顶点至少需（G）条边。
A、n2　B、n(n+1)　C、n(n-1)　D、n(n-1)/2　E、n+1　F、n　G、n-1

3. 对下图从顶点a出发进行深度优先遍历，则（A）是可能得到的遍历序列。
A、acfgdeb　B、abcdefg　C、acdgbef　D、abefgcd
　对下图从顶点a出发进行广度优先遍历，则（D）是不可能得到的遍历序列。
A、abcdefg　B、acdbfge　C、abdcegf　D、adcbgef

4. 设图G的邻接矩阵A=，则G中共有（C）个顶点；若G为有向图，则G中共有（D）条弧；若G为无向图，则G中共有（B）条边。
A、1　B、2　C、3　D、4　E、5　F、9　G、以上答案都不对

5. 含n个顶点的图，最少有（B）个连通分量，最多有（D）个连通分量。
A、0　B、1　C、n-1　D、n

6. 用邻接表存储图所用的空间大小（A）。
A、与图的顶点数和边数都有关　B、只与图的边数有关
C、只与图的顶点数有关　D、与边数的平方有关

7. n个顶点的无向图的邻接表最多有（B）个表结点。
A、n2 B、n(n-1) C、n(n+1) D、n(n-1)/2

8. 无向图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

9. 图的BFS生成树的树高比DFS生成树的树高（A）。
A、小或相等 B、小 C、大或相等 D、大

10. 下列不正确的是（C）。
(1)求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；
(2)利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）
(3)Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。
A、(1),(2),(3)　B、(1)　C、(1),(3)　D、(2),(3)

11. 当各边上的权值（A）时，BFS算法可用来解决单源最短路径问题。
A、均相等　B、均互不相等　C、不一定相等

12. 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（C）。
A、对称矩阵　B、稀疏矩阵　C、三角矩阵　D、一般矩阵

13. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。
A、G中有弧<Vi,Vj>　B、G中有一条从Vi到Vj的路径
C、G中没有弧<Vi,Vj>　D、G中有一条从Vj到Vi的路径

14. 关键路径是AOE网中（B）。
A、从始点到终点的最短路径　B、从始点到终点的最长路径
C、人始点到终点的边数最多的路径　D、从始点到终点的边数最少的路径

15. 下面关于求关键路径的说法不正确的是（C）。
A、求关键路径是以拓扑排序为基础的
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D、关键活动一定位于关键路径上

【填空题】
1. 设无向连通图G含n个顶点e条边，则G的生成树含　　　　个顶点　　　　条边。
2. 连通分量是无向图的　　　　　　子图，生成树是无向连通图的　　　　　　子图。
3. 对稀疏图而言，在邻接矩阵和邻接表这两种存储结构中选择　　　　　　更为适宜。
4. 设无向图G含n个顶点e条边，则G的邻接表表示中含　　　　　　个边表结点。
5. 设有向图G含n个顶点e条弧，则G的邻接表表示中含　　　　　　个边表结点。

【计算题】
1. 设无向图如下，写出对该图从顶点a出发进行广度优先遍历可能得到的所有遍历序列。

解：abcdefg、abdcegf、acbdfeg、acdbfge、adbcgef、adcbgfe。

2. 设有向图如下，写出对该图从顶点a出发进行深度优先遍历可能得到的所有遍历序列。

解：abedc、acbed、acdbe。

3. 设无向网如下，(1)写出其邻接矩阵；(2)基于该邻接矩阵求深度优先生成树和广度优先生成树；(3)基于该邻接矩阵按普里姆算法求最小生成树；(4)写出其邻接表；(5)基于该邻接表按克鲁斯卡尔算法求最小生成树。

解：
(1)
(2)深度优先生成树：；广度优先生成树：
(3)最小生成树：；求解过程：
(4)邻接表：
(5)最小生成树：

4. 设AOV图如下，写出对该图进行拓扑排序可能得到的所有拓扑序列。

解：abcdefg、abcdfeg、abcfdeg

5. 设AOE网如下，试求关键路径。

解：关键路径１：v1→v2→v5→v7　关键路径２：v1→v3→v6→v7。

6. 设有向网如下，试用迪杰斯特拉算法求从顶点A出发到其余各顶点的最短路径。

解：ab：3　af：5　afe：7　abc：11　afed：14

7. 设有向网如下，试用弗洛伊德算法求图中各对顶点间的最短路径。
解：

【算法题】
下列算法题中可能用到的类如下：
public class MGraph{
private Object vexs[];
private int adj[][];
private int vexnum;
private int arcnum;
public MGraph(int maxvn){
int i, j;
vexs=new Object[maxvn];
adj=new int[maxvn][maxvn];
for(i=0;i<maxvn;i++)
for(j=0;j<maxvn;j++)
adj[i][j]=0;
vexnum=0;
arcnum=0;
}//构造函数
}//图的邻接矩阵存储结构类

public class ALANode{
public int adj;
public ALANode next;
}//图的邻接表存储结构中的表结点类

public class ALVNode{
public Object data; //顶点信息
public ALANode firstarc;
}//图的邻接表存储结构中的头结点类

public class ALGraph{
private ALVNode vexs[];
private int vexnum;
private int arcnum;
public ALGraph(int maxvn){
vexs=new ALVNode[maxvn];
vexnum=0;
arcnum=0;
}//构造函数
}//图的邻接表存储结构类

1. 在ALGraph类中添加符合如下要求的构造函数
⑴public ALGraph(Object[ ] v, ArcArray [ ] a)
其中v为顶点向量，a为弧向量，类ArcArray的定义如下：
public class ArcArray{
private int index1; //弧尾顶点下标
private int index2; //弧头顶点下标
}
(2)public ALGraph(MGraph g)

2. 在ALGraph类中添加实现如下功能的方法：
(1)在无向图中插入一个顶点；
(2)在无向图中删除一个顶点；
(3)在无向图中添加一条边；
(4)在无向图中删除一条边。
(5)判定无向图中是否存在从顶点vi到顶点vj的路径（i≠j）。
(6)输出无向图中从顶点vi到顶点vj的所有简单路径。
解：
(5)
public boolean path(int i, int j){
//从顶点vi出发进行深度优先遍历，调用完成时所有与vi有路径相通的顶点都被访问到
boolean visited[ ]=new boolean[vexs.length];
for(k=0;k<vexnum;k++) visited[k]=false;
dfs(i, visited);
return visited[j];
}//path
void dfs(int i, boolean[ ] visited){//从顶点vi出发对图G进行深度优先遍历
visited[i]=true;
for(p=vexs[i].firstarc;p;p=p.next)
if (!visited[p.adj]) dfs(p.adj, visited);
}//dfs

3. 在MGraph类中添加符合如下要求的构造函数：
(1)public class MGraph(Object[ ] v, EdgeArray [ ] e)
其中v为顶点向量，e为边向量，类EdgeArray的定义如下：
public class EdgeArray{
public int index1; //顶点1下标
public int index2; //顶点2下标
}
(2)public MGraph(ALGraph g)

4. 在MGraph类中添加实现如下功能的方法：
(1)在有向图中插入一个顶点；
(2)在有向图中删除一个顶点；
(3)在有向图中添加一条边；
(4)在有向图中删除一条边。
(5)判定有向图中从顶点vi到顶点vj是否存在一条长为k的简单路径。