数据结构试题和答案第7章ans

1、下面关于图的存储的叙述中正确的是()。用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关答案：C对于具有e条边的无向图，它的邻接表中有()个边结点。A:e-1B:eC:2(e-1)D:2e答案：D，(vi,vj)以vi作为头结点保存一次，以vj作为头结点保存一次。图的深度优先搜索类似于树的(A )次序遍历。A:先序B:中序C:后序D:层次设无向图的顶点个数为n，则该图最多有()条

2、边。A: n-1B: n(n-1)/2C: n(n+1)/2D: n(n-1)答案：最多边时：完全图。选B完全有向图:n(n-1)对于有向图，其邻接矩阵表示比邻接表表示更易于()。A:求一个顶点的度 B:求一个顶点的邻接点C:进行图的深度优先遍历D:进行图的广度优先遍历答案：B与邻接矩阵相比，邻接表更适合于存储()。A:无向图B连通图C稀疏图D稠密图答案：C若用邻接矩阵表示一个有向图，则其中每一列包含的 1的个数为()A.图中每个顶点的入度 B.图中每个顶点的出度C.图中弧的条数D.图中连通分量的数目答案：A设无向图的顶点个数为n，则该图最多有()条边。A. n-1B. n(n-1)/2 C.

3、 n(n+1)/2 D. 0E. n2 TOC o 1-5 h z 一个n个顶点的连通无向图，其边的个数至少为()。A. n-1B. nC. n+1D. nlogn；答案：极小连通图，An个结点的完全有向图含有边的数目()。A. n*nB. n (n+1) C. n/2D. n* (nl)在一个无向图中，所有顶点的度数之和等于所有边数(B)倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的(C )倍。A. 1/2B. 2C. 1D. 4在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A. O(n)B. O(n+e)C. O(n2)D. O(n3)答案：C对于一个具

4、有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任 一顶点度数的时间复杂度分别为_O (n) 和O(e/n)。图的优先搜索遍历算法是一种递归算法，图的优先搜索遍历算法需要使用队列。假定一个有向图的顶点集为a,b,c,d,e,f，边集为, , , , , ，则出度为0的顶点个数为，入度为1的顶点个数为。对于下图，从顶点 A 开始的深度优先遍历序列为ABCFEGHID。一个有n个结点的图，至少有 1 个连通分量。设G(V,E)和G(V，E)是连通图，如果V=V，E是保证G连通性的E的最小子集，那么G，被称为G 生成树。对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分

5、别为 n和 n-1。对于一个具有n个顶点e条边的无向图的邻接表的表示，邻接表的边结点个数为2e已知一无向图 G= (V, E),其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd,则采用的_深度 遍历方法。当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。.杳邻接表中入度为0的顶点，并进栈:.若栈不空，则输出栈顶元素,并退栈；查Vj的直接后继Vk,对Vk入度处理，处理方法是Vk入度减1:.若栈空时，输出顶点数小于图的顶点数，说明有 环，否则拓扑排序完成。1、已知一个无向图如下图所示，试求：写出图的邻接矩阵利用Dijkstra算法求顶点V1到其他顶点间的最短