数据结构第7章-图习题

第7章图一、单项选择题１.在一个无向图G中，所有顶点得度数之与等于所有边数之与得______倍.A。l/2 B．1C.2ﻩD.4２.在一个有向图中，所有顶点得入度之与等于所有顶点得出度之与得＿＿＿___倍。A．l／2ﻩＢ。1C．2ﻩD。43.一个具有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)／26.对于具有ｎ个顶点得图,若采用邻接矩阵表示,则该矩阵得大小为__＿__＿。A。n Ｂ.n×nC。n－1ﻩＤ。(n-l)×（n－l）７．无向图得邻接矩阵就是一个_＿____。A.对称矩阵ﻩB.零矩阵Ｃ。上三角矩阵 Ｄ.对角矩阵8．对于一个具有n个顶点与ｅ条边得无（有）向图，若采用邻接表表示，则表头向量得大小为__＿＿__。Ａ.nﻩB.eＣ．2n D．２e9．对于一个具有ｎ个顶点与e条边得无（有）向图，若采用邻接表表示，则所有顶点邻接表中得结点总数为＿_＿___。A.nﻩＢ.ｅC。2nﻩD.２e10。在有向图得邻接表中,每个顶点邻接表链接着该顶点所有______邻接点.Ａ．入边ﻩＢ．出边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,ｖ42234∧35∧5∧4∧v1v2v3v4∧v5图7—1一个有向图得邻接表19.对图７—2所示得无向图，从顶点1开始进行深度优先遍历,可得到顶点访问序列_＿__＿＿。A.１,2,4,３,５，７,６B．１,2，4，3，5,6，7C。1,2，４，5，6，3，７D．1,２，３,4，5,7，6161654327图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与B31．下面说法不正确得就是_＿＿__＿.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出发得广度优先搜索序列为______＿_____＿。vv1v2v3v4∧v5v6∧234∧35∧6∧463∧图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出发得深度优先遍历与广度优先遍历序列。112543图7—4一个无向图7.对于图7-５所示得有向图，试给出:（１）邻接矩阵.(２）邻接表（3)强连通分量(4）对照邻接表，给出从顶点1出发得深度优先遍历序列。（5)对照邻接表，给出从顶点3出发得深度优先遍历序列。1143256图７－5一个有向图８．什么样得图其最小生成树就是惟一得？９.已知带权连通图G（V，E)邻接表如图7－6所示,请画出该图,并分别以深度优先与广度优先遍历该图，写出遍历中结点得序列,并画出该图得一棵最小生成树，其中表结点得3个域各为：顶点号边上所带得权指针v1v1v2v3v4v544∧418∧522∧510∧116112212118222316322234410∧2、3４、5图7-6连通图得邻接表10.已知世界6大城市为：北京(B)纽约（N)巴黎(P）伦敦（L)东京（Ｔ）墨西哥城（M）试用由表１给出得交通网确定最小生成树，并说明所使用得方法及其时间复杂度。BNPLTMＢ1Ｎ1P８２583９79２L81５５３958９T211089795113Ｍ124329２8９１1311．对于图7—7所示得带权有向图,采用狄克斯特拉算法求从顶点１到其它顶点得最短路径,要求给出求解过程。39398221271534265121215131344313204图７—7一个有向图图7—8一个有向图12．设图7-8中得顶点表示村庄,有向边代表交通路线，若要建立一家医院，试问建在哪个村庄能使个村庄总体交通代价最小。13。表2所示给出了某工程各工序之间得优先关系与各工序所需得时间.表2某工程各工序关系表工序代号ＡBCＤEFＧHIJＫLＭN所需时间15105081５40３0０15１２０６015３02040先驱工作—－A，BＢＣ,DBEG,IEIＦ,ＩH,J，KLＧ完成如下各小题：(1）画出相应得AOＥ网（2）列出事件得最早发生时间,最迟发生时间。（3)找出关键路径并指明完成该工程所需得最短时间。1４。如图7—９所示得AOＥ网，求:（１）每项活动ａi最早开始时间ｅ（aｉ）与最迟开始时间ｌ（aｉ）.（2）完成此工程最少需要多少天（设边上权值为天数）。(3)哪些就是关键活动a13=2a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910图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｝,即输出得路径不能包含这些顶点。001234567891011121314图7-１0１2。假设图