数据结构第7章-图习题

《数据结构第7章-图习题》由会员分享，可在线阅读，更多相关《数据结构第7章-图习题（12页珍藏版）》请在装配图网上搜索。

1、第7章 图一、单项选择题.在一个无向图G中，所有顶点得度数之与等于所有边数之与得_倍. A。l/2B1 C.2D.4.在一个有向图中，所有顶点得入度之与等于所有顶点得出度之与得_倍。Al2 。1 C2D。43.一个具有n个顶点得无向图最多包含_条边。A。n B。n+n1 D.n（n-1）2.一个具有n个顶点得无向完全图包含_条边。.n(l)。（n+) C。n（nl）/2 。n（l）/5一个具有个顶点得有向完全图包含_条边。A。n（） B。(n+l） Cn(l） D。n（n+l)26.对于具有个顶点得图,若采用邻接矩阵表示,则该矩阵得大小为_。A。n .nn C。n1 。(n-l) （nl）无向

2、图得邻接矩阵就是一个_。A.对称矩阵 B.零矩阵 。上三角矩阵 .对角矩阵8对于一个具有n个顶点与条边得无（有）向图，若采用邻接表表示，则表头向量得大小为_。.n B.e 2n De9对于一个具有个顶点与e条边得无（有）向图，若采用邻接表表示，则所有顶点邻接表中得结点总数为_。A.n . C。2n D.e10。在有向图得邻接表中,每个顶点邻接表链接着该顶点所有_邻接点.入边 出边 C。入边与出边 。不就是入边也不就是出边11。在有向图得逆邻接表中，每个顶点邻接表链接着该顶点所有_邻接点。A.入边 B出边.入边与出边 D不就是人边也不就是出边12。如果从无向图得任一顶点出发进行一次深度优先搜索即

3、可访问所有顶点,则该图一定就是_。A.完全图 B.连通图C有回路 D一棵树13。采用邻接表存储得图得深度优先遍历算法类似于二叉树得_算法。先序遍历 B.中序遍历。后序遍历 D。按层遍历14。采用邻接表存储得图得广度优先遍历算法类似于二叉树得_算法。A.先序遍历 .中序遍历C后序遍历 D。按层遍历1如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确得就是_。A.G肯定不就是完全图 B.G一定不就是连通图CG中一定有回路 D。G有二个连通分量16.下列有关图遍历得说法不正确得就是_。.连通图得深度优先搜索就是一个递归过程 B。图得广度优先搜索中邻接点得寻找具有“先进先出”得

4、特征 C。非连通图不能用深度优先搜索法 D图得遍历要求每一顶点仅被访问一次17。下列说法中不正确得就是_。A无向图中得极大连通子图称为连通分量 。连通图得广度优先搜索中一般要采用队列来暂存刚访问过得顶点 C.图得深度优先搜索中一般要采用栈来暂存刚访问过得顶点 D.有向图得遍历不可采用广度优先搜索方法1。一个有向图G得邻接表存储如下图1所示,现按深度优先搜索遍历，从顶点v1出发，所得到得顶点序列就是_.v，v2,v，v4，v5 Bv,v,3，v5,vC。1，v，v4，5,3 D.v1,，v,3,4 234 35 5 4 v1v2v3v4 v5图71一个有向图得邻接表19.对图2所示得无向图，从顶

5、点1开始进行深度优先遍历,可得到顶点访问序列_。A.,2,4,，, B,2，4，3，5,6，7C。1,2，5，6，3， D1,，,4，5,7，61654327图72 一个无向图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为

6、G得子图 G为G得极小连通子图且V3、任意一个无向连通图_最小生成树。.只有一棵 有一棵或多棵一定有多棵 D。可能不存在4对于含有个顶点得带权连通图，它得最小生成树就是指图中任意一个_。A由1条权值最小得边构成得子图。 .由n1条权值之与最小得边构成得子图。.由n1条权值之与最小得边构成得连通子图.由n个顶点构成得边得权值之与最小得生成树.25。若一个有向图中得顶点不能排成一个拓扑序列，则可断定该有向图_。A。就是个有根有向图 .就是个强连通图C.含有多个入度为得顶点 .含有顶点数目大于1得强连通分量26判定一个有向图就是否存在回路除了可以利用拓扑排序方法外，还可以用_。A求关键路径得方法 B

7、求最短路径得ijkr算法C广度优先遍历算法 D.深度优先遍历算法27。求最短路径得Dista算法得时间复杂度为_。A。O(n) BO（n+e）C。O(n2) DO（ne）。求最短路径得Floyd算法得时间复杂度为_。A（n） .O（ne)C(2) D。O（n3) 29关键路径就是事件结点网络中_.A.从源点到汇点得最长路径 B。从源点到汇点得最短路径C。最长得回路 D最短得回路30.下面说法不正确得就是_.在AE网中,减少任一关键活动得权值后,整个工期也就相应减少BAOE网工程工期为关键活动得权值与C.在关键路径上得活动都就是关键活动，而关键活动也必须在关键路径上DA与B31下面说法不正确得就

8、是_.A关键活动不按期完成就会影响整个工程得完成时间B.任何一个关键活动提前完成，将使整个工程提前完成C。所有关键活动都提前完成，则整个工程提前完成.某些关键活动若提前完成,将使整个工程提前完成二、填空题1对于具有n个顶点得无向图最多有_条边。2。对于具有n个顶点得强连通有向图G至少有_条边。3.对于具有个顶点得有向图，每个顶点得度最大可达_.4若无向图G得顶点度数最小值大于_时,至少有一条回路。5对于一个具有个顶点与e条边得无向图，若采用邻接表表示,则表头向量得大小为_，所有邻接表中得结点总数就是_。6。已知一个有向图得邻接矩阵表示，删除所有从第个结点出发得弧得方法就是_。7.对于n个顶点得

9、无向图,采用邻接矩阵表示，求图中边数得方法就是_,判断任意两个顶点i与j就是否有边相连得方法就是_,求任意一个顶点得度得方法就是_。对于个顶点得有向图，采用邻接矩阵表示，求图中边数得方法就是_，判断任意两个顶点i与j就是否有边相连得方法就是_,求任意一个顶点得度得方法就是_.9无向图得连通分量就是指_. 10.已知图得邻接表如图73所示，从顶点1出发得深度优先搜索序列为_,从顶点1出发得广度优先搜索序列为_。v1v2v3v4 v5v6 234 35 6 4 63 图73 图G得邻接表1.n个顶点连通图得生成树一定有_条边。1。一个连通图得_就是一个极小连通子图。 13.Prim算法适用于求_得

10、网得最小生成树,ruskl算法适用于求_得网得最小生成树。 1.在O图中,顶点表示_,有向边表示_。1.可以进行拓扑排序得有向图一定就是_。6。从源点到汇点长度最长得路径称为关键路径,该路径上得活动称为_。17.Dijkstra算法从源点到其它各顶点得路径长度按_次序依次产生,该算法在边上得权出现_情况时,不能正确产生最短路径。18.求从某源点到其余各项点得ijkstra算法在图得顶点数为0，用邻接矩阵表示图时计算时间约为10ms,则在图得顶点数为4时，计算时间约为_ms。三、判断题1.具有n个顶点得无向图至多有n(-1)条边。2。有向图中各顶点得入度之与等于各顶点得出度之与.3。邻接矩阵只储

11、存了边得信息，没有存储顶点得信息。4。对同一个有向图，只保存出边得邻接表中结点得数目总就是与只保存入边得邻接表中结点得数目一样多.如果表示图得邻接矩阵就是对称矩阵，则该图一定就是无向图。6。如果表示有向图得邻接矩阵就是对称矩阵,则该有向图一定就是有向完全图。如果表示某个图得邻接矩阵不就是对称矩阵,则该图一定就是有向图。8。连通分量就是无向图得极小连通子图.9。强连通分量就是有向图得极大连通子图。.对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每一个顶点，则该图一定就是完全图.11。连通图得广度优先搜索中一般要采用队列来暂时刚访问过得顶点。1.图得深度优先搜索中一般要采用栈

12、来暂时刚访问过得顶点。3。有向图得遍历不可采用广度优先搜索方法。14。连通图得生成树包含了图中所有顶点。15.设G为具有n个顶点得连通图，如果其中得某个子图有n个顶点，1条边，则该子图一定就是G得生成树。最小生成树就是指边数最小得生成树。17.从个顶点得连通图中选取n1条权值最小得边,即可构成最小生成树。1。只要无向网中没有权值相同得边，其最小生成树就就是惟一得。1.只要无向网中有权值相同得边,其最小生成树就可能不就是惟一得。20。有环图也能进行拓扑排序。21.拓扑排序算法仅适用于有向无环图。任何有向无环图得结点都可以排成拓扑排序，而且拓扑序列不惟一。23。关键路径就是由权值最大得边构成得.2

13、4。在AE网中，减小任一关键活动上得权值后,整个工期也就相应减小。25在AE网中工程工期为关键活动上权值之与。6.在关键路径得活动都就是关键活动，而关键活动未必在关键路径上.27。关键活动不按期完成就会影响整个工程得完成时间。28。所有关键活动都提前完成，则整个工程将提前完成。29某些关键活动若提前完成，将可能使整个工程提前完成。30求单源最短路径得狄克斯特拉算法不适用于有回路得有向网。四、简答题1.图就是一个非连通无向图,共有2条边,则该图至少有多少个顶点?2用邻接矩阵表示图时,矩阵元素得个数与顶点个数就是否相关？与边得条数就是否有关?3.对于稠密图与稀疏图，就存储而言,采用邻接矩阵与邻接表

14、哪个更好些？4.请回答下列关于图得一些问题：（1）有n个顶点得有向强连通图最多有多少条边？最少有多少条边？（）表示一个有00个顶点,100条边得有向图得邻接矩阵有多少个矩阵元素？就是否为稀疏矩阵？（）对于一个有向图，不用拓扑排序,如何判断图就是否存在环?5.对个顶点得无向图与有向图，采用邻接表表示时,如何判别下列有关问题？（1）图中有多少条边？(2)任意两个顶点与就是否有边相连？(3）任意一个顶点得度就是多少？6.给出如图74所示得无向图G得邻接矩阵与邻接表两种存储结构。并在给定得邻接表基础上，指出从顶点1出发得深度优先遍历与广度优先遍历序列。12543图74 一个无向图7.对于图7-所示得有

15、向图，试给出:（）邻接矩阵. (）邻接表 （3)强连通分量(4）对照邻接表，给出从顶点1出发得深度优先遍历序列。（5)对照邻接表，给出从顶点3出发得深度优先遍历序列。143256图5 一个有向图什么样得图其最小生成树就是惟一得？.已知带权连通图G（V，E)邻接表如图76所示,请画出该图,并分别以深度优先与广度优先遍历该图，写出遍历中结点得序列,并画出该图得一棵最小生成树，其中表结点得3个域各为：顶点号边上所带得权指针v1v2v3v4v54 4 4 18 5 22 5 10 1 161 122 12 1 182 223 163 22 23 44 10 1、2、3、5图7-6连通图得邻接表10.已

16、知世界6大城市为：北京(B)纽约（N)巴黎(P）伦敦（L)东京（）墨西哥城（M）试用由表给出得交通网确定最小生成树，并说明所使用得方法及其时间复杂度。BNPLTM 11P58379L81958T21108979511312432981311对于图77所示得带权有向图,采用狄克斯特拉算法求从顶点到其它顶点得最短路径,要求给出求解过程。39822 127153426512 12 15131344313204图7一个有向图 图78一个有向图 12设图7-8中得顶点表示村庄,有向边代表交通路线，若要建立一家医院，试问建在哪个村庄能使个村庄总体交通代价最小。13。表2所示给出了某工程各工序之间得优先关系

17、与各工序所需得时间.表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 EG,I E I , H,J，K L 完成如下各小题：(1）画出相应得AO网（2）列出事件得最早发生时间,最迟发生时间。（3)找出关键路径并指明完成该工程所需得最短时间。1。如图7所示得AO网，求:（）每项活动i最早开始时间（a）与最迟开始时间（a）.（2）完成此工程最少需要多少天（设边上权值为天数）。(3)哪些就是关键活动a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11

18、=2a10=5a9=4a8=113425678910(4)就是否存在某项活动，当其提高速度后能使整个工程缩短工期?图79五、算法设计题1.假设图采用邻接表存储,分别设计实现以下要求得算法：（1）求出图G中每个顶点得入度。（2）求出图G中每个顶点得出度（）求出图G中出度最大得一个顶点,输出该顶点得编号.（4)计算图中出度为得顶点数.(5)判断图中就是否存在边。2假设图G采用邻接矩阵存储,分别设计实现以下要求得算法：（1)求出图G中每个顶点得入度。（2）求出图G中每个顶点得出度（3)求出图G中出度最大得一个顶点，输出该顶点得编号。（）计算图G中出度为0得顶点数。（）判断图G中就是否存在边。.设计一

19、个将邻接表转换为邻接矩阵得算法.4一个连通图采用邻接表作为存储机构，设计一个算法实现从顶点出发得深度优先遍历得非递归过程。5。设计一个算法,求不带权无向连通图中距离顶点得最远顶点。6设计一个算法,判断无向图G就是否就是一棵树,若就是树，返回1；否则返回0。假设图采用邻接表存储，分别写出基于DF与BPS遍历得算法来判别顶点与顶点j(!=j)之间就是否有路径.。假设图G采用邻接表存储,设计一个算法,判断无向图G就是否连通，若连通则返回1；否则返回0。9。假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v得长度为得所有简单路径。0假设图G采用邻接表存储,设计一个算法，输出图G中从顶点到v得

20、所有简单路径。11假设图G采用邻接表存储,设计一个算法，从如图-10所示得无向图中找出满足如下条件得一条路径：（1）给定起点i与终点j。(2)给定一组必经点7,9,即输出得路径必须包含这些顶点。(3）给定一组必避点1，6,即输出得路径不能包含这些顶点。01234567891011121314图7-02。假设图G采用邻接矩阵存储,采用遍历方法实际一个有向图得根得算法.若有向图中存在一个顶点，从v可以通过路径达达图中其它所有顶点，则称为该有向图得根.13假设图G采用邻接矩阵存储，设计一个算法判断在给定得有向图中就是否存在一个简单有向回路，若存在,则以顶点序列得方法输出该回路（找到一条即可）。1.采

21、用堆排序来实现rusal算法,并说明时间复杂度O(elog2)得理由。15。如图711就是一个城市连接图,图中权值表示两城市之间得里程(单位为m),现要设计一条铁路贯通所有城市（即从一个任一城市可以到达其她城市）。设计一个算法,求出最小代价。假设每1km得铁路造价为1000万元.6364255651103452图7-11 城市连通图.利用狄克斯特拉算法，设计一个可产生从指定顶点出发得最小生成树得算法.17。设计一个算法求图得中心点。设就是有向图G得一个顶点，把v得偏心度定义为：A从w到v得最短距离V(G）如果v就是有向图中具有最小偏心度得顶点,则称顶点就是G得中心点。18假设图采用邻接矩阵存储

22、，采用弗洛伊德算法设计一个求有向图得根得算法。若有向图中存在一个顶点v，从v可以通过路径到达图中其她所有顶点,则称v为该有向图得根.19.设计一个算法，判断有向图就是否存在回路。2.对于一个使用邻接表存储得带权有向图。试利用深度优先搜索方法,对该图中所有顶点进行逆向拓扑排序。若邻接表得数据类型定义为Aph，则算法得首部为:id dfs_tosrt（AGhG) 若拓扑排序成功,表示图中不存在环;否则表示图中存在环。在这个算法中嵌套一个递归深度优先搜索算法为：Dfs（AGaph G ，nt v)在遍历图得同时进行逆序拓扑排序，其中,就是顶点编号。(1)给出该图得邻接表定义(2)定义在算法中使用得全局辅助数组(3）写出逆向拓扑排序得算法.假设AO网以邻接表方式存储,设计一个算法求该AOE网得所有关键活动.