第七章图练习题

7．对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为()，利用Kruskal时间复杂度为()。(A)O(1og2n)(B)O(n2)(C)O(ne)(D)O(elog2e)8．具有n个顶点的完全有向图的边数为()。(A)n(n一1)／2(D)n(n—1)(C)n2(D)n2-12．有向图G用邻接矩阵A{l…n，1…n}存储，其第i列的所有元素等于顶点i的______________。3．对于下图，试给出(1)每个顶点的入度和出度(2)邻接矩阵，(3)逆邻接表；(4)强连通分量。3．设汁一个算法，建立无向图(n个顶点，e条边)的邻接表。8．对下图v4的度为()。(A)1(B)2(C)3(D)47．有向图G用邻接矩阵A[1…m，1…m]存储，其第i行的所有元素值之和等于顶点vi的__________________。1．n个顶点的无向图的邻接表中结点总数最多有()个。(A)2n〔B)n(C)n/2(D)n(n-1)2．设连通图G的顶点数为n，则G的生成树的边数为()(A)n(B)n一1(C)2n(D)2n-16．连通分量是无向图中的极小连通子图。()6．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。()7．一个无向连通图有5个顶点8条边，则其生成树将要去掉()条边。(A)3(B)4(C)5(D)62．如果某有向图的所有顶点可以构成一个拓扑排序，则说明有向图存在回路。()8．一个图可以没有边，但不能没有顶点。()3．已知下图是一个有向图。(1)画出该有向图的邻接矩阵。(5分)(2)基于你给出的邻接矩阵，求从顶点6出发的深度优先遍历。(5分)4．有向图的邻接矩阵的第i行的所有元素之和等于第i列的所有元素之和。（）6．图的生成树的边数应小于顶点数。()3．一个无向连通图有6个顶点7条边，则其生成树有_____________条边。8．设无向图G有100条边，则G至少有_____________个顶点。4．已知下图是一个无向团。(1)画出该无向图的邻接链表。(5分)(2)基于你给出的邻接链表，求从顶点C出发的广度优先遍历。(5分)3．一个n个顶点的连通无向图，其边的个数至少为()。(A)n-1(B)n(C)n+1(D)Onlogn4．如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图__________。7．无向图用邻接矩阵存储，其所有元素之和表示无向图的__________。3．已知下图是一个有向图。(1)画出该有向图的邻接链表。(4分)(2)基于你给出的邻接链表，求从顶点5／出发的广度优先温历。(4分)4．用Prim算法(一条顶点一条顶点加入生成树)求下图的最小生成树。(1)从顶点D开始，写出各顶点加人生成树的次序。(4分)(2)画出最终的最小生成树。(4分)4．已知左下图是一个无向图。(1)画出该无向图的邻接矩阵。(5分)(2)基于你给出的邻接矩阵，求从顶点A出发的深度优先遍历。(4分)5．用Kruskal算法(一条边一条边地加入生成树)求右下图的最小生成树。(1)写出各条边加入生成树的次序(用权值表示)。(5分)(2)画出最终的最小生成树。(4分)2．己知一带权有向图的邻接矩阵表示如下，试画出其逻辑图。3．已知一有向图如下图所示，试画出从A点出发的深度优先生成树。4．以(1，3，6，7，9，15，22)为权值，构造一棵Huffman树，并求出其WPL。课后习题：一、单项选择题1、一个n个顶点的无向图最多有________条边。（A）n（B）n(n-1)（C）n(n-1)/2（D）2n2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_________倍。（A）1/2（B）1（C）2（D）43、关键路径是事件结点网络中__________。（A）从源点到汇点的最长路径（B）最长的回路（C）从源点到汇点的最短路径（D）最短的回路4、下面不正确的说法是__________。A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，将使整个工程提前完成C、所有关键活动都提前，则整个工程提前完成D、某些关键活动若提前完成，将使整个工程提前完成。二、填空题1、一个图的表示法是惟一的，而表示法是不惟一的。2、在有n个顶点的有向图中，每个顶点的度最大可达。三、计算题1、设有向图G如下图所示，试给出：（1）该图的邻接矩阵；（2）该图的邻接表；（3）从V1出发的“深度优先”遍历序列；（4）从V1出发的“广度优先”遍历序列。V1V2V4V5V3V7V6V82、对下图的AOE网，求出：（1）每个事件的最早发生时间和最迟发生时间；（2）每个活动的最早开始时间和最迟开始时间；（3）画出关键活动组成的图。对哪些活动提速，可使整个工期提前。987645321a6=2