28.Prim(普里姆)算法适用于求 的网的最小生成树; kruskal(克鲁斯卡尔)算法 适用于求的网的最小生成树。【厦门大学1999一、4】 29.克鲁斯卡尔算法的时间复杂度为 它对图较为适合。【中科院计算所1999 、3(2分)】 对于含N个顶点E条边的无向连通图,利用Prim算法生成最小代价生成树其时间复杂 度为 利用 Kruskal算法生成最小代价生成树其时间复杂度为 【长沙铁道学 院1998二、2(4分)】 31.下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个节点 Ⅵ1,V2,,Ⅶn,用相邻矩阵A表示,边的权全是正数。请在下列划线处填上正确叙述 (1).若(Vi,Vj)是边,则A(i,j)的值等于,若(Vi,Vj)不是边,则A(i, j)的值是一个比任何边的权 矩阵的对角线元素全为 (2).构造最小生成树过程中,若节点Vi已包括进生成树,就把相邻矩阵的对角线元素 A(i,i)置成 若(vi,Vj)已包括进生成树,就把矩阵元素A(i,j)置成 (3).算法结束时,相邻矩阵中的元素指出最小生成树的【山东工业大学1998 二、4(6分)】 32.有一个用于n个顶点连通带权无向图的算法描述如下: (1).设集合T1与T2,初始均为空; (2).在连通图上任选一点加入T1: (3).以下步骤重复n-1次: a.在i属于T1,j不属于T1的边中选最小权的边 b.该边加入T2 上述算法完成后,T2中共有条边,该算法称算法,T2中的边构成图的。 【南京理工大学1999二、7(4分)】 有向图G可拓扑排序的判别条件是 【长沙铁道学院1998二、9(2分)】 34. Di jkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按 次序依次 产生,该算法弧上的权出现情况时,不能正确产生最短路径。【南京理工大学1999二、 8(4分)】 35.求从某源点到其余各顶点的 Di jkstra算法在图的顶点数为10,用邻接矩阵表示图时计 算时间约为10ms,则在图的顶点数为40,计算时间约为ms。【南京理工大学2000二、 分)】 6.求最短路径的 Dijkstra算法的时间复杂度为【哈尔滨工业大学2001-、5(2 分)】 37.有向图G=(V,E),其中VG)={0,1,2,3,4,5},用<a,b,d>三元组表示弧<a,b>及弧上的权 d.E(G)为{<0,5,100),<0,2,10〉<1,2,5><0,4,30)<4,5,60〉<3,5,10)<2,3,50)<4,3,20)》},则 从源点0到顶点3的最短路径长度是_,经过的中间顶点是【南京理工大学1998 三、6(4分)】 38.上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为 【南京理工大学1998三、7(4分)】 9.设有向图有n个顶点和e条边,进行拓扑排序时,总的计算时间为 【西安电子科技大学1999软件一、7(2分)】【武汉大学2000一、7】 40.AOV网中,结点表示 边表示 。AOE网中,结点表示 边表示 【北京理工大学2001七、3(2分)】 41.在AOE网中,从源点到汇点路径上各活动时间总和最长的路径称为。【重庆大学 200028. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法 适用于求______的网的最小生成树。【厦门大学 1999 一、4】 29．克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。【中科院计算所 1999 二、3 （2 分）】 30．对于含 N 个顶点 E 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂 度为______，利用 Kruskal 算法生成最小代价生成树其时间复杂度为______。【长沙铁道学 院 1998 二、2 (4 分)】 31．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括 n 个节点 V1，V2，．．．，Vn，用相邻矩阵 A 表示，边的权全是正数。请在下列划线处填上正确叙述。 （1）．若（Vi，Vj）是边，则 A（i，j）的值等于______，若（Vi，Vj）不是边，则 A（i， j）的值是一个比任何边的权______， 矩阵的对角线元素全为 0。 （2）．构造最小生成树过程中，若节点 Vi 已包括进生成树，就把相邻矩阵的对角线元素 A（i，i）置成______，若（Vi，Vj）已包括进生成树，就把矩阵元素 A（i，j）置成______。 （3）．算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。【山东工业大学 1998 二、4(6 分）】 32. 有一个用于 n 个顶点连通带权无向图的算法描述如下： （1）．设集合 T1 与 T2，初始均为空； （2）．在连通图上任选一点加入 T1； （3）．以下步骤重复 n-1 次： a.在 i 属于 T1，j 不属于 T1 的边中选最小权的边； b.该边加入 T2。 上述算法完成后，T2 中共有______条边，该算法称______算法，T2 中的边构成图的______。 【南京理工大学 1999 二、7 （4 分）】 33. 有向图 G 可拓扑排序的判别条件是______。【长沙铁道学院 1998 二、9(2 分)】 34. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按______次序依次 产生，该算法弧上的权出现______情况时，不能正确产生最短路径。【南京理工大学 1999 二、 8（4 分）】 35. 求从某源点到其余各顶点的 Dijkstra 算法在图的顶点数为 10，用邻接矩阵表示图时计 算时间约为 10ms,则在图的顶点数为 40，计算时间约为______ms。【南京理工大学 2000 二、 3 （1.5 分）】 36．求最短路径的 Dijkstra 算法的时间复杂度为______。【哈尔滨工业大学 2001 一、5 （2 分）】 37.有向图 G=(V,E),其中 V(G)={0,1,2,3,4,5}，用<a,b,d>三元组表示弧<a,b>及弧上的权 d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则 从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。【南京理工大学 1998 三、6 （4 分）】 38. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为______。 【南京理工大学 1998 三、7（4 分）】 39．设有向图有 n 个顶点和 e 条边，进行拓扑排序时，总的计算时间为______。 【西安电子科技大学 1999 软件 一、7 （2 分）】【武汉大学 2000 一、7】 40．AOV 网中,结点表示______,边表示______。AOE 网中,结点表示______,边表示______。 【北京理工大学 2001 七、3 （2 分）】 41．在 AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为______。【重庆大学 2000 一、2】