图练习题.docVIP

第七章 图 7.1、(画出图1的存储结构(1)邻接矩阵(2)邻接表(3)逆邻接表(4)十字链表(5)邻接多重表。 7.2、(在图1中，从顶点A出发深度优先有哪些信誉好的足球投注网站得（__），从B出发广度优先有哪些信誉好的足球投注网站得（__）。在图2中从顶点A出发深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站分别得（__）和（__）。 7.3、(对图2进行拓扑排序得（__）。 7.4、(用普里姆算法计算图3的最小生成树（写出过程）。 7.5、(用克鲁斯卡尔算法计算图3的最小生成树。计算该生成树的代价。 7.6、(设图4为某工程的AOE网，弧上的权值表示活动(i,j)所用的时间（天）。问：整个工程需要多少天才能完成？请计算工程中的关键路径。 7.7、(用迪杰斯特拉算法计算图3和图5中顶点A到其他各顶点的最短路径（写出过程）。 7.8、(用弗洛伊德算法计算图5中各个顶点之间的最短路径。 （本题满分为10分）试利用Dijkstra算法求下图中从顶点1到其它各顶点间的最短路径，写出执行算法过程中各步的状态。 已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是求矩阵第i列非零元的个数。 ( ) （本题10分）下面画出了一个AOE网表示各工序之间的优先关系和各工序所需时间，要求： 1. 列出各事件的最早最迟发生时间 2. 求出该AOE网中的关键路径，及完成该工程所需要的最短时间。 写出求从某个源点到其余各顶点最短路径的Dijkstra算法。要求说明主要的数据结构及其作用，最后针对所给有向图，利用该算法，求V0到各顶点的最短距离和路线，即填写下表： 终点 从V0到到各终点的dist的值和最短距离和路线 V1 V2 V3 V4 V5 Vj V2 V3 V4 V5 一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。A．0 B．1 C．n-1 D．n 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。 A．1/2 B．2 C．1 D．4 从邻接矩阵 可以看出，该图共有（）个顶点；如果是有向图该图共有（） 条弧；如果是无向图，则共有（）条边。 下列说法不正确的是（ ）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．图的深度遍历不适用于有向图 C．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 G中有弧Vi，Vj B．G中有一条从Vi到Vj的路径 C．G中没有弧Vi,Vj D．G中有一条从Vj到Vi的路径 关键路径是事件结点网络中（ ）。 从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 下列关于AOE网的叙述中，不正确的是（）。 关键活动不按期完成就会影响整个工程的完成时间 任何一个关键活动提前完成，那么整个工程将会提前完成 所有的关键活动提前完成，那么整个工程将会提前完成 某些关键活动提前完成，那么整个工程将会提前完成 （1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？ （2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？ A B C D E 图1 A B C D E 图2 A B C D E 图3 F 4 3 2 4 1 2 4 1 3 3 A B E C F D G 图4 4 2 1 6 3 5 2 3 4 2 A B C D E 2 1 4 5 3 4 2 图5 5 2 1 3 4 6 10 10 15 4 30 4 10 15 2 20 1 3 2 4 6 5 9 10 7 8 11 10 15 8 40 15 30 20 15 300 15 50 120 60