数据结构第7章-图习题

第7章 图一、单选题1.在一种无向图G中，所有顶点的度数之和等于所有边数之和的_倍。 A./21 C.2D2在一种有向图中,所有顶点的入度之和等于所有顶点的出度之和的_倍。A/2 B1 CD.3.一种具有n个顶点的无向图最多涉及_条边。An B.n1Cn- D(n-1)24.一种具有n个顶点的无向完全图涉及_条边。An(l) Bn(n+l) C.（nl）/2 Dn(-l)/5.一种具有n个顶点的有向完全图涉及_条边。.n（n-1) Bn（n+l) C（n-l）/2 Dn（n+l)26.对于具有n个顶点的图,若采用邻接矩阵表达，则该矩阵的大小为_。A. B.nn Cn-1 D(n-l） (n-l)7.无向图的邻接矩阵是一种_。A.对称矩阵 B零矩阵 .上三角矩阵 .对角矩阵8.对于一种具有个顶点和e条边的无(有)向图,若采用邻接表表达，则表头向量的大小为_。A B. C.2n D.29.对于一种具有n个顶点和e条边的无(有)向图，若采用邻接表表达，则所有顶点邻接表中的结点总数为_。A.n B C.2 20.在有向图的邻接表中,每个顶点邻接表链接着该顶点所有_邻接点。A.入边 B.出边 入边和出边 D不是入边也不是出边11.在有向图的逆邻接表中,每个顶点邻接表链接着该顶点所有_邻接点。.入边 B出边C入边和出边 D.不是人边也不是出边如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_。A完全图 B.连通图C.有回路D一棵树13.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_算法。A.先序遍历 .中序遍历C.后序遍历 D.按层遍历14采用邻接表存储的图的广度优先遍历算法类似于二叉树的_算法。A.先序遍历 B中序遍历C.后序遍历 按层遍历15.如果无向图G必须进行二次广度优先搜索才干访问其所有顶点,则下列说法中不对的的是_。A.G肯定不是完全图 B一定不是连通图C.G中一定有回路 .G有二个连通分量1下列有关图遍历的说法不对的的是_。A.连通图的深度优先搜索是一种递归过程 B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特性 C非连通图不能用深度优先搜索法 D.图的遍历规定每一顶点仅被访问一次7.下列说法中不对的的是_。A.无向图中的极大连通子图称为连通分量 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D有向图的遍历不可采用广度优先搜索措施18一种有向图G的邻接表存储如下图所示，现按深度优先搜索遍历，从顶点v1出发,所得到的顶点序列是_。A.v1,v,v4，v5 Bv,v2,v3,v5,4Cv，,v,v5,v v1,v，v5，v4234 35 5 4 v1v2v3v4 v5图7- 一种有向图的邻接表19对图7-所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问序列_。1，,5，7， 1,4，5，6，7C.1,，4，5，6，7 D1，2,3,4，7,61654327图72 一种无向图20.对图7-所示的无向图，从顶点1开始进行广度优先遍历,可得到顶点访问序列_。A.1,3，2,4，5，6， B.1,2,4，3，5,6，7C.,3,4，5,， D，1，4,7,3，2一种无向连通图的生成树是具有该连通图的所有顶点的_。A极小连通子图 B.极小子图C极大连通子图 D.极大子图2设无向图 =(V, E)和G=(, E）,如果G为G的生成树，则下列说法中不对的的是_。A为G的连通分量 .G为G的无环子图C.为的子图 D.G为G的极小连通子图且V=2任意一种无向连通图_最小生成树。.只有一棵 B有一棵或多棵C一定有多棵 也许不存在2.对于具有n个顶点的带权连通图,它的最小生成树是指图中任意一种_。A.由n-条权值最小的边构成的子图。 由n1条权值之和最小的边构成的子图。C由1条权值之和最小的边构成的连通子图。D由n个顶点构成的边的权值之和最小的生成树。25.若一种有向图中的顶点不能排成一种拓扑序列,则可断定该有向图_。A是个有根有向图 B.是个强连通图C具有多种入度为0的顶点 D.具有顶点数目不小于1的强连通分量.鉴定一种有向图与否存在回路除了可以运用拓扑排序措施外,还可以用_。A.求核心途径的措施 求最短途径的Djkstra算法.广度优先遍历算法 .深度优先遍历算法27.求最短途径的Dikstr算法的时间复杂度为_。A.O(n) B.O（n+)CO(n2） .O（ne)8.求最短途径的Foy算法的时间复杂度为_。AO(n) BO(e)O（n2） D.O()2.核心途径是事件结点网络中_。A.从源点到汇点的最长途径 从源点到汇点的最短途径C最长的回路 D最短的回路下面说法不对的的是_。A在AO网中，减少任一核心活动的权值后,整个工期也就相应减少B.AOE网工程工期为核心活动的权值和C.在核心途径上的活动都是核心活动,而核心活动也必须在核心途径上D.A和B31下面说法不对的的是_。A.核心活动不按期完毕就会影响整个工程的完毕时间B.任何一种核心活动提前完毕,将使整个工程提前完毕.所有核心活动都提前完毕，则整个工程提前完毕某些核心活动若提前完毕,将使整个工程提前完毕二、填空题1对于具有个顶点的无向图G最多有_条边。2对于具有n个顶点的强连通有向图至少有_条边。3对于具有n个顶点的有向图，每个顶点的度最大可达_。若无向图G的顶点度数最小值不小于_时,至少有一条回路。5.对于一种具有个顶点和条边的无向图,若采用邻接表表达,则表头向量的大小为_，所有邻接表中的结点总数是_。6.已知一种有向图的邻接矩阵表达,删除所有从第i个结点出发的弧的措施是_。7对于n个顶点的无向图，采用邻接矩阵表达,求图中边数的措施是_，判断任意两个顶点i和与否有边相连的措施是_,求任意一种顶点的度的措施是_。对于个顶点的有向图，采用邻接矩阵表达,求图中边数的措施是_，判断任意两个顶点i和j与否有边相连的措施是_,求任意一种顶点的度的措施是_。无向图的连通分量是指_。10已知图G的邻接表如图7-所示,从顶点v1出发的深度优先搜索序列为_,从顶点1出发的广度优先搜索序列为_。v1v2v3v4 v5v6 234 35 6 4 63 图7-3 图G的邻接表11.n个顶点连通图的生成树一定有_条边。12.一种连通图的_是一种极小连通子图。 Pri算法合用于求_的网的最小生成树,Krskl算法合用于求_的网的最小生成树。 1在AOV图中,顶点表达_,有向边表达_。15可以进行拓扑排序的有向图一定是_。6从源点到汇点长度最长的途径称为核心途径,该途径上的活动称为_。 7.Dijktra算法从源点到其他各顶点的途径长度按_顺序依次产生，该算法在边上的权浮现_状况时，不能对的产生最短途径。18.求从某源点到其他各项点的Diksra算法在图的顶点数为10,用邻接矩阵表达图时计算时间约为10s,则在图的顶点数为40时,计算时间约为_m。三、判断题1具有n个顶点的无向图至多有n(n-1）条边。2有向图中各顶点的入度之和等于各顶点的出度之和。3.邻接矩阵只储存了边的信息，没有存储顶点的信息。4对同一种有向图,只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目同样多。5如果表达图的邻接矩阵是对称矩阵，则该图一定是无向图。如果表达有向图的邻接矩阵是对称矩阵,则该有向图一定是有向完全图。如果表达某个图的邻接矩阵不是对称矩阵，则该图一定是有向图。连通分量是无向图的极小连通子图。9.强连通分量是有向图的极大连通子图。10.对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每一种顶点,则该图一定是完全图。11连通图的广度优先搜索中一般要采用队列来临时刚访问过的顶点。1.图的深度优先搜索中一般要采用栈来临时刚访问过的顶点。13有向图的遍历不可采用广度优先搜索措施。14.连通图的生成树涉及了图中所有顶点。15.设G为具有n个顶点的连通图,如果其中的某个子图有n个顶点,n-条边，则该子图一定是G的生成树。1.最小生成树是指边数最小的生成树。17从n个顶点的连通图中选用-1条权值最小的边,即可构成最小生成树。18只要无向网中没有权值相似的边，其最小生成树就是惟一的。9.只要无向网中有权值相似的边,其最小生成树就也许不是惟一的。0.有环图也能进行拓扑排序。21.拓扑排序算法仅合用于有向无环图。22任何有向无环图的结点都可以排成拓扑排序,并且拓扑序列不惟一。23核心途径是由权值最大的边构成的。24在A网中,减小任一核心活动上的权值后，整个工期也就相应减小。25.在OE网中工程工期为核心活动上权值之和。26.在核心途径的活动都是核心活动,而核心活动未必在核心途径上。2核心活动不按期完毕就会影响整个工程的完毕时间。28所有核心活动都提前完毕,则整个工程将提前完毕。29某些核心活动若提前完毕，将也许使整个工程提前完毕。30.求单源最短途径的狄克斯特拉算法不合用于有回路的有向网。四、简答题1.图是一种非连通无向图，共有8条边，则该图至少有多少个顶点?.用邻接矩阵表达图时，矩阵元素的个数与顶点个数与否有关？与边的条数与否有关？对于稠密图和稀疏图，就存储而言,采用邻接矩阵和邻接表哪个更好些？.请回答下列有关图的某些问题：（）有n个顶点的有向强连通图最多有多少条边?至少有多少条边？（2）表达一种有00个顶点,10条边的有向图的邻接矩阵有多少个矩阵元素？与否为稀疏矩阵?()对于一种有向图，不用拓扑排序，如何判断图与否存在环?5对n个顶点的无向图和有向图,采用邻接表表达时，如何鉴别下列有关问题？(）图中有多少条边?(2)任意两个顶点i和j与否有边相连？(3)任意一种顶点的度是多少？6给出如图4所示的无向图G的邻接矩阵和邻接表两种存储构造。并在给定的邻接表基本上,指出从顶点1出发的深度优先遍历和广度优先遍历序列。12543图74一种无向图7.对于图-所示的有向图，试给出：(）邻接矩阵。 （2）邻接表 （）强连通分量(）对照邻接表,给出从顶点1出发的深度优先遍历序列。(5）对照邻接表，给出从顶点3出发的深度优先遍历序列。143256图-5 一种有向图8.什么样的图其最小生成树是惟一的?9.已知带权连通图G(V,E)邻接表如图7-6所示，请画出该图，并分别以深度优先和广度优先遍历该图,写出遍历中结点的序列，并画出该图的一棵最小生成树，其中表结点的3个域各为：顶点号边上所带的权指针v1v2v3v4v54 4 4 18 5 22 5 10 1 161 122 12 1 182 223 163 22 23 44 10 1.234.图7-6连通图的邻接表10.已知世界6大都市为：北京()纽约(N）巴黎（P)伦敦(L）东京（T）墨西哥城（M）试用由表1给出的交通网拟定最小生成树,并阐明所使用的措施及其时间复杂度。BPLTMB 108281141095810832P825839792L8153589T211897911M124329891131对于图-7所示的带权有向图,采用狄克斯特拉算法求从顶点1到其他顶点的最短途径，规定给出求解过程。39822 127153426512 12 15131344313204图7-一种有向图 图7-8一种有向图 1设图78中的顶点表达村庄，有向边代表交通路线,若要建立一家医院,试问建在哪个村庄能使个村庄总体交通代价最小。3表2所示给出了某工程各工序之间的优先关系和各工序所需的时间。表2 某工程各工序关系表工序代号 B C D E F H I J K M 所需时间 15 1 5 815 40 30 120 60 5 30 2 0先驱工作 - - A,B B , E G,I E I F,I H,J, L 完毕如下各小题:（1)画出相应的AOE网(2)列出事件的最早发生时间,最迟发生时间。（3）找出核心途径并指明完毕该工程所需的最短时间。14.如图7-9所示的OE网,求：（）每项活动ai最早开始时间(ai）和最迟开始时间(ai)。(2）完毕此工程至少需要多少天（设边上权值为天数）。（3)哪些是核心活动a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910（)与否存在某项活动，当其提高速度后能使整个工程缩短工期?图-9五、算法设计题1.假设图G采用邻接表存储，分别设计实现如下规定的算法:（)求出图G中每个顶点的入度。（2)求出图G中每个顶点的出度(3)求出图G中出度最大的一种顶点,输出该顶点的编号。（4）计算图G中出度为0的顶点数。（）判断图G中与否存在边。假设图采用邻接矩阵存储,分别设计实现如下规定的算法:(1)求出图G中每个顶点的入度。（)求出图G中每个顶点的出度（）求出图G中出度最大的一种顶点，输出该顶点的编号。()计算图G中出度为0的顶点数。（)判断图G中与否存在边。3.设计一种将邻接表转换为邻接矩阵的算法。4.一种连通图采用邻接表作为存储机构,设计一种算法实现从顶点v出发的深度优先遍历的非递归过程。5.设计一种算法,求不带权无向连通图中距离顶点的最远顶点。6设计一种算法，判断无向图G与否是一棵树，若是树,返回1;否则返回。7假设图采用邻接表存储，分别写出基于DFS和BS遍历的算法来鉴别顶点i和顶点j（i!=j)之间与否有途径。.假设图G采用邻接表存储，设计一种算法,判断无向图与否连通,若连通则返回；否则返回0。9.假设图G采用邻接表存储,设计一种算法，输出图中从顶点到v的长度为1的所有简朴途径。1.假设图采用邻接表存储，设计一种算法,输出图G中从顶点u到的所有简朴途径。11假设图采用邻接表存储，设计一种算法,从如图70所示的无向图G中找出满足如下条件的一条途径：（1)给定起点vi和终点vj。（2）给定一组必经点7,9，即输出的途径必须涉及这些顶点。(3）给定一组必避点1,6,即输出的途径不能涉及这些顶点。01234567891011121314图7-101.假设图采用邻接矩阵存储，采用遍历措施实际一种有向图的根的算法。若有向图中存在一种顶点，从v可以通过途径达达图中其他所有顶点，则称v为该有向图的根。1.假设图G采用邻接矩阵存储，设计一种算法判断在给定的有向图中与否存在一种简朴有向回路,若存在，则以顶点序列的措施输出该回路（找到一条即可）。14.采用堆排序来实现Kruskal算法,并阐明时间复杂度O(lge)的理由。5如图7-11是一种都市连接图,图中权值表达两都市之间的里程（单位为10k）,现要设计一条铁路贯穿所有都市（即从一种任一都市可以达到其她都市)。设计一种算法,求出最小代价。假设每1m的铁路造价为00万元。6364255651103452图-11 都市连通图16运用狄克斯特拉算法,设计一种可产生从指定顶点出发的最小生成树的算法。7设计一种算法求图的中心点。设v是有向图G的一种顶点，把v的偏心度定义为：MX从到的最短距离|wV(G)如果是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。18.假设图G采用邻接矩阵存储，采用弗洛伊德算法设计一种求有向图的根的算法。若有向图中存在一种顶点，从v可以通过途径达到图中其她所有顶点,则称为该有向图的根。19设计一种算法,判断有向图与否存在回路。20.对于一种使用邻接表存储的带权有向图。试运用深度优先搜索措施,对该图中所有顶点进行逆向拓扑排序。若邻接表的数据类型定义为Arp，则算法的首部为:void f_tport(Graph*G) 若拓扑排序成功,表达图中不存在环;否则表达图中存在环。在这个算法中嵌套一种递归深度优先搜索算法为：Dfs(AGah G, nt )在遍历图的同步进行逆序拓扑排序,其中,是顶点编号。(1)给出该图的邻接表定义（2)定义在算法中使用的全局辅助数组（3）写出逆向拓扑排序的算法。假设AOE网以邻接表方式存储，设计一种算法求该AOE网的所有核心活动。