第7章图一、单选题01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A．1/2 B．1 C．2 D ．402、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A．1/2 B．1 C．2 D．403、有8个结点的无向图最多有条边。

A．14 B．28 C．56 D．11204、有8个结点的无向连通图最少有条边。

A．5 B．6 C．7 D．805、有8个结点的有向完全图有条边。

A．14 B．28 C．56 D．11206、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A．栈 B．队列 C．树 D．图07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A．栈 B．队列 C．树 D．图08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A．O(n) B．O(e) C．O(n+e) D．O(n2)09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A．0 2 4 3 1 5 6 B．0 1 3 6 5 4 2C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 210、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A．0 2 4 3 6 5 1 B．0 1 2 3 4 5 6C．0 4 2 3 1 5 6 D．0 1 3 4 2 5 611、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A．0 3 2 1 B．0 1 2 3 C．0 1 3 2 D．0 3 1 2 13、图的深度优先遍历类似于二叉树的。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历14、图的广度优先遍历类似于二叉树的。

A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历15、任何一个无向连通图的最小生成树。

A．只有一棵 B．一棵或多棵C．一定有多棵 D．可能不存在( )16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。

A．n、2e B．n、e C．n、n+e D．2n、2e17、判断有向图是否存在回路，可以利用算法。

A．关键路径 B．最短路径的Dijkstra C．拓扑排序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采用邻接表存储，则拓扑排序算法的时间复杂度为。

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．n B．n(n-1) C．n(n-1)/2 D．2n23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。

A．n B．(n-1)2 C．n-1 D．n224、对某个无向图的邻接矩阵来说，。

A．第i行上的非零元素个数和第i列的非零元素个数一定相等B．矩阵中的非零元素个数等于图中的边数C．第i行上，第i列上非零元素总数等于顶点v i的度数D．矩阵中非全零行的行数等于图中的顶点数25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为。

A．abecdf B．acfebd C．aebcfd D．aedfcb26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为。

A．abcedf B．abcefd C．aebcfd D．acfdeb27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1出发得到的顶点序列是。

A．v1,v2,v3,v5,v4 B．v1,v2,v3,v4,v5 C．v1,v3,v4,v5,v2 D ．v1,v4,v3,v5,v228、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是。

A．v1,v2,v3,v4,v5 B．v1,v3,v2,v4,v5C．v1,v2,v3,v5,v4 D．v1,v4,v3,v5,v229、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用次深度优先遍历算法。

A．k B．1 C．n-k D．n30、以下不正确的说法是。

A．无向图中的极大连通子图称为连通分量B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先搜索方法二、填空题01、在有向图中，以顶点v为终点的边的数目称为v的。

02、含n个顶点的无向连通图中至少含有条边。

03、图的存储结构表示有、、十字链表、邻接多重表等多种存储结构。

04、遍历图的2种常见方法是优先遍历和优先遍历。

04、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的。

05、如果n个顶点的图是一个环，则它有棵生成树。

06、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为。

若采用邻接表存储，则空间复杂度为。

07、图的逆邻接表存储结构只适用于图。

08、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是。

09、图采用邻接矩阵表示，则计算第i个顶点入度的方法是求。

10、用邻接矩阵表示图时，则判断任意两个顶点vi和vj之间是否有路径相连，只需要检查即可。

11、用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为；用克鲁斯卡尔(Kruskal)算法的时间复杂度是。

12、对稀疏图最好用算法求最小生成树，对稠密图最好用算法来求解最小生成树。

13、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。

14、拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。

15、有向图G用邻接矩阵存储，则第i行的所有元素之和等于顶点i的。

16、有n个顶点的强连通有向图G至少有条弧。

17、设有向图G的邻接矩阵为A，如果图中不存在弧<Vi,Vj>，则A[i,j]的值为。

18、在n个顶点的无向图中，若边数>n-1，则该图必是连通图，此断言是的。

(正确/错误)19、在有n个顶点的有向图中，每个顶点的度最大可达。

20、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑排序序列必定。

(存在/不存在)三、简答题01、写出下面有向图的所有强连通分量。

02、已知图的邻接表如下，画出图G的所有连通分量。

03、如下图，分别用普里姆算法和克鲁斯卡尔算法从顶点1开始求最小生成树，写出按次序产生边的序列。

说明：边用(i,j)方式表示。

04、如下图，写出所有的拓扑序列，并求在添加什么边之后仅可能有惟一的拓扑序列。

05、已知如图所示的有向图，请给出该图的:(1) 每个顶点的入/出度；(2) 邻接矩阵；(3) 邻接表；(4) 逆邻接表。

06、写出无向带树图的邻接矩阵，并按普里姆算法填写表格中的内容，最后画出最小生成树；V b c D e F g h U V-UVex lowcost a4a3A∞a∞a∞a∞a∞{a} {bcdefgh}VexlowcostVexlowcostVexlowcostVexlowcostVexlowcostVexLowcostVexlowcost07、写出无向带树图的邻接表，并按克鲁斯卡尔算法写出求最小生成树产生的边序列。

08、已知二维数组表示的图的邻接矩阵如下图所示。

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

09、利用Dijkstra算法填写表格求图中从顶点a到其他各顶点间的最短路径，并写出最终结果。

终点Distb c D e f gS(终点集)k=1k=2k=3k=4k=5k=6求利用表格给出求解过程。

11、设图G=(V，E)，V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}。

画出图G，并写出图G中顶点的所有拓扑序列。

12、已知图的邻接表表示的形式说明如下：#define MaxNum 80typedef struct node{ int adjvex; //邻接点域struct node *next; //链指针域} EdgeNode; //边表结点结构描述typedef struct{ char vertex; //顶点域EdgeNode *firstedge; //边表头指针} VertexNode; //顶点表结点结构描述typedef struct{ VertexNode adjlist[MaxNum]; //邻接表int n,e;} AlGraph; //邻接表结构描述下列算法输出图G的深度优先生成树(或森林)的边，阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。

typedef enum {FALSE,TRUE} Boolean;Boolean visited[MaxNum];void DFSForest(AlGraph *G){ for(i=0; i<G->n; i++) visited[i]=___;for(i=0;i<G->n;i++)if (!visited[i]) DFSTree(G,i);}void DFSTree(AlGraph *G, int i){ visited[i]=TRUE;p=G->adjlist[i].firstedge;while(p!=NULL){ if (!visited[p->adjves]){ printf(G->adjlist[i].vertex, G->adjlist[p->adjvex].vertex);___;}___;}} 四、算法设计题01、编写编历算法，完成对图的深度优先搜索和广度优先搜索。

02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。