七图练习题.docVIP

7．对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )，利用Kruskal时间复杂度为( )。 (A)O(1og2n) (B)O(n2) (C)O(ne) (D)O(e log2 e) 8．具有n个顶点的完全有向图的边数为( )。 (A)n(n一1)／2 (D)n(n—1) (C)n2 (D) n2 -1 2．有向图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)4 7．有向图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-1 6．连通分量是无向图中的极小连通子图。( ) 6．用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。( ) 7．一个无向连通图有5个顶点8条边，则其生成树将要去掉( )条边。 (A)3 (B)4 (C)5 (D)6 2．如果某有向图的所有顶点可以构成一个拓扑排序，则说明有向图存在回路。( ) 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)O n log n 4．如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图__________。 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） 2n 2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_________倍。 （A）1/2 （B）1 （C）2 （D）4 3、关键路径是事件结点网络中 __________ 。 （A）从源点到汇点的最长路径 （B）最长的回路 （C）从源点到汇点的最短路径 （D）最短的回路 4、下面不正确的说法是_____