习题 51．填空题(1）n 个顶点的无向图，最多能有(___________)条边.答案： ［n＊（n—1)］/2(2）有 n 个顶点的强连通图 G 至少有（___________）条弧。答案：n（3）G 为无向图，假如从 G 的某个顶点出发，进行一次广度优先遍历，即可访问图的每个顶点，则该图一定是（___________）图.答案：连通（4)若采纳邻接矩阵结构存储具有 n 个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为（___________）.答案：O（n2）(5）n 个顶点的连通图的生成树有（___________)条边.答案：n—1（6）图的深度优先遍历类似于树的（___________)遍历；图的广度优先遍历类似于树的(___________)遍历.答案:前序 层序（7）对于含有 n 个顶点 e 条边的连通图,用普里姆算法求最小生成树的时间复杂度为（___________）。答案：O（n2）（8）已知无向图 G 的顶点数为 n，边数为 e，其邻接表表示的空间复杂度为（___________）.答案:O（n+e)（9）一棵具有 n 个顶点的生成树有且仅有（___________）条边。答案：n—12．单选题（1）在一个无向图中,所有顶点的度数之和等于所有边数的（ ）倍。A。 1/2B. 1 C. 2 D。 4(2)在一个具有 n 个顶点的有向图中,若所有顶点的出度数之和为 S，则所有顶点的度数之和为( ）。A. S B. S－1 C. S+1 D。 2S(3）具有 n 个顶点的有向图最多有（ ）条边。A. n B。 n（n-1) C. n(n+1） D. 2n（4）在一个无向图中，所有顶点的度数之和等于所有边数的( ）倍。A.3 B.2 C。1 D.1/2（5)若一个图中包含有 k 个连通重量,若根据深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。A. k B. 1 C. k—1 D。 k+1（6）若一个图的边集为｛<1，2〉，<1，4〉,〈2，5>，〈3，1>,<3，5〉，〈4,3>｝，则从顶点 1 开始对该图进行深度优先遍历，得到的顶点序列可能为（ ）。A。 1，2，5，4,3 B。 1，2，3，4，5C. 1，2，5，3，4 D。 1，4,3，2,5(7）若一个图的边集为｛（A，B），（A，C），(B，D），（C,F）,（D,E）,（D,F）｝，则从顶点 A 开始对该图进行广度优先遍历，得到的顶点序列可能是( ）。A。 A,B,C,D，E,F B. A，B,C，F，D,E C. A，B，D，C，E，F D。 A,C，B，F，D，E说明:教材中某结点的邻接点选择次序默认都是自小而大，假如按此进行广度优先遍历，则结果应该为ABCDFE，但题目问可能的序列，则邻接点选择次序可以随便确定,此时，D 是正确...
