数据结构第七节习题课.doc

1、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（ ）。 A、求关键路径的方法 B、求最短路径的Dijkstra方法 C、宽度优先遍历算法 D、深度优先遍历算法 2．图中有关路径的定义是（ ）。 由顶点和相邻顶点序偶构成的边所形成的序列 由不同顶点所形成的序列 由不同边所形成的序列 上述定义都不是 3．一个n个顶点的连通无向图，其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 4．当一个有N个顶点的无向图用邻接矩阵A表示时，顶点Vi的度是（ ）。 A． B． C． D．+ 5. 下列说法不正确的是（ ）。 图的遍历是从给定的源点出发每一个顶点仅被访问一次 遍历的基本算法有两种：深度遍历和广度遍历 图的深度遍历不适用于有向图 图的深度遍历是一个递归过程 6．无向图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 7. 设图如右所示，在下面的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个 8. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 9．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（ ）。 A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 10．若一个有向图的邻接矩阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ ）。 A．存在 B．不存在 11．一个有向无环图的拓扑排序序列（ ）是唯一的。 A．一定 B．不一定 12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 A．G中有弧Vi，Vj B．G中有一条从Vi到Vj的路径 C．G中没有弧Vi,Vj D．G中有一条从Vj到Vi的路径 13．下列关于AOE网的叙述中，不正确的是（ ）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 14.判断一个无向图是一棵树的条件是______。 答：有n个顶点，n-1条边的无向连通图 15．有向图G的强连通分量是指______。 答：有向图的极大强连通子图 16. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1=i=n），则e=______ 答：（d1+d2+……+dn）/2(3) 33．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。 34．G=(V,E)是一个带有权的连通图,则： （1）．请回答什么是G的最小生成树； （2）．G为下图所示,请找出G的所有最小生成树。 35．一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。 36．请看下边的无向加权图。 （1）．写出它的邻接矩阵 （2）．按Prim算法求其最小生成树，并给出构造最小生成树过程中辅助数组的各分量值。