数据结构第六章参考答案.doc

习题6 填空题 （1）n个顶点的无向图，最多能有（___________）条边。 答案： [n* n-1 ]/2 （2）有n个顶点的强连通图G最多有（___________）条弧。 答案：n* n-1 （3）有n个顶点的强连通图G至少有（___________）条弧。 答案：n （4）G为无向图，如果从G的某个顶点出发，进行一次广度优先遍历，即可访问图的每个顶点，则该图一定是（___________）图。 答案：连通 （5）若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为（___________）。 答案：O（n2） （6）n个顶点的连通图的生成树有（___________）条边。 答案：n-1 （7）图的深度优先遍历类似于树的（___________）遍历；图的广度优先遍历类似于树的（___________）遍历。 答案：前序 层序 （8）对于含有n个顶点e条边的连通图，用普里姆算法求最小生成树的时间复杂度为（___________）。 答案：O（n2） （9）已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（___________）。 答案：O（n+e） （10）一棵具有n个顶点的生成树有且仅有（___________）条边。 答案：n-1 单选题 （1）在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A. 1/2 B. 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）若一个图中包含有k个连通分量，若按照深度优先有哪些信誉好的足球投注网站的方法访问所有顶点，则必须调用（ ）次深度优先有哪些信誉好的足球投注网站遍历的算法。 A. k B. 1 C. k-1 D. k+1 （5）若一个图的边集为 1，2 ， 1，4 ， 2，5 ， 3，1 ， 3，5 ， 4，3 ，则从顶点1开始对该图进行深度优先遍历，得到的顶点序列可能为（ ）。 A. 1，2，5，4，3 B. 1，2，3，4，5 C. 1，2，5，3，4 D. 1，4，3，2，5 （6）若一个图的边集为 （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是正确的。 （7）存储无向图的邻接矩阵是（ A ），存储有向图的邻接矩阵是（ B ）。 A. 对称的 B. 非对称的 （8）采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 （9）设有一个无向图G＝（V，E）和G′＝（V′，E′），如果G′为G的生成树，则下面不正确的说法是（ ）。 A. G′为G的子图 B. G′为G的连通分量 C. G′为G的极小连通子图，且V＝V D. G′为G的一个无环子图 画出图6－32所示的无向图的邻接表（顶点由小到大排列），并根据所得邻接表给出深度优先和广度优先有哪些信誉好的足球投注网站遍历该图所有的顶点序列。 答案： 深度优先：ABCDEFGH 广度优先：ABHCGFDE 使用普里姆算法构造出图6－33中图G的一棵最小生成树。 答案：生成最小树的顺序如下