数据结构第7章 图习题
第7章 图
一、单项选择题
1.在一个无向图G 中,所有顶点的度数之和等于所有边数之和的______倍。 A .l/2 C .2
B .1 D .4
2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的______倍。 A .l/2 C .2
B .1 D .4
3.一个具有n 个顶点的无向图最多包含______条边。 A .n C .n-1
B .n +1 D .n(n-1)/2
4.一个具有n 个顶点的无向完全图包含______条边。 A .n(n-l) C .n(n-l)/2
B .n(n+l) D .n(n-l)/2
5.一个具有n 个顶点的有向完全图包含______条边。 A .n(n-1) C .n(n-l)/2
B .n(n+l) D .n(n+l)/2
6.对于具有n 个顶点的图,若采用邻接矩阵表示,则该矩阵的大小为______。A .n C .n-1
7.无向图的邻接矩阵是一个______。 A .对称矩阵 C .上三角矩阵
B .零矩阵 D .对角矩阵 B .n ×n D .(n-l) ×(n-l)
8.对于一个具有n 个顶点和e 条边的无(有) 向图,若采用邻接表表示,则表头向量的大小为______。
A .n C .2n
B .e D .2e
9.对于一个具有n 个顶点和e 条边的无(有) 向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为______。
A .n C .2n
B .e D .2e
10.在有向图的邻接表中,每个顶点邻接表链接着该顶点所有______邻接点。A .入边
C .入边和出边
B .出边
D .不是入边也不是出边
11.在有向图的逆邻接表中,每个顶点邻接表链接着该顶点所有______邻接点。 A .入边
C .入边和出边
B .出边
D .不是人边也不是出边
12.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是______。
A .完全图 C .有回路
B .连通图 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 .无向图中的极大连通子图称为连通分量
B .连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C .图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D .有向图的遍历不可采用广度优先搜索方法
18.一个有向图G 的邻接表存储如下图7-1所示,现按深度优先搜索遍历,从顶点v 1出发,所得到的顶点序列是______。
A .v 1,v 2,v 3,v 4,v 5 B .v 1,v 2,v 3,v 5,v 4 C .v 1,v 2,v 4,v 5,v 3 D .v 1,v 2,v 5,v 3,v 4
图7-1 一个有向图的邻接表
19.对图7-2所示的无向图,从顶点1开始进行深度优先遍历,可得到顶点访问
序列______。
A .1,2,4,3,5
,7,6 B .1,2,4,3,5,6,7 C .1,2,4,5,6,3,7 D .1,2,3,4,5,7,6
图7-2 一个无向图
20.对图7-2所示的无向图,从顶点1开始进行广度优先遍历,可得到顶点访问
序列______。
A .1,3,2,4,5,6,7
B .1,2,4,3,5,6,7
C .1,2,3,4,5,7,6 D .2,5,1,4,7,3,6 21.一个无向连通图的生成树是含有该连通图的全部顶点的______。
A .极小连通子图 C .极大连通子图
B .极小子图 D .极大子图
22.设无向图 G=(V, E) 和G’= (V’, E’),如果 G’为G 的生成树,则下列说法中
不正确的是______。
A .G’为G 的连通分量 B .G’为G 的无环子图
C .G’为G 的子图 D .G’为G 的极小连通子图且V’=V 23. 任意一个无向连通图______最小生成树。 A .只有一棵 C .一定有多棵
B .有一棵或多棵 D .可能不存在
24.对于含有n 个顶点的带权连通图,它的最小生成树是指图中任意一个
________。
A .由n-1条权值最小的边构成的子图。 B .由n-1条权值之和最小的边构成的子图。 C .由n-1条权值之和最小的边构成的连通子图。 D .由n 个顶点构成的边的权值之和最小的生成树。
25.若一个有向图中的顶点不能排成一个拓扑序列,则可断定该有向图_______。 A .是个有根有向图 B .是个强连通图
C .含有多个入度为0的顶点 D .含有顶点数目大于1的强连通分量 26.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用____。
A .求关键路径的方法 B.求最短路径的Dijkstra 算法 C .广度优先遍历算法 D.深度优先遍历算法 27.求最短路径的Dijkstra 算法的时间复杂度为______。 A .O(n)
B .O(n+e)
C .O(n2) D .O(ne) 28.求最短路径的Floyd 算法的时间复杂度为______。 A .O(n) C .O(n2) 29.关键路径是事件结点网络中______。 A .从源点到汇点的最长路径
B .O(ne) D .O(n3)
B .从源点到汇点的最短路径
C .最长的回路 30.下面说法不正确的是______。
D .最短的回路
A .在AOE 网中,减少任一关键活动的权值后,整个工期也就相应减少 B .AOE 网工程工期为关键活动的权值和
C .在关键路径上的活动都是关键活动,而关键活动也必须在关键路径上 D .A 和B
31.下面说法不正确的是______。
A .关键活动不按期完成就会影响整个工程的完成时间 B .任何一个关键活动提前完成,将使整个工程提前完成 C .所有关键活动都提前完成,则整个工程提前完成 D .某些关键活动若提前完成,将使整个工程提前完成
二、填空题
1.对于具有n 个顶点的无向图G 最多有_________条边。 2.对于具有n 个顶点的强连通有向图G 至少有_________条边。 3.对于具有n 个顶点的有向图,每个顶点的度最大可达___________。 4.若无向图G 的顶点度数最小值大于___________时,G 至少有一条回路。 5.对于一个具有n 个顶点和e 条边的无向图,若采用邻接表表示,则表头向量的大小为___________,所有邻接表中的结点总数是__________。
6.已知一个有向图的邻接矩阵表示,删除所有从第i 个结点出发的弧的方法是____________。
7.对于n 个顶点的无向图,采用邻接矩阵表示,求图中边数的方法是__________,判断任意两个顶点i 和j 是否有边相连的方法是__________,求任意一个顶点的度的方法是___________。
8.对于n 个顶点的有向图,采用邻接矩阵表示,求图中边数的方法是_________,判断任意两个顶点i 和j 是否有边相连的方法是__________,求任意一个顶点的度的方法是__________。
9.无向图的连通分量是指___________。
10.已知图G 的邻接表如图7-3所示,从顶点v 1出发的深度优先搜索序列为________,从顶点1出发的广度优先搜索序列为_____________。
图7-3 图G 的邻接表
11.n 个顶点连通图的生成树一定有__________条边。 12.一个连通图的___________是一个极小连通子图。
13.Prim 算法适用于求_________的网的最小生成树,Kruskal 算法适用于求
________的网的最小生成树。
14.在AOV 图中,顶点表示________,有向边表示________。 15.可以进行拓扑排序的有向图一定是_________。
16.从源点到汇点长度最长的路径称为关键路径,该路径上的活动称为________。 17.Dijkstra 算法从源点到其它各顶点的路径长度按________次序依次产生,该
算法在边上的权出现_________情况时,不能正确产生最短路径。 18.求从某源点到其余各项点的Dijkstra 算法在图的顶点数为10,用邻接矩阵表
示图时计算时间约为10ms ,则在图的顶点数为40时,计算时间约为_________ms。
三、判断题
1.具有n 个顶点的无向图至多有n (n-1)条边。 2.有向图中各顶点的入度之和等于各顶点的出度之和。 3.邻接矩阵只储存了边的信息,没有存储顶点的信息。
4.对同一个有向图,只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多。
5.如果表示图的邻接矩阵是对称矩阵,则该图一定是无向图。
6.如果表示有向图的邻接矩阵是对称矩阵,则该有向图一定是有向完全图。
7.如果表示某个图的邻接矩阵不是对称矩阵,则该图一定是有向图。 8.连通分量是无向图的极小连通子图。 9.强连通分量是有向图的极大连通子图。
10.对有向图G ,如果以任一顶点出发进行一次深度优先或广度优先搜索能访问
到每一个顶点,则该图一定是完全图。
11.连通图的广度优先搜索中一般要采用队列来暂时刚访问过的顶点。 12.图的深度优先搜索中一般要采用栈来暂时刚访问过的顶点。 13.有向图的遍历不可采用广度优先搜索方法。 14.连通图的生成树包含了图中所有顶点。
15.设G 为具有n 个顶点的连通图,如果其中的某个子图有n 个顶点,n-1条边,则该子图一定是G 的生成树。 16.最小生成树是指边数最小的生成树。
17.从n 个顶点的连通图中选取n-1条权值最小的边,即可构成最小生成树。 18.只要无向网中没有权值相同的边,其最小生成树就是惟一的。 19.只要无向网中有权值相同的边,其最小生成树就可能不是惟一的。 20.有环图也能进行拓扑排序。
21.拓扑排序算法仅适用于有向无环图。
22.任何有向无环图的结点都可以排成拓扑排序,而且拓扑序列不惟一。 23.关键路径是由权值最大的边构成的。
24.在AOE 网中,减小任一关键活动上的权值后,整个工期也就相应减小。 25.在AOE 网中工程工期为关键活动上权值之和。
26.在关键路径的活动都是关键活动,而关键活动未必在关键路径上。 27.关键活动不按期完成就会影响整个工程的完成时间。 28.所有关键活动都提前完成,则整个工程将提前完成。 29.某些关键活动若提前完成,将可能使整个工程提前完成。 30.求单源最短路径的狄克斯特拉算法不适用于有回路的有向网。
四、简答题
1.图G 是一个非连通无向图,共有28条边,则该图至少有多少个顶点? 2.用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是
否有关?
3.对于稠密图和稀疏图,就存储而言,采用邻接矩阵和邻接表哪个更好些? 4.请回答下列关于图的一些问题:
(1)有n 个顶点的有向强连通图最多有多少条边?最少有多少条边? (2)表示一个有1000个顶点,1000条边的有向图的邻接矩阵有多少个矩阵
元素?是否为稀疏矩阵?
(3)对于一个有向图,不用拓扑排序,如何判断图是否存在环?
5.对n 个顶点的无向图和有向图,采用邻接表表示时,如何判别下列有关问题? (1)图中有多少条边?
(2)任意两个顶点i 和j 是否有边相连? (3)任意一个顶点的度是多少?
6.给出如图7-4所示的无向图G 的邻接矩阵和邻接表两种存储结构。并在给定的邻接表基础上,指出从顶点1出发的深度优先遍历和广度优先遍历序列。
图7-4 一个无向图
7.对于图7-5所示的有向图,试给出:
(1)邻接矩阵。 (2)邻接表 (3)强连通分量 (4)对照邻接表,给出从顶点1出发的深度优先遍历序列。 (5)对照邻接表,给出从顶点3出发的深度优先遍历序列。
图7-5 一个有向图
8.什么样的图其最小生成树是惟一的?
9.已知带权连通图G(V,E) 邻接表如图7-6所示,请画出该图,并分别以深度优
先和广度优先遍历该图,写出遍历中结点的序列,并画出该图的一棵最小生成树,其中表结点的3个域各为: 1. 2. 3 4. 5
图7-6 连通图的邻接表
10.已知世界6大城市为:北京(B )纽约(N )巴黎(P )伦敦(L )东京(T )
墨西哥城(M )试用由表1给出的交通网确定最小生成树,并说明所使用的方法及其时间复杂度。
11.对于图7-7所示的带权有向图,采用狄克斯特拉算法求从顶点1到其它顶点
的最短路径,要求给出求解过程。
图7-7 一个有向图 图7-8一个有向图
12.设图7-8中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试
问建在哪个村庄能使个村庄总体交通代价最小。
13.表2所示给出了某工程各工序之间的优先关系和各工序所需的时间。
表2 某工程各工序关系表
工序代号 A B C D E F G H I J K L M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作 - - A,B B C,D B E G ,I E I F,I H,J,K L G 完成如下各小题:
(1)画出相应的AOE 网
(2)列出事件的最早发生时间,最迟发生时间。 (3)找出关键路径并指明完成该工程所需的最短时间。 14.如图7-9所示的AOE 网,求:
(1)每项活动a i 最早开始时间e (a i ) 和最迟开始时间l (a i ) 。 (2)完成此工程最少需要多少天(设边上权值为天数)。 (3)哪些是关键活动
(4)是否存在某项活动,当其提高速度后能使整个工程缩短工期?
五、算法设计题
1.假设图G 采用邻接表存储,分别设计实现以下要求的算法: (1)求出图G 中每个顶点的入度。 (2)求出图G 中每个顶点的出度
(3)求出图G 中出度最大的一个顶点,输出该顶点的编号。 (4)计算图G 中出度为0的顶点数。
(5)判断图G 中是否存在边。
2.假设图G 采用邻接矩阵存储,分别设计实现以下要求的算法:
(1)求出图G 中每个顶点的入度。
(2)求出图G 中每个顶点的出度
(3)求出图G 中出度最大的一个顶点,输出该顶点的编号。
(4)计算图G 中出度为0的顶点数。
(5)判断图G 中是否存在边。
3.设计一个将邻接表转换为邻接矩阵的算法。
4.一个连通图采用邻接表作为存储机构,设计一个算法实现从顶点v 出发的深
度优先遍历的非递归过程。
5.设计一个算法,求不带权无向连通图G 中距离顶点v 的最远顶点。
6.设计一个算法,判断无向图G 是否是一棵树,若是树,返回1;否则返回0。
7.假设图采用邻接表存储,分别写出基于DFS 和BPS 遍历的算法来判别顶点i
和顶点j (i!=j)之间是否有路径。
8.假设图G 采用邻接表存储,设计一个算法,判断无向图G 是否连通,若连通
则返回1;否则返回0。
9.假设图G 采用邻接表存储,设计一个算法,输出图G 中从顶点u 到v 的长度
为1的所有简单路径。
10.假设图G 采用邻接表存储,设计一个算法,输出图G 中从顶点u 到v 的所
有简单路径。
11.假设图G 采用邻接表存储,设计一个算法,从如图7-10所示的无向图G 中
找出满足如下条件的一条路径:
(1)给定起点vi 和终点vj 。
(2)给定一组必经点{7,9},即输出的路径必须包含这些顶点。
(3)给定一组必避点{1,6},即输出的路径不能包含这些顶点。
图7-10
12.假设图G 采用邻接矩阵存储,采用遍历方法实际一个有向图的根的算法。
若有向图中存在一个顶点v ,从v 可以通过路径达达图中其它所有顶点,则称v 为该有向图的根。
13.假设图G 采用邻接矩阵存储,设计一个算法判断在给定的有向图中是否存
在一个简单有向回路,若存在,则以顶点序列的方法输出该回路(找到一条即可)。
14.采用堆排序来实现Kruskal 算法,并说明时间复杂度O(elog2e) 的理由。
15.如图7-11是一个城市连接图,图中权值表示两城市之间的里程(单位为
100km ),现要设计一条铁路贯通所有城市(即从一个任一城市可以到达其他城市)。设计一个算法,求出最小代价。假设每1km 的铁路造价为1000万元。
图7-11 城市连通图
16.利用狄克斯特拉算法,设计一个可产生从指定顶点出发的最小生成树的算法。
17.设计一个算法求图的中心点。设v 是有向图G 的一个顶点,把v 的偏心度
定义为:MAX{从w 到v 的最短距离|wV(G)}如果v 是有向图G 中具有最小偏心度的顶点,则称顶点v 是G 的中心点。
18.假设图G 采用邻接矩阵存储,采用弗洛伊德算法设计一个求有向图的根的
算法。若有向图中存在一个顶点v ,从v 可以通过路径到达图中其他所有顶点,则称v 为该有向图的根。
19.设计一个算法,判断有向图是否存在回路。
20.对于一个使用邻接表存储的带权有向图G 。试利用深度优先搜索方法,对该
图中所有顶点进行逆向拓扑排序。若邻接表的数据类型定义为AGraph ,则算法的首部为:void dfs_topsort(AGraph *G) 若拓扑排序成功,表示图中不存在环;否则表示图中存在环。在这个算法中嵌套一个递归深度优先搜索算
法为:Dfs(AGaph G , int v) 在遍历图的同时进行逆序拓扑排序,其中,v 是顶点编号。
(1)给出该图的邻接表定义
(2)定义在算法中使用的全局辅助数组
(3)写出逆向拓扑排序的算法。
21.假设AOE 网以邻接表方式存储,设计一个算法求该AOE 网的所有关键活
动。