习题12(图的应用)

习题12（图的应用）一、选择题1、下面（B）方法可以判断出一个有向图是否有环。A）深度优先遍历B）拓扑排序C）求最短路径D）求关键路径2、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为（C）A）O(n)B）O(n＋e)C）O(n*n)D）O(n*n*n)3、在用邻接表表示图时，拓扑排序算法时间复杂度为（B）A）O(n)B）O(n＋e)C）O(n*n)D）O(n*n*n)4、求解最短路径的Floyd算法的时间复杂度为（D）A）O(n)B）O(n＋e)C）O(n*n)D）O(n*n*n)5、下面（A）算法适合构造一个稠密图G的最小生成树。A）Prim算法B）Kruskal算法C）Floyd算法D）Dijkstra算法6、最小生成树指的是（C）A）由连通网所得到的边数最少的生成树B）由连通网所得到的顶点相对较少的生成树C）连通网中所有生成树中权值之和为最小的树D）连通网的极小连通子图7、关键路径是事件结点网络中（A）A）从源点到汇点的最长路径B）从源点到汇点的最短路径C）最长回路D）最短回路8、下列关于AOE网的叙述中，不正确的是（B）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成9、求图中一个顶点到其它各个顶点最短路径的算法是（C）A）Kruskal算法B）Prim算法C）Dijkstra算法D）Floyd算法10、下面关于求关键路径的说法不正确的是（C）A）求关键路径是以拓扑排序为基础的B）事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C）事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D）关键活动一定位于关键路径上11、下面叙述中不正确的是（D）(1)求源点到其余顶点的Dijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2)利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3)；（图用邻接矩阵表示）(3)Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。A）(1),(2),(3)B）(1)C）(1),(3)D）(2),(3)12、已知有向图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）A）V1V3V4V6V2V5V7B）V1V3V2V6V4V5V7C）V1V3V4V5V2V6V7D）V1V2V5V3V4V6V713、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）A）存在弧Vi，VjB）有一条从Vi到Vj的路径C）不存在弧Vi,VjD）有一条从Vj到Vi的路径14、下面关于有向图的运算的叙述中，哪个（些）是正确的（D）Ⅰ.求有向图结点的拓扑序列，其结果必定是惟一的。Ⅱ.求两个指定结点间的最短路径，其结果必定是惟一的。Ⅲ.求事件结点网络的关键路径，其结果必定是惟一的。A）只有ⅠB）Ⅰ和ⅡC）都正确D）都不正确二、填空题1、Prim算法的时间复杂度是（o(n*n)），适用于求（稠密）图的最小生成树；kruskal算法的时间复杂度是（O（eloge）），适用于求（稀疏）图的最小生成树。2、实现构造最小生成树的Prim算法需附设一个（辅助数组），用来记录（从U到v-u具体最小代价的边），在（辅助数组）中存在一个分量，它包括（2）个域。3、拓扑排序是从每个集合上的一个（偏序）得到该集合上的一个（全序）。4、有向图G可拓扑排序的判别条件是（不存在环）。5、设有向图有n个顶点和e条边，进行拓扑排序时，时间复杂度为（O（n+e））。6、已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={V1，V2，V1，V3，V3，V2，V2，V4，V3，V4}，图G的拓扑序列是（V1，V3，V2，V4）。7、AOE网为边表示活动的网，是一个带权的（有向无环图），其长度最长的路径称为（关键路径）。8、在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为（关键路径）。9、AOV网中,结点表示（活动）,边表示（活动时间的优先关系）。AOE网中,结点表示（事件）,边表示（活动）。10、在AOV网中，存在环意味着（某项活动应以自己为先决条件），这是（荒谬）的；对程序的数据流图来说，它表明存在（死循环）。11、求最短路径的Dijkstra算法的时间复杂度为（O(n*n)）。12、Dijkstra提出的求最短路径方法，引进一个辅助向量dist，它的每个分量dist[I]表示当前所找到的从（源点）到每个（终点）的最短路径的（长度）。13、求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为（160）ms。14、Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按（严格递增）次序依次产生，该算法弧上的权出现（权值为负）情况时，不能正确产生最短路径。三、应用题1、利用Dijkstra算法求图1中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。2、对图2所示的AOE-网，求每个活动的最早开始时间和最迟开始时间，并确定关键活动及整个工程的最早结束时间。图1图23、按Kruthkal算法写出求图3最小生成树的过程。按Prim算法写出求图4最小生成树的过程。图3图44、求出图5中顶点1到其余各顶点的最短路径长度，写出所有拓扑有序序列，并指出应用拓扑排序算法得到的是哪一个？5、求出图6所示AOE网的关键路径（要求写出各条弧代表的活动的最早、最迟开始时间）。图5图66、下表给出了某工程各工序之间的优先关系和各工序所需时间。（1）画出相应的AOE网。（2）列出各事件的最早发生时间，最迟发生时间。（3）找出关键路径并指明完成该工程所需最短时间。7、下图是带权的有向图G的邻接表表示法，其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。求：（1）以V1出发深度遍历图所得结点序列；（2）以V1出发广度遍历图所得结点序列；（3）从V1到V8的最短路径；（4）从V1到V8的关键路径；（7）写出至少2个拓扑序列。四、算法设计题2、设计算法，求出无向连通图中距离顶点V0的最短路径长度（最短路径长度以边数为单位计算）为K的所有的结点，要求尽可能地节省时间。5、有向图G采用邻接表存储结构，试编写一算法判断图G是否存在回路，若存在回路，则输出“Error”的信息，否则输出“OK”的信息，并输出图G的一个拓扑序列。工序代号ABCDEFGHIJKLMN所需时间15105081540300151206015302040先驱工作----A，BBC,DBEGEIFH,J,KL,NG