《第七章图练习题》由会员分享，可在线阅读，更多相关《第七章图练习题（6页珍藏版）》请在金锄头文库上搜索。
1、第七章：图练习题一、 选择题1、一个有n个顶点的无向图最多有（ ）条边。A、n B、n(n-1) C、n(n-1)/2 D、2n2、具有6个顶点的无向图至少有（ ）条边才能保证是一个连通图。A、5 B、6 C、7 D、83、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（ ）。A、线性图 B、无向完全图 C、无向图 D、简单图4、具有4个顶点的无向完全图有（ ）条边。A、6 B、12 C、16 D、205、G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点A、6 B、7 C、8 D、96、存储稀疏图的数据结构常用的是（ ）。A、邻接矩阵 B、三元组 C、邻接表 D、十字链表7
2、、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（ ）。A、n B、(n-1)2 C、(n+1)2 D、n28、设连通图G的顶点数为n，则G的生成树的边数为（ ）。A、n-1 B、n C、2n D、2n-19、n个顶点的无向图的邻接表中结点总数最多有（ ）个。A、2n B、n C、n/2 D、n(n-1)10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（ ），所有顶点邻接表的结点总数为（ ）。A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（ ）。A、顶点v的
3、度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（ ）和（ ）（1） A、abecdf B、acfebd C、acebfd D、acfdeb（2） A、abcedf B、abcefd C、abedfc D、acfdeb13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（ ）和（ ）。A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（ ）和（ ）。A、v
4、1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v215、已知有8个顶点为A，B，C，D，E，F，G，H的无向图，其邻接矩阵存储结构如下，由此结构，从A点开始深度遍历，得到的顶点序列为（ ）。ABCDEFGHA01010000B10101110C01010000D10100010E01000001F01000011G01010101H00001110A、ABCDGHFE B、ABCDGFHE C、ABGHFECD D、ABFHEGDCE、ABEHFGDC F、ABEHGFCD16、已知一个图如下，在该图的最小生成树中各
5、边上权值之和为（ ），在该图的最小生成树中，从v1到v6的路径为（ ）。A、31 B、38 C、36 D、43 E、v1,v3,v6 F、v1,v4,v6 G、v1,v5,v4,v6 H、v1,v4,v3,v6 17、关键路径是事件结点网络中的（ ）。A、从源点到汇点的最长路径 B、从源点到汇点的最短路径C、最长的回路 D、最短的回路18、正确的AOE网必须是（ ），AOE网中某边权值应当是（ ），权值为0的边表示（ ）。（1）A、完全图 B、哈密尔顿图 C、无环图 D、强连通图（2）A、实数 B、正整数 C、正数 D、非负数（3）A、为决策而增加的活动 B、为计算方便而增加的活动 C、表示活
6、动间的时间顺序关系 D、该活动为关键活动19、已知一个图如下，则由该图得到的一种拓扑序列为（ ）。A、v1,v4,v6,v2,v5,v3 B、v1,v2,v3,v4,v5,v6 C、v1,v4,v2,v3,v6,v5 D、v1,v2,v4,v6,v3,v520、下面结论中正确的是（ ）A、在无向图中，边的条数是顶点度数之和。 B、在图结构中，顶点可以没有任何前驱和后继。 C、在n个顶点的无向图中，若边数大于n-1，则该图必定是连通图 D、图的邻接矩阵必定是对称矩阵。21、下面结论中正确的是（ ）A、若有向图的邻接矩阵中对角线以下元素均为0，则该图的拓扑排序序列必定存在。 B、网络的最小代价生成
7、树是唯一的。 C、在拓扑排序序列中，任意两个相继顶点vi和vj都存在从vi到vj的路径。 D、在有向图中，从一个顶点到另一个顶点的最短路径是唯一的。22、下面结论不正确的是（ ）。A、无向图的连通分量是该图的极大连通子图。 B、有向图用邻接矩阵表示容易实现求顶点度数的操作。 C、无向图用邻接矩阵表示，图中的边数等于邻接矩阵元素之和的一半。 D、有向图的邻接矩阵必定不是对称矩阵。23、下面结论中正确的是（ ）。A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按深度优先搜索遍历的结果是唯一的。 C、若有向图G中包含一个环，则G的顶点间不存在拓扑排序。 D、图的拓
8、扑排序序列是唯一的。24、下面结论中不正确的是（ ）。A、按广度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。 B、一个图按广度优先搜索遍历的结果是唯一的。 C、无向图的邻接表表示法中，表中结点的数目是图中边的条数的2倍。 D、图的多重邻接表表示法中，表中结点数目是图中边的条数。二、 填空题1、n个顶点的连通图至少有（ ）条边。2、一个无向图有n个顶点和e条边，则所有顶点的度数之和为（ ）。3、在图形结构中，每个结点的前驱结点和后继结点可以有（ ）。4、若无向图G的顶点度数的最小值大于或等于（ ）时，G至少有一条回路。5、设无向图G的顶点数为n，图G最少有（ ）边，最多有（ ）
9、条边。若G为有向图，有n个顶点，则图G最少有（ ）条边，最多有（ ）条边。具有n个顶点的无向完全图，边的总数为（ ）条，而有n个顶点的有向完全图，边的总数为（ ）条。6、在无权图G的邻接矩阵A中，若(vi,vj)或属于G的边/弧的集合，则对应元素Aij等于（ ），否则等于（ ）。7、在无向图G的邻接矩阵A中，若Aij=1，则Aji等于（ ）。8、已知一个图的邻接矩阵表示，计算第I个顶点的入度方法为（ ）9、在一个图G的邻接表表示中，每个顶点的邻接表中所含的结点数，对于有向图而言等于该顶点的（ ），而对于无向图而言等于该顶点的（ ）。10、已知图G的邻接表如下，从顶点v1出发的深度优先搜索遍历序
10、列为（ ），广度优先序列为（ ）。11、n个顶点的弱连通有向图G最多有（ ）条弧，最少有（ ）条弧。12、在n个顶点e条边的连通图中，连通分量个数为（ ）。13、任何（ ）的有向图，其所有结点都可以排 在一个拓扑序列中，拓扑排序的方法是先从图中选一个（ ）为0的结点且输出，然后从图中删除该结点及其（ ），反复执行，直到所有结点都输出为止。14、一个连通图的（ ）是一个极小连通子图。15、在AOE网中，从源点到汇点各活动时间总和最长的路径为（ ）。三、 简答题1、 对于一个具有n个顶点的连通无向图，如果它有且只有一个简单回路，此图有几条边？一个具有n个顶点的弱连通图至少有几条边？2、 已知某图的
11、邻接表，如何建立该图的邻接矩阵？3、 有4个顶点A，B，C，D的无向连通图，按广度和深度搜索遍历结果都为ABCD，画出所有可能的结构图？4、 简述无向图和有向图有哪几种存储结构，并说明各种结构在图的不同操作中有什么优越性？5、 什么是AOE网的关键路径？6、 给出下图邻接矩阵、邻接表和邻接多重表存储结构。从顶点1出发进行广度个深度优先搜索遍历。7、 对下图，请给出（1）对应的邻接矩阵，并给出v1,v2,v3三个顶点的出度和入度；（2）邻接表和逆邻接表表示；（3）强连通分量。8、 试列出图中全部可能的拓扑排序序列。答案：一、 选择题12345678CABADCDA910111213141516D
12、AGCDBBDCBB1718192021222324ACDBABADCB二、 填空题1n-19出度数，度数22e10V1v2v3v6v5v4,v1v2v5v4v3v63任意多个11N(n-1),n-14412等于150,n(n-1)/2,0,n(n-1),n(n-1)/2,n(n-1)13无环，前驱，所有以它为尾的弧61,014生成树7115关键路径8求矩阵第I列非零元素之和三、 简答题1、（1）n条边 （2）n-1条边2、根据邻接表中表向量的大小确定邻接矩阵的行列数；由第I个顶点指向的单链表中结点j来确定邻接矩阵中第I行j列元素为1，其余为0。3、略4、图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。借助于邻接矩阵容易判断任意两个顶点是否有边/弧相连，并容易求出顶点的度。对无向图，顶点vi的度是邻接矩阵中第I行或第j列的元素之和；对有向图，第I行的元素之和为顶点vi的出度，第j列的元素之和为顶点vj的入度。在无向图的邻接表中，第I个链表中表结点个数恰好为顶点vi的度；而在有向图中，第I个链表中表结点个数只是顶点vi的出度。利用十字链表容易求得顶点的出度和入度。邻接多重表适合于对边进行操作，如在遍历时对边作记号或在拓扑排序中对边进行删除。5、在AOE网中完成工程的最短时间是从开始点到完成点的最长路径的长度，这条路径长度最长的路径叫关键路径。后面题答案略。
