.1/15一、单选题C01、在一个图中，所有顶点的度数之和等于图的边数的倍。A)1/2B)1C)2D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A)1/2B)1C)2D)4B03、有8个结点的无向图最多有条边。A)14B)28C)56D)112C04、有8个结点的无向连通图最少有条边。A)5B)6C)7D)8C05、有8个结点的有向完全图有条边。A)14B)28C)56D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A)栈B)队列C)树D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A)栈B)队列C)树D)图A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。A)O(n)B)O(e)C)O(n+e)D)O(n2)C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。A)0243156B)0136542C)0134256D)0361542B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。A)0243651B)0123465C)0423156D)0134256D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。A)0132B)0231C)0321D)0123A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。A)0321B)0123C)0132D)0312A13、图的深度优先遍历类似于二叉树的。A)先序遍历B)中序遍历C)后序遍历D)层次遍历D14、图的广度优先遍历类似于二叉树的。A)先序遍历B)中序遍历C)后序遍历D)层次遍历B15、任何一个无向连通图的最小生成树。A)只有一棵B)一棵或多棵C)一定有多棵D)可能不存在A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。A)n、2eB)n、eC)n、n+eD)2n、2eC17、判断有向图是否存在回路，可以利用___算法。A)关键路径B)最短路径的DijkstraC)拓扑排序D)广度优先遍历A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。A)图中每个顶点的入度B)图中每个顶点的出度C)图中弧的条数D)图中连通分量的数目.2/15C19、求最短路径的Dijkstra算法的时间复杂度是___。A)O(n)B)O(n+e)C)O(n2)D)O(n*e)B20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。A)O(n)B)O(n+e)C)O(n2)D)O(n*e)D21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。A)第i行非∞的元素之和B)第i列非∞的元素之和C)第i行非∞且非0的元素个数D)第i列非∞且非0的元素个数C22、一个有n个顶点的无向图最多有条边。A)nB)n(n-1)C)n(n-1)/2D)2nD23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。A)nB)(n-1)2C)n-1D)n2A24、对某个无向图的邻接矩阵来说，。A)第i行上的非零元素个数和第i列的非零元素个数一定相等B)矩阵中的非零元素个数等于图中的边数C)第i行上，第i列上非零元素总数等于顶点vi的度数D)矩阵中非全零行的行数等于图中的顶点数D25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。A)abecdfB)acfebdC)aebcfdD)aedfcbB26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为。A)abcedfB)abcefdC)aebcfdD)acfdebC27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1出发得到的顶点序列是。A)v1,v2,v3,v5,v4B)v1,v2,v3,v4,v5C)v1,v3,v4,v5,v2D)v1,v4,v3,v5,v2B28、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是。A)v1,v2,v3,v4,v5B)v1,v3,v2,v4,v5C)v1,v2,v3,v5,v4D)v1,v4,v3,v5,v2A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用次深度优先遍历算法。A)kB)1C)n-kD)nD30、以下不正确的说法是。A)无向图中的极大连通子图称为连通分量B)连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C)图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D)有向图的遍历不可采用广度优先搜索方法A31、图中有关路径的定义是___。A)由顶点和相邻顶点序偶构成的边所形成的序列B)由不同顶点所形成的序列C)由不同...
