第5课图.doc

第五课 图 一、选择题 1．图中有关路径的定义是（ ）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 参考答案：A 2．设无向图的顶点个数为n，则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 参考答案：B 3．一个n个顶点的连通无向图，其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn 参考答案：A 4．要连通具有n个顶点的有向图，至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 参考答案：B 5．n个结点的完全有向图含有边的数目（　　）。 A．n*n Ｂ．n（n+1） C．n／2 D．n*（n-1） 参考答案：D 6．一个有n个结点的图，最少有（ ）个连通分量。 A．0 B．1 C．n-1 D．n 参考答案：B 7．一个有n个结点的图，最多有（ ）个连通分量。 A．0 B．1 C．n-1 D．n 参考答案：D 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为（　　）。 A．5 B．6 C．8 D．9 参考答案：A 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（　　）。 A．逆拓扑有序 B．拓扑有序 C．无序的 参考答案：A 10．下面结构中最适于表示稀疏无向图的是（ ）。 A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表 参考答案：C 11．下列哪一种图的邻接矩阵是对称矩阵？（ ） A．有向图 B．无向图 C．AOV网 D．AOE网 参考答案：B 12．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ ）。 A． B． C． D．+ 参考答案：B 13．下列说法不正确的是（ ）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 参考答案：C 14．无向图G=(V,E),其中： V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 参考答案：D 15．设图如右所示，，在下面的5个序列中，符合深度优先遍历的序列有（ ）个。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A．5个 B．4个 C．3个 D．2个 参考答案：D 16．下列方法中可以判断出一个有向图是否有环（回路）的是（　　）。 A．广度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 参考答案：B 17．在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（　　）。 A．O(n) B．O(n+e) C．O(n2) D．O(n3) 参考答案：B 18．当各边上的权值（　　）时，BFS算法可用来解决单源最短路径问题。 A．均相等 B．均互不相等 C．不一定相等 参考答案：A 19．求解最短路径的Floyd算法的时间复杂度为（　　）。 A．O（n） B．O（n+c） C．O（n*n） D．O（n*n*n） 参考答案：D 20．已知有向图G=(V,E)，其中