B070106 图图的辅导练习题及解答.pdf

《B070106 图图的辅导练习题及解答.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构专科辅导六------图的辅导练习题及解答（一）单项选择题1.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为()。AsBs-1Cs+1Dn2.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为()。AsBs-1Cs+1D2s3.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为()。AnBeCn+eD2e4.在一个具有n个顶点的无向完全图中，则所含的边数为()。AnBn(n-1)Cn(n-1)/2Dn(n+1)/25.在一个具有n个顶点的有向完全图中，则所含的边数为()。AnBn(n-1)Cn

2、(n-1)/2Dn(n+1)/26.在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为()。AkBk+1Ck+2D2k7.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为()。A0B1CnDn+18.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用()次深度优先搜索遍历的算法。AkB1Ck-1Dk+19.若要把n个顶点连接为一个连通图，则至少需要()条边。AnBn+1Cn-1D2n10.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为()。AnBneCeD2e11.在一个具有n个顶

3、点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为()。AnBneCeD2e12.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为()。AnBneCeD2e13.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为()。AnB2nCeD2e14.在一个无权图的邻接表表示中，每个边结点至少包含()域。A1B2C3D415.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为()。Ak1Bk2Ck1-k2Dk1+k216.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶

4、点单链表中的边结点数为()。1Ak1Bk2Ck1-k2Dk1+k217.对于一个无向图，下面()种说法是正确的。A每个顶点的入度等于出度B每个顶点的度等于其入度与出度之和C每个顶点的入度为0D每个顶点的出度为018.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()。A出边数B入边数C度数D度数减119．若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为()。AA,B,C,F,D,EBA,C,F,D,E,BCA,B,D,C,F,EEA,B,D,F,E,C20.若一个图

5、的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为()。AA,B,C,D,E,FBA,B,C,F,D,ECA,B,D,C,E,FDA,C,B,F,D,E21.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为()。A1,2,5,4,3B1,2,3,4,5C1,2,5,3,4C1,4,3,2,522.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从

6、顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为()。A1,2,3,4,5B1,2,4,3,5C1,2,4,5,3D1,4,2,5,323.由一个具有n个顶点的连通图生成的最小生成树中，具有()条边。AnBn-1Cn+1D2n24.已知一个无向图的边集为{(0,1)3,(0,2)5,(0,3)6,(1,4)10,(2,3)2,(2,4)9,(3,4)8}，则该图的最小生成树的权为()。A43B16C18D2325.已知一个无向图的边集为{(0,1)3,(0,2)5,(0,3)6,(1,4)10,(2,3)2,(2,4)9,(3,4)8}，则该图的最小生成树的边集为()。A{

7、(0,1)3,(0,2)5,(0,3)6,(3,4)8}B{(0,1)3,(0,2)5,(0,3)6,(2,3)2}C{(2,3)2,(0,2)5,(3,4)8,(0,3)6}D{(2,3)2,(0,2)5,(3,4)8,(0,1)3}26.已知一个有向图的边集为{,,,,,}，则由该图产生的一种可能的拓扑序列为()。Aa,b,c,d,eBa,b,d,e,bCa,c,b,e,dDa,c,d,b,e（二）填空题