资源描述：
《1设无向图顶点个数为n》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第7章图一、选择题1．设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n22．一个具有n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；3．要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n4．n个结点的完全有向图含有边的数目（ ）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）5．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。A．0B．1C．n-1D．n6．在一个无向图
2、中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．47．下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网8.下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．图的深度遍历不适用于有向图C．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程9．下面哪一方法可以判断出一个有向图是否有环（回路）：A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径10．已知有向
3、图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},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,V711．一个有向无环图的拓扑排序序列（）是唯一的。A．一定B．不一定12.在有向图G的拓扑序列中，若顶点Vi在
4、顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧B．G中有一条从Vi到Vj的路径C．G中没有弧D．G中有一条从Vj到Vi的路径13.关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路三、填空题1.判断一个无向图是一棵树的条件是______。2．有向图G的强连通分量是指______。4．具有10个顶点的无向图，边的总数最多为______。5．若用n表示图中顶点数目，则有_______条边的无向图成为完全图。6.设无向图G有n个顶点和e
5、条边，每个顶点Vi的度为di（1<=i<=n〉，则e=______7．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。8.在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。9．在有n个顶点的有向图中，每个顶点的度最大可达______。10．设G为具有N个顶点的无向连通图，则G中至少有______条边。11．n个顶点的连通无向图，其边的条数至少为______。12．在图G的邻接表表示中，每个顶点邻接表中所含的表结点数，对于无向图来说等于该顶点的______；对于有向图来说等
6、于该顶点的______。14．构造连通网最小生成树的两个典型算法是______和_________。15.有向图G=(V,E),其中V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d。E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。16.上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。17
7、．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为______。18．AOV网中,结点表示______,边表示______。AOE网中,结点表示______,边表示______。19．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为______。20.当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。（1）．查邻接表中入度为______的顶点，并进栈；（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是______；（3）．若栈空时，输出顶点数小于图
8、的顶点数，说明有______，否则拓扑排序完成。四、应用题367589421310578421691．首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。2．给出图G：（1）．画出G的邻接表表示图；（2）．根据你画出的邻接表，以顶点①为根，画出G的深度优先
