资源描述：
《数据结构习题与答案--图.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第7章图9一、单选题01、在一个图中，所有顶点的度数之和等于图的边数的倍。A．1/2B．1C．2D．402、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B．1C．2D．403、有8个结点的无向图最多有条边。A．14B．28C．56D．11204、有8个结点的无向连通图最少有条边。A．5B．6C．7D．805、有8个结点的有向完全图有条边。A．14B．28C．56D．11206、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A．栈B．队列C．树D．图07、用邻接表表示图进行深度优先遍历时，通常
2、是采用来实现算法的。A．栈B．队列C．树D．图08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。A．O(n)B．O(e)C．O(n+e)D．O(n2)09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。A．0243156B．0136542C．0134256D．036154210、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。A．0243651B．0123456C．0423156D．013425611、已知图的邻接表
3、如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。A．0132B．0231C．0321D．012312、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。A．0321B．0123C．0132D．031213、图的深度优先遍历类似于二叉树的。A．先序遍历B．中序遍历C．后序遍历D．层次遍历14、图的广度优先遍历类似于二叉树的。A．先序遍历B．中序遍历C．后序遍历D．层次遍历15、任何一个无向连通图的最小生成树。A．只有一棵B．一棵或多棵C．一定有多棵D．可能不存在()16、对于一个具有n个结点和
4、e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。A．n、2eB．n、eC．n、n+eD．2n、2e17、判断有向图是否存在回路，可以利用算法。A．关键路径B．最短路径的DijkstraC．拓扑排序D．广度优先遍历18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目19、求最短路径的Dijkstra算法的时间复杂度是___。A．O(n)B．O(n+e)C．O(n2)D．O(n*e)20、设图G采用邻接表存
5、储，则拓扑排序算法的时间复杂度为。A．O(n)B．O(n+e)C．O(n2)D．O(n*e)21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。A．第i行非∞的元素之和B．第i列非∞的元素之和C．第i行非∞且非0的元素个数D．第i列非∞且非0的元素个数22、一个有n个顶点的无向图最多有条边。A．nB．n(n-1)C．n(n-1)/2D．2n23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。A．nB．(n-1)2C．n-1D．n224、对某个无向图的邻接矩阵来说，。A．第i行上的非零元素个数和第i列的
6、非零元素个数一定相等B．矩阵中的非零元素个数等于图中的边数C．第i行上，第i列上非零元素总数等于顶点vi的度数D．矩阵中非全零行的行数等于图中的顶点数25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。A．abecdfB．acfebdC．aebcfdD．aedfcb926、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为。A．abcedfB．abcefdC．aebcfdD．acfdeb27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1
7、出发得到的顶点序列是。A．v1,v2,v3,v5,v4B．v1,v2,v3,v4,v5C．v1,v3,v4,v5,v2D．v1,v4,v3,v5,v228、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是。A．v1,v2,v3,v4,v5B．v1,v3,v2,v4,v5C．v1,v2,v3,v5,v4D．v1,v4,v3,v5,v229、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用次深度优先遍历算法。A．kB．1C．n-kD．n30、以下不正确的说法
8、是。A．无向图中的极大连通子图称为连通分量B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先搜索方法二、填空题01、在有向图中，以顶点v为终点的边的数目
