《数据结构第7章 图习题.doc》由会员分享，可在线阅读，更多相关《数据结构第7章 图习题.doc（13页珍藏版）》请在三一文库上搜索。
1、第7章 图一、单项选择题1在一个无向图G中，所有顶点的度数之和等于所有边数之和的_倍。 Al/2B1 C2D42在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_倍。Al/2 B1 C2D43一个具有n个顶点的无向图最多包含_条边。 An Bn1Cn-1 Dn(n-1)/24一个具有n个顶点的无向完全图包含_条边。An(n-l) Bn(n+l) Cn(n-l)/2 Dn(n-l)/25一个具有n个顶点的有向完全图包含_条边。An(n-1) Bn(n+l) Cn(n-l)/2 Dn(n+l)/26对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为_。An Bnn Cn-1 D(
2、n-l) (n-l)7无向图的邻接矩阵是一个_。A对称矩阵 B零矩阵 C上三角矩阵 D对角矩阵8对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为_。An Be C2n D2e9对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为_。An Be C2n D2e10在有向图的邻接表中，每个顶点邻接表链接着该顶点所有_邻接点。A入边 B出边 C入边和出边 D不是入边也不是出边11在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有_邻接点。A入边 B出边C入边和出边 D不是人边也不是出边12如果从无向图的任一顶点出发进行一次深度
3、优先搜索即可访问所有顶点，则该图一定是_。A完全图 B连通图C有回路 D一棵树13采用邻接表存储的图的深度优先遍历算法类似于二叉树的_算法。A先序遍历 B中序遍历C后序遍历 D按层遍历14采用邻接表存储的图的广度优先遍历算法类似于二叉树的_算法。A先序遍历 B中序遍历C后序遍历 D按层遍历15如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是_。AG肯定不是完全图 BG一定不是连通图CG中一定有回路 DG有二个连通分量16下列有关图遍历的说法不正确的是_。A连通图的深度优先搜索是一个递归过程 B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C非连通图不能用深
4、度优先搜索法 D图的遍历要求每一顶点仅被访问一次17下列说法中不正确的是_。A无向图中的极大连通子图称为连通分量 B连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D有向图的遍历不可采用广度优先搜索方法18一个有向图G的邻接表存储如下图7-1所示，现按深度优先搜索遍历，从顶点v1出发，所得到的顶点序列是_。Av1，v2，v3，v4，v5 Bv1，v2，v3，v5，v4Cv1，v2，v4，v5，v3 Dv1，v2，v5，v3，v4 234 35 5 4 v1v2v3v4 v5图7-1 一个有向图的邻接表19对图7-2所示的无向图，从
5、顶点1开始进行深度优先遍历，可得到顶点访问序列_。A1，2，4，3，5，7，6 B1，2，4，3，5，6，7C1，2，4，5，6，3，7 D1，2，3，4，5，7，61654327 图7-2 一个无向图20对图7-2所示的无向图，从顶点1开始进行广度优先遍历，可得到顶点访问序列_。A1，3，2，4，5，6，7 B1，2，4，3，5，6，7C1，2，3，4，5，7，6 D2，5，1，4，7，3，621一个无向连通图的生成树是含有该连通图的全部顶点的_。A极小连通子图 B极小子图C极大连通子图 D极大子图22设无向图 G=(V, E) 和G= (V, E)，如果 G为G的生成树，则下列说法中不正确
6、的是_。AG为G的连通分量 BG为G的无环子图CG为G的子图 DG为G的极小连通子图且VV23.任意一个无向连通图_最小生成树。A只有一棵 B有一棵或多棵C一定有多棵 D可能不存在24对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个_。A由n-1条权值最小的边构成的子图。 B由n-1条权值之和最小的边构成的子图。C由n-1条权值之和最小的边构成的连通子图。D由n个顶点构成的边的权值之和最小的生成树。25若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图_。A是个有根有向图 B是个强连通图C含有多个入度为0的顶点 D含有顶点数目大于1的强连通分量26判定一个有向图是否存在回路
7、除了可以利用拓扑排序方法外，还可以用_。A求关键路径的方法 B求最短路径的Dijkstra算法C广度优先遍历算法 D深度优先遍历算法27求最短路径的Dijkstra算法的时间复杂度为_。AO(n) BO(n+e)CO(n2) DO(ne)28求最短路径的Floyd算法的时间复杂度为_。AO(n) BO(ne)CO(n2) DO(n3) 29关键路径是事件结点网络中_。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长的回路 D最短的回路30下面说法不正确的是_。A在AOE网中，减少任一关键活动的权值后，整个工期也就相应减少BAOE网工程工期为关键活动的权值和C在关键路径上的活动都是关键活
8、动，而关键活动也必须在关键路径上DA和B31下面说法不正确的是_。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，将使整个工程提前完成C所有关键活动都提前完成，则整个工程提前完成D某些关键活动若提前完成，将使整个工程提前完成二、填空题1对于具有n个顶点的无向图G最多有_条边。2对于具有n个顶点的强连通有向图G至少有_条边。3对于具有n个顶点的有向图，每个顶点的度最大可达_。4若无向图G的顶点度数最小值大于_时，G至少有一条回路。5对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_，所有邻接表中的结点总数是_。6已知一个有向图的邻接矩阵表示，删
9、除所有从第i个结点出发的弧的方法是_。7对于n个顶点的无向图，采用邻接矩阵表示，求图中边数的方法是_，判断任意两个顶点i和j是否有边相连的方法是_，求任意一个顶点的度的方法是_。8对于n个顶点的有向图，采用邻接矩阵表示，求图中边数的方法是_，判断任意两个顶点i和j是否有边相连的方法是_，求任意一个顶点的度的方法是_。9无向图的连通分量是指_。 10已知图G的邻接表如图7-3所示，从顶点v1出发的深度优先搜索序列为_，从顶点1出发的广度优先搜索序列为_。v1v2v3v4 v5v6 234 35 6 4 63 图7-3 图G的邻接表11n个顶点连通图的生成树一定有_条边。12一个连通图的_是一个极
10、小连通子图。 13Prim算法适用于求_的网的最小生成树，Kruskal算法适用于求_的网的最小生成树。 14在AOV图中，顶点表示_,有向边表示_。15可以进行拓扑排序的有向图一定是_。16从源点到汇点长度最长的路径称为关键路径，该路径上的活动称为_。 17Dijkstra算法从源点到其它各顶点的路径长度按_次序依次产生，该算法在边上的权出现_情况时，不能正确产生最短路径。18求从某源点到其余各项点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则在图的顶点数为40时，计算时间约为_ms。三、判断题1具有n个顶点的无向图至多有n（n-1）条边。2有向图中各顶
11、点的入度之和等于各顶点的出度之和。3邻接矩阵只储存了边的信息，没有存储顶点的信息。4对同一个有向图，只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多。5如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。6如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是有向完全图。7如果表示某个图的邻接矩阵不是对称矩阵，则该图一定是有向图。8连通分量是无向图的极小连通子图。9强连通分量是有向图的极大连通子图。10对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每一个顶点，则该图一定是完全图。11连通图的广度优先搜索中一般要采用队列来暂时刚访问过的顶点。12图的深
12、度优先搜索中一般要采用栈来暂时刚访问过的顶点。13有向图的遍历不可采用广度优先搜索方法。14连通图的生成树包含了图中所有顶点。15设G为具有n个顶点的连通图，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。16最小生成树是指边数最小的生成树。17从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。18只要无向网中没有权值相同的边，其最小生成树就是惟一的。19只要无向网中有权值相同的边，其最小生成树就可能不是惟一的。20有环图也能进行拓扑排序。21拓扑排序算法仅适用于有向无环图。22任何有向无环图的结点都可以排成拓扑排序，而且拓扑序列不惟一。23关键路径是由权值
13、最大的边构成的。24在AOE网中，减小任一关键活动上的权值后，整个工期也就相应减小。25在AOE网中工程工期为关键活动上权值之和。26在关键路径的活动都是关键活动，而关键活动未必在关键路径上。27关键活动不按期完成就会影响整个工程的完成时间。28所有关键活动都提前完成，则整个工程将提前完成。29某些关键活动若提前完成，将可能使整个工程提前完成。30求单源最短路径的狄克斯特拉算法不适用于有回路的有向网。四、简答题1图G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？2用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？3对于稠密图和稀疏图，就存储而言，采用邻接矩阵
14、和邻接表哪个更好些？4请回答下列关于图的一些问题：（1）有n个顶点的有向强连通图最多有多少条边？最少有多少条边？（2）表示一个有1000个顶点，1000条边的有向图的邻接矩阵有多少个矩阵元素？是否为稀疏矩阵？（3）对于一个有向图，不用拓扑排序，如何判断图是否存在环？5对n个顶点的无向图和有向图，采用邻接表表示时，如何判别下列有关问题？（1）图中有多少条边？（2）任意两个顶点i和j是否有边相连？（3）任意一个顶点的度是多少？6给出如图7-4所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。12543图7-4 一个无向图7对于图
15、7-5所示的有向图，试给出：（1）邻接矩阵。 （2）邻接表 （3）强连通分量（4）对照邻接表，给出从顶点1出发的深度优先遍历序列。（5）对照邻接表，给出从顶点3出发的深度优先遍历序列。143256图7-5 一个有向图8什么样的图其最小生成树是惟一的？9已知带权连通图G(V,E)邻接表如图7-6所示，请画出该图，并分别以深度优先和广度优先遍历该图，写出遍历中结点的序列，并画出该图的一棵最小生成树，其中表结点的3个域各为：顶点号边上所带的权指针v1v2v3v4v54 4 4 18 5 22 5 10 1 161 122 12 1 182 223 163 22 23 44 10 1.2.34.5图7
16、-6 连通图的邻接表10已知世界6大城市为：北京（B）纽约（N）巴黎（P）伦敦（L）东京（T）墨西哥城（M）试用由表1给出的交通网确定最小生成树，并说明所使用的方法及其时间复杂度。BNPLTMB 109828121124N109585510832P825839792L815539589T211089795113M12432928911311对于图7-7所示的带权有向图，采用狄克斯特拉算法求从顶点1到其它顶点的最短路径，要求给出求解过程。39822 127153426512 12 15131344313204图7-7 一个有向图 图7-8一个有向图 12设图7-8中的顶点表示村庄，有向边代表交通
17、路线，若要建立一家医院，试问建在哪个村庄能使个村庄总体交通代价最小。13表2所示给出了某工程各工序之间的优先关系和各工序所需的时间。表2 某工程各工序关系表工序代号 A B C D E F G H I J K L M N所需时间 15 10 50 8 15 40 300 15 120 60 15 30 20 40先驱工作 - - A,B B C,D B E G,I E I F,I H,J,K L G完成如下各小题：（1）画出相应的AOE网（2）列出事件的最早发生时间，最迟发生时间。（3）找出关键路径并指明完成该工程所需的最短时间。14如图7-9所示的AOE网，求：（1）每项活动ai最早开始时间
18、e(ai)和最迟开始时间l(ai)。（2）完成此工程最少需要多少天（设边上权值为天数）。（3）哪些是关键活动a13=2a1=5a2=6a3=3a4=6a5=3a6=3a7=4a12=4a11=2a10=5a9=4a8=113425678910（4）是否存在某项活动，当其提高速度后能使整个工程缩短工期？图7-9五、算法设计题1假设图G采用邻接表存储，分别设计实现以下要求的算法：（1）求出图G中每个顶点的入度。（2）求出图G中每个顶点的出度（3）求出图G中出度最大的一个顶点，输出该顶点的编号。（4）计算图G中出度为0的顶点数。（5）判断图G中是否存在边。2假设图G采用邻接矩阵存储，分别设计实现以下
19、要求的算法：（1）求出图G中每个顶点的入度。（2）求出图G中每个顶点的出度（3）求出图G中出度最大的一个顶点，输出该顶点的编号。（4）计算图G中出度为0的顶点数。（5）判断图G中是否存在边。3设计一个将邻接表转换为邻接矩阵的算法。4一个连通图采用邻接表作为存储机构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。5设计一个算法，求不带权无向连通图G中距离顶点v的最远顶点。6设计一个算法，判断无向图G是否是一棵树，若是树，返回1；否则返回0。7假设图采用邻接表存储，分别写出基于DFS和BPS遍历的算法来判别顶点i和顶点j（i!=j）之间是否有路径。8假设图G采用邻接表存储，设计一个算法，
20、判断无向图G是否连通，若连通则返回1；否则返回0。9假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的长度为1的所有简单路径。10假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。11假设图G采用邻接表存储，设计一个算法，从如图7-10所示的无向图G中找出满足如下条件的一条路径：（1）给定起点vi和终点vj。（2）给定一组必经点7,9，即输出的路径必须包含这些顶点。（3）给定一组必避点1,6，即输出的路径不能包含这些顶点。01234567891011121314图7-1012假设图G采用邻接矩阵存储，采用遍历方法实际一个有向图的根的算法。若有向图中存在一个
21、顶点v，从v可以通过路径达达图中其它所有顶点，则称v为该有向图的根。13假设图G采用邻接矩阵存储，设计一个算法判断在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方法输出该回路（找到一条即可）。14采用堆排序来实现Kruskal算法，并说明时间复杂度O(elog2e)的理由。15如图7-11是一个城市连接图，图中权值表示两城市之间的里程（单位为100km），现要设计一条铁路贯通所有城市（即从一个任一城市可以到达其他城市）。设计一个算法，求出最小代价。假设每1km的铁路造价为1000万元。6364255651103452图7-11 城市连通图16利用狄克斯特拉算法，设计一个可产生
22、从指定顶点出发的最小生成树的算法。17设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX从w到v的最短距离|wV(G)如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。18假设图G采用邻接矩阵存储，采用弗洛伊德算法设计一个求有向图的根的算法。若有向图中存在一个顶点v，从v可以通过路径到达图中其他所有顶点，则称v为该有向图的根。19设计一个算法，判断有向图是否存在回路。20对于一个使用邻接表存储的带权有向图G。试利用深度优先搜索方法，对该图中所有顶点进行逆向拓扑排序。若邻接表的数据类型定义为AGraph，则算法的首部为：void dfs_topsort(AGraph *G) 若拓扑排序成功，表示图中不存在环；否则表示图中存在环。在这个算法中嵌套一个递归深度优先搜索算法为：Dfs(AGaph G , int v)在遍历图的同时进行逆序拓扑排序，其中，v是顶点编号。（1）给出该图的邻接表定义（2）定义在算法中使用的全局辅助数组（3）写出逆向拓扑排序的算法。21假设AOE网以邻接表方式存储，设计一个算法求该AOE网的所有关键活动。