数据结构第7章-图习题.doc

第7章 图
一、单项选择题
１.在一个无向图G中，所有顶点得度数之与等于所有边数之与得______倍.
A。l/2 B．1
C.2ﻩD.4
２.在一个有向图中，所有顶点得入度之与等于所有顶点得出度之与得＿＿＿___倍。
A．l／2 　 　　 ﻩＢ。1
C．2ﻩD。4
3.一个具有n个顶点得无向图最多包含__＿___条边。
　A。n　　 　　　 　 　　 ﻩB。n+１
Ｃ．n—1　 　 　　 D.n（n-1）／2
４.一个具有n个顶点得无向完全图包含______条边。
Ａ.n(ｎ—l)　 Ｂ。ｎ（n+ｌ)
C。n（n－l）/2　 Ｄ。n（ｎ—l）/２
5．一个具有ｎ个顶点得有向完全图包含____＿_条边。
A。n（ｎ－１） 　　　 ﻩB。ｎ(n+l） 　 　
C．n(ｎ－l）／２　　　 　 D。n（n+l)／2
6.对于具有ｎ个顶点得图,若采用邻接矩阵表示,则该矩阵得大小为__＿__＿。A。n 　　 　 　 　 Ｂ.n×n 　
C。n－1　 　　 　　 ﻩＤ。(n-l) ×（n－l）
７．无向图得邻接矩阵就是一个_＿____。
A.对称矩阵 ﻩB.零矩阵 　 　
Ｃ。上三角矩阵 Ｄ.对角矩阵
8．对于一个具有n个顶点与ｅ条边得无（有）向图，若采用邻接表表示，则表头向量得大小为__＿＿__。
Ａ.n 　 　 ﻩB.e 　 　
Ｃ．2n 　 　 D．２e
9．对于一个具有ｎ个顶点与e条边得无（有）向图，若采用邻接表表示，则所有顶点邻接表中得结点总数为＿_＿___。
A.n　 　 　　 ﻩＢ.ｅ 　
C。2n 　 　 ﻩD.２e
10。在有向图得邻接表中,每个顶点邻接表链接着该顶点所有______邻接点.Ａ．入边 　　 　 　 ﻩＢ．出边
　C。入边与出边 　 　　 　 　　 ﻩＤ。不就是入边也不就是出边
11。在有向图得逆邻接表中，每个顶点邻接表链接着该顶点所有___＿__邻接点。
A.入边 　 　　 　 　 B．出边
Ｃ.入边与出边　 　 　 　 　 　 　 D．不就是人边也不就是出边
12。如果从无向图得任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定就是＿___＿＿。
A.完全图 　 　　　 　 B.连通图
C．有回路 D．一棵树
13。采用邻接表存储得图得深度优先遍历算法类似于二叉树得__＿___算法。
Ａ。先序遍历 　 　 　　 　　 　 B.中序遍历
Ｃ。后序遍历 　 　 　 　　 　　 　　 　ﻩD。按层遍历
14。采用邻接表存储得图得广度优先遍历算法类似于二叉树得＿__＿__算法。
A.先序遍历 　 　 　 　 　 　 　 　 ﻩＢ.中序遍历
C．后序遍历　 　 　　　 D。按层遍历
1５．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确得就是＿____＿。
A.G肯定不就是完全图 　 　 ﻩB.G一定不就是连通图
C．G中一定有回路 　　 　 　 ﻩD。G有二个连通分量
16.下列有关图遍历得说法不正确得就是___＿＿_。
Ａ.连通图得深度优先搜索就是一个递归过程
　 B。图得广度优先搜索中邻接点得寻找具有“先进先出”得特征
　C。非连通图不能用深度优先搜索法
D．图得遍历要求每一顶点仅被访问一次
17。下列说法中不正确得就是_＿_＿_＿。
A．无向图中得极大连通子图称为连通分量
Ｂ。连通图得广度优先搜索中一般要采用队列来暂存刚访问过得顶点
C.图得深度优先搜索中一般要采用栈来暂存刚访问过得顶点
D.有向图得遍历不可采用广度优先搜索方法
1８。一个有向图G得邻接表存储如下图７－1所示,现按深度优先搜索遍历，从顶点v1出发，所得到得顶点序列就是_＿＿_＿_.
Ａ．v１，v2,v３，v4，v5 　 　 　 　 ﻩB．v１,v２,ｖ3，v5,v４
C。ｖ1，v２，v4，ｖ5,ｖ3 　 　 　 　 ﻩD.v1,ｖ２，v５,ｖ3,ｖ4
2
3

4 ∧
3
5 ∧
5 ∧
4 ∧
v1

v2

v3

v4 ∧

v5

图7—1　一个有向图得邻接表
19.对图７—2所示得无向图，从顶点1开始进行深度优先遍历,可得到顶点访问序列_＿__＿＿。
A.１,2,4,３,５，７,６ 　 　 　 　　　　　　B．１,2，4，3，5,6，7
C。1,2，４，5，6，3，７ 　　 　 　 　D．1,２，３,4，5,7，6
1
6
5
4
3
2
7

图7－2 一个无向图
2０.对图7—２所示得无向图,从顶点1开始进行广度优先遍历，可得到顶点访问序列___＿_＿.
A.１，3,２，4,5，6,7　　 B。1,2，4，３，5,6，７
Ｃ。１，２，3,４，5，7，6 　 　 　 　　ﻩＤ.２,５，1，4,7，３，６
2１。一个无向连通图得生成树就是含有该连通图得全部顶点得___＿＿_。
A。极小连通子图 　 B.极小子图
C。极大连通子图　 　　 　 　 Ｄ。极大子图
22.设无向图　Ｇ＝(V， Ｅ） 与G’=　（V’, E'）,如果 G’为G得生成树,则下列说法中不正确得就是__＿＿_＿.
Ａ．Ｇ’为G得连通分量 　 　 B。G’为G得无环子图
C.G'为G得子图　 　 　 Ｄ．G’为G得极小连通子图且Ｖ’＝V
２3、任意一个无向连通图______最小生成树。
Ａ.只有一棵　　 　　 ﻩＢ．有一棵或多棵
Ｃ．一定有多棵 　 　 　 　 　ﻩD。可能不存在
２4．对于含有ｎ个顶点得带权连通图，它得最小生成树就是指图中任意一个＿____＿__。
A．由ｎ—1条权值最小得边构成得子图。　 　 　　　
Ｂ.由n－1条权值之与最小得边构成得子图。
Ｃ.由n—1条权值之与最小得边构成得连通子图.
Ｄ．由n个顶点构成得边得权值之与最小得生成树.
25。若一个有向图中得顶点不能排成一个拓扑序列，则可断定该有向图_______。
A。就是个有根有向图 　 　　　　 　Ｂ.就是个强连通图
C.含有多个入度为０得顶点 Ｄ.含有顶点数目大于1得强连通分量
26．判定一个有向图就是否存在回路除了可以利用拓扑排序方法外，还可以用＿___。
A．求关键路径得方法　 　 　 　ﻩB．求最短路径得Ｄijkｓｔrａ算法
C．广度优先遍历算法 　 　 　　 　 ﻩD.深度优先遍历算法
27。求最短路径得Diｊｋstｒa算法得时间复杂度为__＿＿＿＿。
A。O(n) 　　　 　 　 B．O（n+e）
C。O(n2) 　 　 　 　　 ﻩD．O（ne）
２８。求最短路径得Floyd算法得时间复杂度为＿____＿。
A．Ｏ（n） 　 　 　 　 　 Ｂ.O（ne)
C．Ｏ(ｎ2) 　 　 　　 　　　　　　　 D。O（n3)
29．关键路径就是事件结点网络中_____＿.
A.从源点到汇点得最长路径 ﻩB。从源点到汇点得最短路径
C。最长得回路 　 　 D．最短得回路
30.下面说法不正确得就是___＿__.
Ａ.在AＯE网中,减少任一关键活动得权值后,整个工期也就相应减少
B．AOE网工程工期为关键活动得权值与
C.在关键路径上得活动都就是关键活动，而关键活动也必须在关键路径上
D．A与B
31．下面说法不正确得就是_＿＿__＿.
A．关键活动不按期完成就会影响整个工程得完成时间
B.任何一个关键活动提前完成，将使整个工程提前完成
C。所有关键活动都提前完成，则整个工程提前完成
Ｄ.某些关键活动若提前完成,将使整个工程提前完成
二、填空题
1．对于具有n个顶点得无向图Ｇ最多有________＿条边。
2。对于具有n个顶点得强连通有向图G至少有_＿_＿_＿__＿条边。
3.对于具有ｎ个顶点得有向图，每个顶点得度最大可达____＿______.
4．若无向图G得顶点度数最小值大于___＿___＿_＿＿时,Ｇ至少有一条回路。
5．对于一个具有ｎ个顶点与e条边得无向图，若采用邻接表表示,则表头向量得大小为_______＿＿__，所有邻接表中得结点总数就是_＿_＿__＿___。
6。已知一个有向图得邻接矩阵表示，删除所有从第ｉ个结点出发得弧得方法就是__＿＿_____＿__。
7.对于n个顶点得无向图,采用邻接矩阵表示，求图中边数得方法就是__＿__＿_＿_＿,判断任意两个顶点i与j就是否有边相连得方法就是________＿_,求任意一个顶点得度得方法就是_＿_________。
８．对于ｎ个顶点得有向图，采用邻接矩阵表示，求图中边数得方法就是____＿_＿__，判断任意两个顶点i与j就是否有边相连得方法就是＿＿＿_______,求任意一个顶点得度得方法就是_＿_＿＿＿__＿＿.
9．无向图得连通分量就是指＿___＿＿_____.
10.已知图Ｇ得邻接表如图7－3所示，从顶点ｖ1出发得深度优先搜索序列为____＿＿＿_,从顶点1出发得广度优先搜索序列为______＿_____＿。
v1

v2

v3

v4 ∧

v5

v6 ∧
2
3

4 ∧
3
5 ∧
6 ∧
4
6
3 ∧

图7－3 图G得邻接表
１1.n个顶点连通图得生成树一定有＿＿____＿___条边。
1２。一个连通图得_＿＿_＿＿_____就是一个极小连通子图。
13.Prim算法适用于求________＿得网得最小生成树,Ｋruskａl算法适用于求___＿__＿_得网得最小生成树。
1４.在ＡOＶ图中,顶点表示＿＿_＿_＿__,有向边表示__＿＿_＿＿_。
1５.可以进行拓扑排序得有向图一定就是＿____＿＿＿_。
１6。从源点到汇点长度最长得路径称为关键路径,该路径上得活动称为_＿＿＿____。　
17.Dijkstra算法从源点到其它各顶点得路径长度按＿_＿_＿___次序依次产生,该算法在边上得权出现_＿_＿____＿情况时,不能正确产生最短路径。
18.求从某源点到其余各项点得Ｄijkstra算法在图得顶点数为１0，用邻接矩阵表示图时计算时间约为10ms,则在图得顶点数为4０时，计算时间约为_______＿_ms。
三、判断题
1.具有n个顶点得无向图至多有n(ｎ-1)条边。
2。有向图中各顶点得入度之与等于各顶点得出度之与.
3。邻接矩阵只储存了边得信息，没有存储顶点得信息。
4。对同一个有向图，只保存出边得邻接表中结点得数目总就是与只保存入边得邻接表中结点得数目一样多.
５．如果表示图得邻接矩阵就是对称矩阵，则该图一定就是无向图。
6。如果表示有向图得邻接矩阵就是对称矩阵,则该有向图一定就是有向完全图。
７．如果表示某个图得邻接矩阵不就是对称矩阵,则该图一定就是有向图。
8。连通分量就是无向图得极小连通子图.
9。强连通分量就是有向图得极大连通子图。
１０.对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每一个顶点，则该图一定就是完全图.
11。连通图得广度优先搜索中一般要采用队列来暂时刚访问过得顶点。
1２.图得深度优先搜索中一般要采用栈来暂时刚访问过得顶点。
１3。有向图得遍历不可采用广度优先搜索方法。
14。连通图得生成树包含了图中所有顶点。
15.设G为具有n个顶点得连通图，如果其中得某个子图有n个顶点，ｎ—1条边，则该子图一定就是G得生成树。
１６．最小生成树就是指边数最小得生成树。
17.从ｎ个顶点得连通图中选取n—1条权值最小得边,即可构成最小生成树。
1８。只要无向网中没有权值相同得边，其最小生成树就就是惟一得。
1９.只要无向网中有权值相同得边,其最小生成树就可能不就是惟一得。
20。有环图也能进行拓扑排序。
21.拓扑排序算法仅适用于有向无环图。
２２。任何有向无环图得结点都可以排成拓扑排序，而且拓扑序列不惟一。
23。关键路径就是由权值最大得边构成得.
24。在AＯE网中，减小任一关键活动上得权值后,整个工期也就相应减小。
25．在AＯE网中工程工期为关键活动上权值之与。
２6.在关键路径得活动都就是关键活动，而关键活动未必在关键路径上.
27。关键活动不按期完成就会影响整个工程得完成时间。
28。所有关键活动都提前完成，则整个工程将提前完成。
29．某些关键活动若提前完成，将可能使整个工程提前完成。
30．求单源最短路径得狄克斯特拉算法不适用于有回路得有向网。
四、简答题
1.图Ｇ就是一个非连通无向图,共有2８条边,则该图至少有多少个顶点?
2．用邻接矩阵表示图时,矩阵元素得个数与顶点个数就是否相关？与边得条数就是否有关?
3.对于稠密图与稀疏图，就存储而言,采用邻接矩阵与邻接表哪个更好些？
4.请回答下列关于图得一些问题：
（1）有n个顶点得有向强连通图最多有多少条边？最少有多少条边？
（２）表示一个有１00０个顶点,1０00条边得有向图得邻接矩阵有多少个矩阵元素？就是否为稀疏矩阵？
（３）对于一个有向图，不用拓扑排序,如何判断图就是否存在环?
5.对ｎ个顶点得无向图与有向图，采用邻接表表示时,如何判别下列有关问题？
（1）图中有多少条边？
(2)任意两个顶点ｉ与ｊ就是否有边相连？
(3）任意一个顶点得度就是多少？
6.给出如图7－4所示得无向图G得邻接矩阵与邻接表两种存储结构。并在给定得邻接表基础上，指出从顶点1出发得深度优先遍历与广度优先遍历序列。
1
2
5
4
3

图7—4 一个无向图
7.对于图7-５所示得有向图，试给出:
（１）邻接矩阵. 　 (２）邻接表　 　　　（3)强连通分量
(4）对照邻接表，给出从顶点1出发得深度优先遍历序列。
（5)对照邻接表，给出从顶点3出发得深度优先遍历序列。
1
4
3
2
5
6

图７－5 一个有向图
８．什么样得图其最小生成树就是惟一得？
９.已知带权连通图G（V，E)邻接表如图7－6所示,请画出该图,并分别以深度优先与广度优先遍历该图，写出遍历中结点得序列,并画出该图得一棵最小生成树，其中表结点得3个域各为：
顶点号
边上所带得权
指针
v1

v2

v3

v4

v5
4 4 ∧
4 18 ∧
5 22 ∧
5 10 ∧
1 16
1 12
2 12
1 18
2 22
3 16
3 2
2 2
3 4
4 10 ∧
1、
2、
3
４、
5
图7-6　连通图得邻接表
10.已知世界6大城市为：北京(B)纽约（N)巴黎(P）伦敦（L)东京（Ｔ）墨西哥城（M）试用由表１给出得交通网确定最小生成树，并说明所使用得方法及其时间复杂度。

B
N
P
L
T
M
Ｂ

1

Ｎ
1

P
８２
58

3
９7
9２
L
81
５５
３

95
8９
T
21
108
97
95

113
Ｍ
124
32
9２
8９
１13

11．对于图7—7所示得带权有向图,采用狄克斯特拉算法求从顶点１到其它顶点得最短路径,要求给出求解过程。
3
9
8
2
2
1
2
7
1
5
3
4
2
6
5
12
12
15
13
13
4
4
3
1
3
2
0
4

图７—7　一个有向图 　 　 　 　　　　 图7—8一个有向图 　 　 　 　
12．设图7-8中得顶点表示村庄,有向边代表交通路线，若要建立一家医院，试问建在哪个村庄能使个村庄总体交通代价最小。
13。表2所示给出了某工程各工序之间得优先关系与各工序所需得时间.
表2 某工程各工序关系表
工序代号 Ａ 　 B C Ｄ 　E F Ｇ H I 　　J Ｋ 　 L　　 Ｍ　 N
所需时间 15　 10 50 8 1５ 40 ３0０ 　15　　１２０ ６0 15　 　 ３0 20 40
先驱工作 — － A，B Ｂ　 Ｃ,D　 B 　 E　　G,I E　 I Ｆ,Ｉ H,J，K L 　 Ｇ
完成如下各小题：
(1）画出相应得AOＥ网
（2）列出事件得最早发生时间,最迟发生时间。
（3)找出关键路径并指明完成该工程所需得最短时间。
1４。如图7—９所示得AOＥ网，求:
（１）每项活动ａi最早开始时间ｅ（aｉ）与最迟开始时间ｌ（aｉ）.
（2）完成此工程最少需要多少天（设边上权值为天数）。
(3)哪些就是关键活动
a13=2
a1=5
a2=6
a3=3
a4=6
a5=3
a6=3
a7=4
a12=4
a11=2
a10=5
a9=4
a8=1
1
3
4
2
5
6
7
8
9
10
(4)就是否存在某项活动，当其提高速度后能使整个工程缩短工期?
图7－9
五、算法设计题
1.假设图Ｇ采用邻接表存储,分别设计实现以下要求得算法：
（1）求出图G中每个顶点得入度。
（2）求出图G中每个顶点得出度
（３）求出图G中出度最大得一个顶点,输出该顶点得编号.
（4)计算图Ｇ中出度为０得顶点数.
(5)判断图Ｇ中就是否存在边<ｉ，j>。
2．假设图G采用邻接矩阵存储,分别设计实现以下要求得算法：
（1)求出图G中每个顶点得入度。
（2）求出图G中每个顶点得出度
（3)求出图G中出度最大得一个顶点，输出该顶点得编号。
（４）计算图G中出度为0得顶点数。
（５）判断图G中就是否存在边<i,ｊ>。
３.设计一个将邻接表转换为邻接矩阵得算法.
4．一个连通图采用邻接表作为存储机构，设计一个算法实现从顶点ｖ出发得深度优先遍历得非递归过程。
5。设计一个算法,求不带权无向连通图Ｇ中距离顶点ｖ得最远顶点。
6．设计一个算法,判断无向图G就是否就是一棵树,若就是树，返回1；否则返回0。
７。假设图采用邻接表存储，分别写出基于DFＳ与BPS遍历得算法来判别顶点ｉ与顶点j(ｉ!=j)之间就是否有路径.
８。假设图G采用邻接表存储,设计一个算法,判断无向图G就是否连通，若连通则返回1；否则返回0。
9。假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v得长度为１得所有简单路径。
１0．假设图G采用邻接表存储,设计一个算法，输出图G中从顶点ｕ到v得所有简单路径。
11．假设图G采用邻接表存储,设计一个算法，从如图７-10所示得无向图Ｇ中找出满足如下条件得一条路径：
（1）给定起点ｖi与终点ｖj。
(2)给定一组必经点｛7,9｝,即输出得路径必须包含这些顶点。
(3）给定一组必避点｛1，6｝,即输出得路径不能包含这些顶点。
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

图7-１0
１2。假设图G采用邻接矩阵存储,采用遍历方法实际一个有向图得根得算法.若有向图中存在一个顶点ｖ，从v可以通过路径达达图中其它所有顶点，则称ｖ为该有向图得根.
13．假设图G采用邻接矩阵存储，设计一个算法判断在给定得有向图中就是否存在一个简单有向回路，若存在,则以顶点序列得方法输出该回路（找到一条即可）。
1４.采用堆排序来实现Ｋrusｋal算法,并说明时间复杂度O(elog2ｅ)得理由。
15。如图7—11就是一个城市连接图,图中权值表示两城市之间得里程(单位为１００ｋm),现要设计一条铁路贯通所有城市（即从一个任一城市可以到达其她城市）。设计一个算法,求出最小代价。假设每1km得铁路造价为1000万元.
6
3
6
4
2
5
5
6
5
1
1
0
3
4
5
2

图7-11 城市连通图
１６.利用狄克斯特拉算法，设计一个可产生从指定顶点出发得最小生成树得算法.
17。设计一个算法求图得中心点。设ｖ就是有向图G得一个顶点，把v得偏心度定义为：ＭAＸ｛从w到v得最短距离｜ｗV(G）｝如果v就是有向图Ｇ中具有最小偏心度得顶点,则称顶点ｖ就是G得中心点。
18．假设图Ｇ采用邻接矩阵存储，采用弗洛伊德算法设计一个求有向图得根得算法。若有向图中存在一个顶点v，从v可以通过路径到达图中其她所有顶点,则称v为该有向图得根.
19.设计一个算法，判断有向图就是否存在回路。
2０.对于一个使用邻接表存储得带权有向图Ｇ。试利用深度优先搜索方法,对该图中所有顶点进行逆向拓扑排序。若邻接表得数据类型定义为AＧｒａph，则算法得首部为:ｖｏid dfs_toｐsｏrt（AGｒａｐh　＊G) 若拓扑排序成功,表示图中不存在环;否则表示图中存在环。在这个算法中嵌套一个递归深度优先搜索算法为：Dfs（AGaph G ，　ｉnt　 v)在遍历图得同时进行逆序拓扑排序，其中,ｖ就是顶点编号。
(1)给出该图得邻接表定义
(2)定义在算法中使用得全局辅助数组
(3）写出逆向拓扑排序得算法.
２１.假设AOＥ网以邻接表方式存储,设计一个算法求该AOE网得所有关键活动.