资源描述：
《数据结构专科辅导六图的辅导练习题及解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构专科辅导六------图的辅导练习题及解答<一）单项选择题1.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(>。b5E2RGbCAPAsBs-1Cs+1Dn2.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为(>。p1EanqFDPwAsBs-1Cs+1D2s3.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为(>。AnBeCn+eD2e4.在一个具有n个顶点的无向完全图中，则所含的边数为(>。AnBn(n-1>Cn(n-1>/2Dn(n+1>/25
2、.在一个具有n个顶点的有向完全图中，则所含的边数为(>。AnBn(n-1>Cn(n-1>/2Dn(n+1>/26.在一个无权图中，若两顶点之间的路径长度为k，则该路径上的顶点数为(>。AkBk+1Ck+2D2k7.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为(>。A0B1CnDn+18.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用(>次深度优先搜索遍历的算法。DXDiTa9E3dAkB1Ck-1Dk+19.若要把n个顶点连接为一个连通图，则至少需要(>条边。AnBn+1Cn-1D2n10.在一个
3、具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素<又称为有效元素）的个数为(>。RTCrpUDGiTAnBn´eCeD2´e11.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为(>。AnBn´eCeD2´e12.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为(>。AnBn´eCeD2´e13.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为(>。5PCzVD7HxAAnB2nCeD2e8/814.在一个无权图的邻接表表示中，每个边结点至少包含(>域。A1B2C
4、3D415.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为(>。jLBHrnAILgAk1Bk2Ck1-k2Dk1+k216.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为(>。xHAQX74J0XAk1Bk2Ck1-k2Dk1+k217.对于一个无向图，下面(>种说法是正确的。A每个顶点的入度等于出度B每个顶点的度等于其入度与出度之和C每个顶点的入度为0D每个顶点的出度为018.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的(>。A出边数
5、B入边数C度数D度数减119．若一个图的边集为{(A,B>,(A,C>,(B,D>,(C,F>,(D,E>,(D,F>}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为(>。LDAYtRyKfEAA,B,C,F,D,EBA,C,F,D,E,BCA,B,D,C,F,EEA,B,D,F,E,C20.若一个图的边集为{(A,B>,(A,C>,(B,D>,(C,F>,(D,E>,(D,F>}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为(>。Zzz6ZB2LtkAA,B,C,D,E,FBA,B,C,F,D,ECA,B,D,C,
6、E,FDA,C,B,F,D,E21.若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(>。dvzfvkwMI1A1,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>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(>。rqyn14ZNXIA1,2,3,4,5B1,2,4,3,5C1,2,4,5,3D1,4,2,5
7、,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}，则该图的最小生成树的权为(>。EmxvxOtOcoA43B16C18D2325.已知一个无向图的边集为{(0,1>3,(0,2>5,(0,3>6,(1,4>10,(2,3>2,(2,4>9,(3,4>8}，则该图的最小生成树的边集为(>。SixE2yXPq5A{(0,1>3,(0,2>5,(0,3>6,(3,4>8}B
8、{(0,1>3,(0,2>5,(0,3>6,(2,3>2}6ewMyirQFL8/8C{(2,3>2,(0,2>5,(3,4>8,(0,3>6}D{(
