第4章图结构测试卷

中国人民解放军理工大学指挥自动化学院试卷考试科目：第4章图结构队别专业：学号：姓名：考试日期：年月日题号123总分得分阅卷人1.单项选择题（每题2分，共36分）【1】在一个无向图中，所有顶点的度数之和等于所有边数的倍。A．1／2B．1C．2D．4【2】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1／2B．1C．2D．4【3】一个有n个顶点的无向图最多有条边。A．nB．n(n-1)C．n(n-1)/2D．2n【4】具有4个顶点的无向完全图有条边。A．6B．12C．16D．20【5】具有6个顶点的无向图至少应有条边才能确保是一个连通图。A．5B．6C．7D．8【6】在一个具有n个顶点的无向图中，要连通全部顶点至少需要条边。A．nB．n+1C．n-1D．n/2【7】对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。A．nB．(n-1)2C．n-1D．n2【8】对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为①：所有邻接表中的结点总数是②。①A．nB．n+1C．n-1D．n+e②A．e/2B．eC．2eD．n+e【9】对某个无向图的邻接矩阵来说，。A．第i行上的非零元素个数和第i列的非零元素个数一定相等B．矩阵中的非零元素个数等于图中的边数C．第i行上，第i列上非零元素总数等于顶点vi的度数D．矩阵中非全零行的行数等于图中的顶点数【10】已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为①；按广度搜索法进行遍历，则可能得到的一种顶点序列为②。①A．a，b，e，c，d，fB．a，c，f，e，b，dC．a，e，b，c，f，dD．a，e，d，f，c，b②A．a，b，c，e，d，fB．a，b，c，e，f，dC．a，e，b，c，f，dD．a，c，f，d，e，b【11】已知一有向图的邻接表存储结构如图所示。（1）根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是①。A．v1，v2，v3，v5，v4B．v1，v2，v3，v4，v5C．v1，v3，v4，v5，v2D．v1，v4，v3，v5，v2（2）根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是②。A．v1，v2，v3，v4，v5B．v1，v3，v2，v4，v5C．v1，v2，v3，v5，v4D．v1，v4，v3，v5，v2【12】采用邻接表存储的图的深度优先遍历算法类似于二叉树的。A．先序遍历B．中序遍历C．后序遍历D．按层遍历【13】采用邻接表存储的图的广度优先遍历算法类似于二叉树的。A．先序遍历B．中序遍历C．后序遍历D．按层遍历【14】一个图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用次深度优先遍历算法。A．kB．1C．k-1D．k+1【15】任何一个无向连通图的最小生成树。A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在【16】以下说法中不正确的是。A．无向图中的极大连通子图称为连通分量B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点c．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先搜索方法【17】判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以用。A．求关键路径的方法B．求最短路径的Dijkstra方法【18】下面不正确的说法是。(1)求从指定源点到其余各顶点的Dijkstra最短路径算法中弧上权值可以为负值。(2)利用Dijkstra算法求所有不同顶点对的最短路径的算法时间为O(n3)(图用邻接矩阵表示)。(3)利用Floyd算法求每个不同顶点对的算法中允许弧上的权值为负，但不能有权之和为负的回径。A．(1)、(2)、(3)B．(1)C．(1)、(3)D．(2)、(3)2.填空题（每题12分，共26分）【1】在n个顶点的无向图中，若边数n-1，则该图必是连通图。此断言是的。【2】有向图G有n个顶点{v1，v2，…，vn)，它的邻接矩阵为A，A[il[j]=1表示从vi到vj存在邻接关系，而A[i][j]=0则不存在。故G中顶点vi的度为①，而②为所有通过vk的存在形为vi,vk，vi的路径个数之和。①②【3】n个顶点的连通图至少条边。【4】在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于。【5】一个图的①表示法是惟一的，而②表示法是不惟一的。①②【6】G是一个非连通无向图，共有28条边，则该图至少有个顶点。【7】具有10个顶点的无向图，边的总数最多为。【8】在有n个顶点的有向图中，每个顶点的度最大可达。【9】已知图G的邻接表如图所示，其从顶点v1出发的深度优先搜索序列为①，其从顶点v1出发的广度优先搜索序列为②。①②【10】已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是。【11】已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是。【12】图的深度优先搜索序列和广度优先搜索序列不是惟一的。此断言是的。【13】如果含n个顶点的图形成一个环，则它有棵生成树。【14】对n个顶点的连通图来说，它的生成树一定有条边。【15】对于如图所示的图，用普里姆算法从顶点1开始求最小生成树，按次序产生的边为①，共②条边；用克鲁斯卡尔算法产生的边次序是③。(注：边用(i,j)的形式表示。)①②③【16】设图G有n个顶点和e条边，采用邻接矩阵存储，则拓扑排序算法的时间复杂度为。【17】求最小生成树的克鲁斯卡尔算法的时间复杂度为①，它对②图较为适合。①②【18】若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。此断言是的。【19】设有向图G如图所示。（1）写出所有的拓扑序列；（2）添加边后，则仅可能有惟一的拓扑序列。3.简答题（共23分）【1】（3分）从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些?【2】（4分）请回答下列关于图的一些问题：（1）有n个顶点的有向强连通图最多有多少条边?最少有多少条边?（2）表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否为稀疏矩阵?（3）对于一个有向图，不用拓扑排序，如何判断图中是否存在环?【3】（3分）给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。【4】（3分）使用普里姆算法构造出如图所示的图G的一棵最小生成树。【5】（3分）使用克鲁斯卡尔算法构造出如图所示的图G的一棵最小生成树。【6】（4分）如图所示给出了图G及对应的邻接表，根据给定的dfs算法：intvisited[MAXVEX];voiddfs(AdjList*gl,intv){structArcNode*p;printf(%d,v);visited[v]=1;p=gl[v]-firstarc;while(p!=NULL)if(visited[p-adjvex]==0)dfs(gl,p-adjvex);p=p-next;}（1）从顶点7出发，求出其搜索序列。（2）指出p的整个变化过程。【7】（3分）给出一个以下带权图的邻接矩阵表示：试完成下列要求：（1）写出在该图上从顶点1出发进行深度优先遍历的顶点序列，并据此判断该图是否为连通图。（2）画出该图的带权邻接表。4.算法设计题（每题5分，共15分）【1】编写一个算法将一个无向图的邻接矩阵转换成邻接表。【2】设计一个算法，求出无向图G的连通分量个数。【3】假设图用邻接矩阵表示，设计一个算法，判定从顶点vi到顶点vj是否可达。