②A)a,b,c,d,e,f B)a, b, c, e, f, d c)a,e, b, c, f, d D)a,c, f, d, e, b 10.已知一有向图的邻接表存储结构如图所示。 2 4 (1)根据有向图的深度优先遍历算法,从顶点v1出发,所得到的顶点序列是c A)vl, v2, v3, v5, v4 B)vl, v2, v3, v4, v5 C)v1, v3, v4, v5, v2 D) vl, v4, v3, v5, v2 (2)根据有向图的宽度优先遍历算法,从顶点v1出发,所得到的顶点序列是b A)v1,v2,v3,v4,v5B)vl,v3,v2,v4,v5C)v1,v2,v3,v5,v4D)v1,v4,v3,wv5,v2 1.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_a A)先序遍历B)中序遍历C)后序遍历D)按层遍历 12.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的 A)先序遍历B)中序遍历C)后序遍历D)按层遍历 13.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用d A)求关键路径的方法 B)求最短路径的 Di jkstra方法 C)宽度优先遍历算法 D)深度优先遍历算法 填空题(将正确的答案填在相应的空中) 1.N个顶点的连通图至少N-1条边 在无权图G的邻接矩阵A中,若(vi,vj)或<vi,vj属于图G的边集合,则对应元素A[i][j等于」 否则等于0。 3.在无向图G的邻接矩阵A中,若A[i][j等于1,则A[j[]等于_1 4.已知图G的邻接表如图1所示,其从顶点v1出发的深度优先搜索序列为vlv2v3v6v5v4,其从顶 点v1出发的宽度优先搜索序列为vlv2v5v4v3v6② A) a,b,c,d,e,f B) a,b,c,e,f,d C) a,e,b,c,f,d D) a,c,f,d,e,b 10．已知一有向图的邻接表存储结构如图所示。 (1) 根据有向图的深度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是_c____。 A) v1,v2,v3,v5,v4 B) v1,v2,v3,v4,v5 C) v1,v3,v4,v5,v2 D) v1,v4,v3,v5,v2 (2) 根据有向图的宽度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是_b____。 A) v1,v2,v3,v4,v5 B) v1,v3,v2,v4,v5 C) v1,v2,v3,v5,v4 D) v1,v4,v3,v5,v2 11．采用邻接表存储的图的深度优先遍历算法类似于二叉树的_a____。 A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历 12．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的 d_____。 A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历 13．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用__d___。 A） 求关键路径的方法 B） 求最短路径的 Dijkstra 方法 C） 宽度优先遍历算法 D） 深度优先遍历算法 二．填空题（将正确的答案填在相应的空中） 1． N 个顶点的连通图至少_N-1____条边。 2． 在无权图 G 的邻接矩阵 A 中，若（vi,vj）或<vi,vj>属于图 G 的边集合，则对应元素 A[i][j]等于_1____， 否则等于_0____。 3． 在无向图 G 的邻接矩阵 A 中，若 A[i][j]等于 1，则 A[j][i]等于_1____。 4． 已知图 G 的邻接表如图 1 所示，其从顶点 v1 出发的深度优先搜索序列为_v1v2v3v6v5v4____，其从顶 点 v1 出发的宽度优先搜索序列为___v1v2v5v4v3v6__。 1 2 ^ 3 4 ^ 5 3 4 ^ 4 5 2 4 2 V6 ^ V4 V6 V3 ^ V3 V5 ^ V1 V2 V3 V4 V5 V6 6 V2 V5 V4 ^