第4章图结构测试卷.doc

理工大学指挥自动化学院试卷考试科目： 第4 章 图结构 队别专业： 学 号： 姓 名： 考试日期： 年 月 日题 号123总 分得 分阅 卷 人1.单项选择题（每题2分，共36分）【1】在一个无向图中，所有顶点的度数之和等于所有边数的 倍。 A12 B1 C2 D4 【2】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A12 B1 C2 D4【3】一个有n个顶点的无向图最多有 条边。 An Bn(n-1) Cn(n-1)/2 D2n【4】具有4个顶点的无向完全图有 条边。 A6 B12 C16 D20 【5】具有6个顶点的无向图至少应有 条边才能确保是一个连通图。 A5 B6 C7 D8 【6】在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边。 An Bn+1 Cn-1 Dn/2 【7】对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。 An B(n-1)2 Cn-1 Dn2 【8】对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 ：所有邻接表中的结点总数是 。 An Bn+1 Cn-1 Dn+e Ae/2 Be C2e Dn+e 【9】对某个无向图的邻接矩阵来说， 。 A第i行上的非零元素个数和第i列的非零元素个数一定相等 B矩阵中的非零元素个数等于图中的边数 C第i行上，第i列上非零元素总数等于顶点vi的度数 D矩阵中非全零行的行数等于图中的顶点数【10】已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 ；按广度搜索法进行遍历，则可能得到的一种顶点序列为 。 Aa，b，e，c，d，f Ba，c，f，e，b，d Ca，e，b，c，f，d Da，e，d，f，c，b Aa，b，c，e，d，f Ba，b，c，e，f，d Ca，e，b，c，f，d Da，c，f，d，e，b 【11】已知一有向图的邻接表存储结构如图所示。 （1）根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是 。 Av1，v2，v3，v5，v4 Bv1，v2，v3，v4，v5 Cv1，v3，v4，v5，v2 Dv1，v4，v3，v5，v2 （2）根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是 。 Av1，v2，v3，v4，v5 Bv1，v3，v2，v4，v5 Cv1，v2，v3，v5，v4 Dv1，v4，v3，v5，v2【12】采用邻接表存储的图的深度优先遍历算法类似于二叉树的 。 A先序遍历 B中序遍历 C后序遍历 D按层遍历【13】采用邻接表存储的图的广度优先遍历算法类似于二叉树的 。 A先序遍历 B中序遍历 C后序遍历 D按层遍历【14】一个图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用 次深度优先遍历算法。 Ak B1 Ck-1 Dk+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，Ailj=1表示从vi到vj存在邻接关系，而Aij=0则不存在。故G中顶点vi的度为 ，而 为所有通过vk的存在形为的路径个数之和。 【3】n个顶点的连通图至少 条边。 【4】在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 。 【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算法：int visitedMAXVEX; void dfs(AdjList *gl,int v) struct ArcNode *p; printf(%d ,v); visited v =1; p=glv-firstarc; while (p!=NULL) if (visited p-adjvex =0) dfs (gl,p-adjvex) ; p=p-next ; （1）从顶点7出发，求出其搜索序列。（2）指出p的整个变化过程。【7】（3分）给出一个以下带权图的邻接矩阵表示： 试完成下列要求：（1）写出