第07章 图

第七章图一、选择题1．图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n24．要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n5．n个结点的完全有向图含有边的数目（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）6．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。A．0B．1C．n-1D．n7．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．49．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是()。A．逆拓扑有序B．拓扑有序C．无序的11．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网12．从邻接阵矩010101010A可以看出，该图共有（①）个顶点；如果是有向图该图共有（②）条弧；如果是无向图，则共有（③）条边。①．A．9B．3C．6D．1E．以上答案均不正确②．A．5B．4C．3D．2E．以上答案均不正确③．A．5B．4C．3D．2E．以上答案均不正确abedcf13．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。A．nijiA1],[B．n1jj,iAC．niijA1],[D．nijiA1],[+n1ji,jA14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查（）的第i行第j列的元素是否为零即可。A．mAB．AC．AmD．Am-115.下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程16．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b17.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（）aebdfcacfdebaedfcbaefdcbaefdbcA．5个B．4个C．3个D．2个第17题图第18题图18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(①)，而进行广度优先遍历得到的顶点序列是（②）。①．A．1354267B．1347652C．1534276D．1247653E．以上答案均不正确②．A．1534267B．1726453C．l354276D．1247653E．以上答案均不正确19．下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径20.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)22.(1).求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2).利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3).Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是（）。A．(1),(2),(3)B．(1)C．(1),(3)D．(2),(3)23．当各边上的权值()时，BFS算法可用来解决单源最短路径问题。A．均相等B．均互不相等C．不一定相等24.求解最短路径的Floyd算法的时间复杂度为()。A．O（n）B.O（n+c）C.O（n*n）D.O（n*n*n）25．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V727．一个有向无环图的拓扑排序序列（）是唯一的。A．一定B．不一定28.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧Vi，VjB．G中有一条从Vi到Vj的路径C．G中没有弧Vi,VjD．G中有一条从Vj到Vi的路径29.在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n＋e)C.O(n*n)D.O(n*n*n)30.关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路31.下面关于求关键路径的说法不正确的是（）。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上32．下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成三、填空题3．一个连通图的______是一个极小连通子图。7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。8.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。10．设G为具有N个顶点的无向连通图，则G中至少有______条边。12．如果含n个顶点的图形形成一个环，则它有______棵生成树。17．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。20.对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。【青岛大学2002三、8（2分）】21.遍历图的过程实质上是______，breath-firstsearch遍历图的时间复杂度(以邻接表为存储结构)______；depth-firstsearch遍历图的时间复杂度______，两者不同之处在于______，反映在数据结构上的差别是______。23.一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是______。24.为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。【南京理工大学1999二、9（2分）】25.按下图所示，画出它的广度优先生成树______和深度优先生成树______。28.Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。【厦门大学1999一、4】30．对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为______，利用Kruskal算法生成最小代价生成树其时间复杂度为______。31．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点V1，V2，．．．，Vn，用相邻矩阵A表示，边的权全是正数。请在下列划线处填上正确叙述。（1）．若（Vi，Vj）是边，则A（i，j）的值等于______，若（Vi，Vj）不是边，则A（i，j）的值是一个比任何边的权______，矩阵的对角线元素全为0。（2）．构造最小生成树过程中，若节点Vi已包括进生成树，就把相邻矩阵的对角线元素A（i，i）置成______，若（Vi，Vj）已包括进生成树，就把矩阵元素A（i，j）置成______。（3）．算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。【山东工业大学1998二、4(6分）】32.有一个用于n个顶点连通带权无向图的算法描述如下：（1）．设集合T1与T2，初始均为空；（2）．在连通图上任选一点加入T1；（3）．以下步骤重复n-1次：a.在i属于T1，j不属于T1的边中选最小权的边；b.该边加入T2。上述算法完成后，T2中共有______条边，该算法称______算法，T2中的边构成图的______。33.有向图G可拓扑排序的判别条件是______。34.Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次产生，该算法弧上的权出现______情况时，不能正确产生最短路径。35.求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。36．求最短路径的Dijkstra算法的时间复杂度为______。37.有向图G=(V,E),其中V(G)={0,1,2,3,4,5}，用a,b,d三元组表示弧a,b及弧上的权d.E(G)为{0,5,100,0,2,101,2,50,4,304,5,603,5,102,3,504,3,20}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。38.上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。39．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为______。40．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。41．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。42．在AOV网中，存在环意味着______，这是______的；对程序的数据流图来说，它表明存在______。43.当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。（1）．查邻接表中入度为______的顶点，并进栈；（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______；（3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。第7章图一.选择题1.A2.B3.A4.B5.D6.1B6.2D7.1B7.2C8.A9.A10.1C10.2BDE11.B12.1B12.2B12.3D13.B14.C15.C16.D17.D18.1C18.2C19.AB20.B21.1C21.2A21.3B21.4A22.A23.A24.D25.A26.A27.B28.D29.B30.A31.C32.B二.判断题1.√2.×3.×4.×5.×6.√7.×8.×9.×10.×11.√12.×13.√14.×15.×16.×17.√18.×19.×20.×21.×22.×23.×24.×25.×26.√27.×28.√29.×30.×31.√32.√33.×34.×35.×36.√37.×38.×39.×40.×41.√42.×43.×44.√45.×46.×47.×48.√49.×部分答案解释