第7章 图 自测卷 姓名 班级
题号
一
二
三
四
五
总分
题分
16
20
24
10
30
100
得分
一、单选题（每题1分，共16分）
（ ）1,在一个图中，所有顶点的度数之和等于图的边数的 倍。
A．1/2 B,1 C,2 D,4
（ ）2,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A．1/2 B,1 C,2 D,4
（ ）3,有8个结点的无向图最多有 条边。
A．14 B,28 C,56 D,112
（ ）4,有8个结点的无向连通图最少有 条边。
A．5 B,6 C,7 D,8
（ ）5,有8个结点的有向完全图有 条边。
A．14 B,28 C,56 D,112
（ ）6,用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A．栈 B,队列 C,树 D,图
（ ）7,用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A．栈 B,队列 C,树 D,图
（ ）8,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是
（ ）9,已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是
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 1 3 4 2 5 6
（ ）10,已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
A,0 2 4 3 6 5 1 B,0 1 3 6 4 2 5 C,0 4 2 3 1 5 6 D,0 1 3 4 2 5 6
（ ）11,已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
A,0 2 4 3 1 6 5 B,0 1 3 5 6 4 2 C,0 1 2 3 4 6 5 D,0 1 2 3 4 5 6
（ ）12,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是
（ ）13,已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是
（ ）14,深度优先遍历类似于二叉树的
A．先序遍历 B,中序遍历 C,后序遍历 D,层次遍历
（ ）15,广度优先遍历类似于二叉树的
A．先序遍历 B,中序遍历 C,后序遍历 D,层次遍历
（ ）16,任何一个无向连通图的最小生成树
A．只有一棵 B,一棵或多棵 C,一定有多棵 D,可能不存在
二、填空题（每空1分，共20分）
1,图有,等存储结构，遍历图有,等方法。
2,有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 。
3,如果n个顶点的图是一个环，则它有 棵生成树。
4,n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。
5,n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。
6,设有一稀疏图G，则G采用 存储较省空间。
7,设有一稠密图G，则G采用 存储较省空间。
8,图的逆邻接表存储结构只适用于 图。
9,已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 。
10,图的深度优先遍历序列 惟一的。
11,n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接表存储时，该算法的时间复杂度为 。
12,n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 ；若采用邻接表存储，该算法的时间复杂度为 。
13,图的BFS生成树的树高比DFS生成树的树高 。
14,用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 。
15,若要求一个稀疏图G的最小生成树，最好用 算法来求解。
16,若要求一个稠密图G的最小生成树，最好用 算法来求解。
17,用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。
18,拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的。
三、简答题（每题6分，共24分）
1,【严题集7.1①】已知如图所示的有向图，请给出该图的:
每个顶点的入/出度；
邻接矩阵；
邻接表；
逆邻接表。
2,【严题集7.7②】请对下图的无向带权图：
写出它的邻接矩阵，并按普里姆算法求其最小生成树；
写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
3,【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
4,【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。
四、给定下列网G,（10分）
1 试着找出网G的最小生成树，画出其逻辑结构图；
2 用两种不同的表示法画出网G的存储结构图；
3 用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。
五、算法设计题（每题10分，共30分）
1,【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息，以建立邻接表
{
return OK;
}//Build_AdjList
2,【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。
（如果要删除所有从第i个顶点出发的边呢？ 提示,将邻接矩阵的第i行全部置0 ）
解,//设本题中的图G为有向无权图
Status DeleteArc(MGraph &G,char v,char w) //在邻接矩阵表示的图G上删除边(v,w)
{
}
return OK;
}//Delete_Arc
3,【严题集7.22③】试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
附加题：【严题集7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。
（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。
注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）
题号
一
二
三
四
五
总分
题分
16
20
24
10
30
100
得分
一、单选题（每题1分，共16分）
（ ）1,在一个图中，所有顶点的度数之和等于图的边数的 倍。
A．1/2 B,1 C,2 D,4
（ ）2,在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A．1/2 B,1 C,2 D,4
（ ）3,有8个结点的无向图最多有 条边。
A．14 B,28 C,56 D,112
（ ）4,有8个结点的无向连通图最少有 条边。
A．5 B,6 C,7 D,8
（ ）5,有8个结点的有向完全图有 条边。
A．14 B,28 C,56 D,112
（ ）6,用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A．栈 B,队列 C,树 D,图
（ ）7,用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A．栈 B,队列 C,树 D,图
（ ）8,已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是
（ ）9,已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是
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 1 3 4 2 5 6
（ ）10,已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
A,0 2 4 3 6 5 1 B,0 1 3 6 4 2 5 C,0 4 2 3 1 5 6 D,0 1 3 4 2 5 6
（ ）11,已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是
A,0 2 4 3 1 6 5 B,0 1 3 5 6 4 2 C,0 1 2 3 4 6 5 D,0 1 2 3 4 5 6
（ ）12,已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是
（ ）13,已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是
（ ）14,深度优先遍历类似于二叉树的
A．先序遍历 B,中序遍历 C,后序遍历 D,层次遍历
（ ）15,广度优先遍历类似于二叉树的
A．先序遍历 B,中序遍历 C,后序遍历 D,层次遍历
（ ）16,任何一个无向连通图的最小生成树
A．只有一棵 B,一棵或多棵 C,一定有多棵 D,可能不存在
二、填空题（每空1分，共20分）
1,图有,等存储结构，遍历图有,等方法。
2,有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 。
3,如果n个顶点的图是一个环，则它有 棵生成树。
4,n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 。
5,n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 。
6,设有一稀疏图G，则G采用 存储较省空间。
7,设有一稠密图G，则G采用 存储较省空间。
8,图的逆邻接表存储结构只适用于 图。
9,已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 。
10,图的深度优先遍历序列 惟一的。
11,n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 ；若采用邻接表存储时，该算法的时间复杂度为 。
12,n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 ；若采用邻接表存储，该算法的时间复杂度为 。
13,图的BFS生成树的树高比DFS生成树的树高 。
14,用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 。
15,若要求一个稀疏图G的最小生成树，最好用 算法来求解。
16,若要求一个稠密图G的最小生成树，最好用 算法来求解。
17,用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。
18,拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完成的。
三、简答题（每题6分，共24分）
1,【严题集7.1①】已知如图所示的有向图，请给出该图的:
每个顶点的入/出度；
邻接矩阵；
邻接表；
逆邻接表。
2,【严题集7.7②】请对下图的无向带权图：
写出它的邻接矩阵，并按普里姆算法求其最小生成树；
写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。
3,【严题集7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
4,【严题集7.11②】试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。
四、给定下列网G,（10分）
1 试着找出网G的最小生成树，画出其逻辑结构图；
2 用两种不同的表示法画出网G的存储结构图；
3 用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。
五、算法设计题（每题10分，共30分）
1,【严题集7.14③】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。
解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息，以建立邻接表
{
return OK;
}//Build_AdjList
2,【严题集7.15③】试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w)，即删除一条边的操作。
（如果要删除所有从第i个顶点出发的边呢？ 提示,将邻接矩阵的第i行全部置0 ）
解,//设本题中的图G为有向无权图
Status DeleteArc(MGraph &G,char v,char w) //在邻接矩阵表示的图G上删除边(v,w)
{
}
return OK;
}//Delete_Arc
3,【严题集7.22③】试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
附加题：【严题集7.27④】采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。
（注1：一条路径为简单路径指的是其顶点序列中不含有重现的顶点。
注2：此题可参见严题集P207-208中有关按“路径”遍历的算法基本框架。）
