文档介绍：第七次作业一、选择题 1 、深度优先遍历类似与二叉树的 A: A. 先根遍历. 中根遍历 C. 后根遍历 D. 层次遍历 2 、广度优先遍历类似与二叉树的 D: A. 先根遍历 B. 中根遍历 C. 后根遍历 D. 层次遍历 3 、下列关于开放树(Free Tree) 的说法错误的是 C: A. 具有 n 个结点的开放树包含 n-1 条边 B. 开放树没有回路 C. 开放树可以是非连通图 D. 在开放树中任意加一条边,一定会产生回路 4、在如下图所示的图中,从顶点 a 出发,按深度优先遍历,则可能得到的一种顶点的序列为D。 A. a, b, e, c, d,f B. a, c, f, e, b,d C. a, e, b, c, f,d D. a, e, d, f, c,b 5、在如上图所示的图中,从顶点 a 出发,按广度优先遍历,则可能得到的一种顶点的序列为A。 A. a, b, e, c, d,f B. a, b, e, c, f,d C. a, e, b, c, f,d D. a, e, d, f, c,b 二、填空题 1 、图的遍历有深度和广度优先遍历等方法。 2 、在深度优先搜索和广度优先搜索中,都采用 visited[i]= false 的方式设置第 i 个顶点为 new ,而采用 visited[i]= true 的方式标识第 i 个结点为 old 。 3 、由于深度优先算法的特点,深度优先往往采用递归的方式实现。 4 、由于广度优先算法的特点,在广度优先实现过程中,往往要借助于另一种数据结构队列实现。 5、在深度优先搜索和广度优先搜索中,在搜索过程中所经过的边都称为树边三、已知一个连通图如下图所示,分别给出一个按深度优先遍历和广度优先遍历的顶点序列(假设从顶点 v1 出发) 。并编程分别实现该图的邻接矩阵表示和邻接表表示,要求编写相关基本操作,并在主函数中求出深度优先序列和广度优先序列。深度优先顶点序列: v1v 6v4 v5v 3v2 等; 广度优先顶点序列: v1v2v4v6v3v5 等// 邻接矩阵表示深度优先搜索、广度优先搜索: #include<iostream> using namespace std; #define NumVertices 6// 定义顶点个数 typedef char VertexData;// 顶点数据类型 typedef int EdgeData;// 边上权值类型 typedef struct{ VertexData vexlist[NumVertices];// 顶点数组 EdgeData edge[NumVertices][NumVertices];// 邻接矩阵 int n;// 定点数 int e;// 边数} MTGraph;// 邻接矩阵表示的图结构,这里是无向图 void IniMGraph(MTGraph *G)// 初始化邻接矩阵的图结构{ for(int i=0; i<NumVertices; i++) for(int j=0; j<NumVertices; j++) G->edge[i][j]=0;// 将所有的边删除 G->n=0; G->e=0; } void NewNode(MTGraph *G, VertexData v)// 单纯添加顶点 v ,不添加边{ G->vexlist[G->n]=v; G->n++; } void DelNode(MTGraph *G, int m)// 删除第 m 个顶点{ int i, j; if(G->n==0 || m>=NumVertices)// 没有顶点|| 不存在顶点 m return; for(i=m; i<G->n-1; i++)// 顶点 m 后面的顶点前移 G->vexlist[i]=G->vexlist[i+1]; // 删除与第 m 个顶点相连的边// 删掉边数 for(i=0; i<G->n; i++) { if(G->edge[i][m]!=0) G->e--; } // 邻接矩阵降阶 for(i=m; i<G->n-1; i++) for(j=0; j<G->n; j++) G->edge[i][j]=G->edge[i+1][j]; for(i=m; i<G->n-1; i++) for(j=0; j<G->n-1; j++) G->edge[j][i]=G->edge[j][i+1]; // 减掉顶点数 G->n--; } // 判断 v1和 v2 之间有没有边 bool IsEdge(MTGraph *G, int v1, int v2) { if(v1>=0 && v1<G->n && v2>=0 && v2<G->n && v1!=v2) if(G->edge[v1][v