发布时间 : 星期四 文章数据结构习题册更新完毕开始阅读
的拓扑排序序列是唯一的。
24、下面结论中不正确的是（ ）。
A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按广度优先搜索遍历的结果是唯一的。 C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。 D、图的多重邻接表表示法中，表中结点数目是图中边的条数。
25、在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A、1/2 B、1 C、2 D、4
26、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A、1/2 B、1 C、2 D、4
27、判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（ ） A、求关键路径的方法 B、求最短路径的DIJKSTRA方法 C、广度优先遍历算法 D、深度优先遍历算法 28、任何一个带权的无向连通图的最小生成树（ ）
A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在 29、以下说法正确的是（ ）
A、连通图的生成树，是该连通图的一个极小连通子图。
B、无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C、任何一个有向图，其全部顶点可以排成一个拓扑序列。 D、有回路的图不能进行拓扑排序。 30、以下说法错误的是（ ）
A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。 C、存储无向图的邻接矩阵是对称的，因此也可以只要存储邻接矩阵的下（或上）三角部分。
D、用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am
的第 i行第j列的元素是否为0即可。 31、以下说法正确的是（ ）
A、连通分量是无向图中的极小连通子图。 B、强连通分量是有向图中的极大强连通子图。
C、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧
D、对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 二、 判断题
1、用邻接矩阵法存储一个图时，所占用的存储空间大小仅与图中结点个数有关。
2、对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。 3、任何有向网拓扑排序的结果是唯一的。 4、有回路的图不能进行拓扑排序。 5、存储有向图的邻接矩阵是对称的。
6、一个有向图G中若有弧
7、在AOE网中一定有一条关键路径。
8、含有10个顶点的无向连通图其生成树含有9条边。 9、十字链表是图的一种顺序表示法。
三、 填空题
13
1、对具有n个顶点的图，其生成树有且仅有__________条边，即生成树是图的边数__________的连通图。 2、一个无向图有n个顶点和e条边，则所有顶点的度数之和为（ ），其邻接矩阵是一个关于__________对称的矩阵。
3、在图形结构中，每个结点的前驱结点和后继结点可以有（ ）。
5、设无向图G的顶点数为n，图G最少有（ ）边，最多有（ ）条边。若G为有向图，有n个顶点，则图G最少有（ ）条边，最多有（ ）条边。具有n个顶点的无向完全图，边的总数为（ ）条，而有n个顶点的有向完全图，边的总数为（ ）条。
6、在无权图G的邻接矩阵A中，若(vi,vj)或
7、在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（ ）。 8、已知一个图的邻接矩阵表示，计算第I个顶点的入度方法为（ ） 9、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（ ），而对于无向图而言等于该顶点的（ ）。
10、已知图G的邻接表如图7.4所示，其从顶点V1出发的深度优先搜索序列为__________，其从顶点V1出发的广度优先搜索序列为__________。 4 1 3 ∧ 0 V1 4 ∧ 1 V2 2 2 V3 5 ∧ 3 V ∧ 4 4 V5 5 3 2 ∧ 5 V6 ∧
图7.4
11、n个顶点的弱连通有向图G最多有（ ）条弧，最少有（ ）条弧。 12、在n个顶点e条边的连通图中，连通分量个数为（ ）。
13、任何（ ）的有向图，其所有结点都可以排 在一个拓扑序列中，拓扑排序的方法是先从图中选一个（ ）为0的结点且输出，然后从图中删除该结点及其（ ），反复执行，直到所有结点都输出为止。 14、一个连通图的（ ）是一个极小连通子图。
15、在AOE网中，从源点到汇点各活动时间总和最长的路径为（ ）。
16、在有向图的邻接矩阵上，由第i行可得到第__________个结点的出度，而由第j列可得到第__________个结点的入度。
17、对无向图，设有n个结点，e条边，则其邻接表表示中需要__________个表结点，对有向图，设有n个顶点，e条弧，则其邻接表表示需要__________个表结点。
18、在无权图G的邻接矩阵A中，若 (Vi,Vj)或
19、已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是__________。
删除所有从第i个结点出发的边的方法是__________。
20、设无向图G中顶点数为n，则图G最少有__________条边，最多有 条边。若G为有向图，有n个顶点，则图至少有__________条边，最多有__________条边。
21、某作业工程表示成网络图，如图7.5所示。事件5的最早完成时间是_______。事件4的最迟开始时间是________。事件5的迟缓时间是________。关键路径是__________。
14
e4=4 4 1 e8=12
e1=5 e9=6
2 0 9 e5=10 5 e10=10 e2=9 e3=14 e14=8 6 e11=5
8 e6=3 e12=5
3 e13=8 e7=7
7 图7.5
22、设x,y∈V，若
23、在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为________。 24、连通分量是无向图中的________连通子图。
25、对无向图，若它有n个顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成头结点，________个结点构成边结点表。
26、对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________个结点构成头结点，________个结点构成边结点表。 27、在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为________的结点的个数是顶点vi的入度。
28、遍历图的基本方法有________优先搜索和________优先搜索两种。
四、 简答题
1、 对于一个具有n个顶点的连通无向图，如果它有且只有一个简单回路，此图有几条边？一个具有n
个顶点的弱连通图至少有几条边？
2、 已知某图的邻接表，如何建立该图的邻接矩阵？
3、 简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操作中有什么优越性？ 什么是AOE网的关键路径？
五、补充应用题
1. 给出无向图如图7.6所示的G1的邻接矩阵和邻接表。
V1 V2 V1 V2 V1
V4 V3 V4 V5 V3 V4 V5
G2 G3
V3
G1 7.6 所示的 G 2 的邻接矩阵、邻接表和逆邻接表。 图7.6 2. 分别给出图
15
V2 V5 3. 分别给出图7.6所示的G3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶点序列。 4. 求出图7.7的连通分量。
V1 V2 V6 V3 V8 V7 V V5 4 图7.7 5. 设有一无向图G=(V,E),其中
V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。 (1)按上述顺序输入后，画出其相应的邻接表；
(2)在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
6. 已知连通网的邻接矩阵如图7.8所示，顶点集合为{v1,v2,v3,v4,v5}，试画出它所表示的从顶点v1开始
利用Prim算法得到的最小生成树。
?? 1 12 510??1?89??? ??128??2?
? ? ?59??4? ??10?24???
图7.8
1 4 2 7 6 8 5 3 9 图7.9
7. 拓扑排序的结果不是唯一的，对图7.9进行拓扑排序，写出全部不同的拓扑排序序列。 8. 已知图G的邻接表如图7.10所示，顶点V1为出发点，完成要求： （1） 深度优先搜索的顶点序列； （2） 广度优先搜索的顶点序列；
（3） 由深度优先搜索得到的一棵生成树； 1 （4） 由广度优先搜索得到的一棵生成树。 1 4 2 3 2 V1 1 3 4 ∧ 5 4 V2 0 2 5 ∧ 3 8 4 V3 1 4 5 ∧ V4 0 4 V5 0 2 3 5 ∧ 5 2 6 3 6 V6 1 2 4 ∧ 4 5
7 图7.10
图7.11
9. 图7.11所示为一无向连通网络，要求根据Prim算法和Kruskal构造出它的最小生成树。
16