搜索
《图》练习题一、单项选择题1、在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为()。A.sB.s-1C.s+1D.2s2、在一个具有n个顶点的无向完全图中，所含的边数为()。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/23、在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为()。A.kB.k+1C.k+2D.2k4、对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为()。A.0B.1C.nD.n+15、若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用()次深度优先搜索遍历的算法。A.kB.1C.k-1D.k+16、若要把n个顶点连接为一个连通图，则至少需要()条边。A.nB.n+1C.n-1D.2n7、在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为()。A.nB.neC.eD.2e8、在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为()。A.nB.neC.eD.2e9、在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()。A.出边数B.入边数C.度数D.度数减110、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为()。A.A,B,C,F,D,EB.A,C,F,D,E,BC.A,B,D,C,F,ED.A,B,D,F,E,C11、若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为()。A.A,B,C,D,E,FB.A,B,C,F,D,EC.A,B,D,C,E,FD.A,C,B,F,D,E12、若如下图所示的无向连通图，则从顶点A开始对该图进行广度优先遍历，得到的顶点序列可能为()。ABDCEFGA.A,B,C,D,E,F,GB.A,B,C,D,E,G,FC.A,B,F,C,D,E,GD.A,B,F,C,D,G,E二、填空题1.在一个无向图中，所有顶点的度数之和等于所有边数的_2倍。2.在一个具有n个顶点的无向完全图中，包含有_n*（n-1）/2条边，在一个具有n个顶点的有向完全图中，包含有_n*（n-1）条边。3.假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{a,c,a,e,c,f,d,c,e,b,e,d}，则出度为0的顶点个数为_2，入度为1的顶点个数为_4。4.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要_n-1条边。5.图的_深度优先搜索遍历算法可以使用栈结果实现或用递归算法，图的_广度优先搜索遍历算法则需要使用队列结构。6.若一个连通图中每个边上的权值均不同，则得到的最小生成树是_唯一（唯一/不唯一）的。7.以下有向图中，从顶点A出发到达顶点E的最短路径长度为_34_。EFDBCA39715113017201217三、判断题1、用邻接矩阵表示图进行深度优先遍历时，通常是采用队列来实现算法的。(0)2、n个顶点的连通图，至少有n-1条边。（1）3、有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。（0）4、若连通图G中的一条边e是所以边中权值最小的边，则图G必存在着一最小生成棵包含边e的最小生成树。（1）四、应用题1、设无向网G=（V，E）如下图所示，顶点集V利用线性表{A,B,C,D,E,F}进行存储，求该网的邻接矩阵，并分别求出该图的深度优先和广度优先遍历结果。20305115010ABCDEF60深度：ACBDEF广度：ACFBDE2、设图G=（V，E），其中V={A,B,C,D,E,F},其邻接矩阵如下所示，按照Prim方法，从顶点A出发，求该网的最小生成树的产生过程，并计算该最小生成树的代价值。FEDCBAG06010100600203010200505005105010030100)(AFEDCBA最小生成树：FD20BAEC51030103、设无向网G=（V，E）如下图所示，按照Dijkstra算法，求从A出发到达其余各顶点的最短路径10ABCDEF720182511309530A-B:AB10A-C:ADC16A-D:AD5A-E:ABE19A-F:ADF23姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………