下面步骤重复n-1次:a:(2):b:(3):最后:(4)。【南京理工大学1997一、1114 (8分)】 (1).A.VT,ET为空 B.ⅥT为所有顶点,ET为空 C.ⅥT为网中任意一点,ET为空 VT为空,ET为网中所有边 (2).A.选i属于ⅥT,j不属于ⅥT,且(i,j)上的权最小 B.选i属于ⅥT,j不属于ⅥT,且(i,j)上的权最大 C.选i不属于ⅥT,j不属于Ⅵ,且(i,j)上的权最小 D.选i不属于ⅥT,j不属于ⅥT,且(i,j)上的权最大 (3).A.顶点i加入ⅥT,(i,j)加入ET B.顶点j加入ⅥT,(i,j)加入ET C.顶点j加入ⅥT,(i,j)从ET中删去D.顶点i,j加入ⅥT,(i,j)加入 (4).A.ET中为最小生成树 B.不在ET中的边构成最小生成树 C.ET中有n-1条边时为生成树,否则无解D.ET中无回路时,为生成树,否 则无解 22.(1).求从指定源点到其余各顶点的迪杰斯特拉( Di jkstra)最短路径算法中弧上权不 能为负的原因是在实际应用中无意义 (2).利用 Di jkstra求每一对不同顶点之间的最短路径的算法时间是0(m);(图用邻 接矩阵表示) (3). Floyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。 上面不正确的是()。【南京理工大学2000一、21(1.5分)】 B.(1 C.(1),(3) D.(2),(3) 23.当各边上的权值()时,BFS算法可用来解决单源最短路径问题。【中科院计算所2000 3(2分)】 A.均相等B.均互不相等C.不一定相等 24.求解最短路径的 Floyd算法的时间复杂度为()。【合肥工业大学1999一、2(2 分)】 A.0(n) B.0(n+c) C.0(n*n) 25.已知有向图G=(V,E),其中V={V1,V2,V3,V4,V3,V,V}, E={V1,V2>,<V1,V3>,<V,V4>,<V2,V5,<V3,V3>,<V3,V>,<V,V>,<V5,Vz>,<V,V2>},G的拓扑序列 是()。 A. V1, V3, V4, V6, V2, V5, V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V,V4,V,V2,V6,V7 D. V, V2, V5, V3, V4, V6, V7 【北京航空航天大学2000一、7(2分)】 26.若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 A.存在B.不存在【中科院计算所1998二、6(2分)】【中国科技大学1998二、6 (2分)】 27.一个有向无环图的拓扑排序序列()是唯一的。【北京邮电大学2001一、3(2 分)】 定 28.在有向图G的拓扑序列中,若顶点i在顶点Vj之前,则下列情形不可能出现的是 ()。 A.G中有弧<Vi,Vj B.G中有一条从Vi到Vj的路径 C.G中没有弧<Vi,Vj D.G中有一条从Vj到Vi的路径下面步骤重复 n-1 次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。【南京理工大学 1997 一、11_14 （8 分）】 （1）．A．VT，ET 为空 B．VT 为所有顶点，ET 为空 C．VT 为网中任意一点，ET 为空 D．VT 为空，ET 为网中所有边 （2）．A. 选 i 属于 VT，j 不属于 VT，且（i，j）上的权最小 B．选 i 属于 VT，j 不属于 VT，且（i，j）上的权最大 C．选 i 不属于 VT，j 不属于 VT，且（i，j）上的权最小 D．选 i 不属于 VT，j 不属于 VT，且（i，j）上的权最大 （3）．A．顶点 i 加入 VT，（i,j）加入 ET B. 顶点 j 加入 VT，（i,j）加入 ET C. 顶点 j 加入 VT，（i,j）从 ET 中删去 D．顶点 i,j 加入 VT，（i,j）加入 ET （4）．A．ET 中为最小生成树 B．不在 ET 中的边构成最小生成树 C．ET 中有 n-1 条边时为生成树，否则无解 D．ET 中无回路时，为生成树，否 则无解 22. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不 能为负的原因是在实际应用中无意义； (2). 利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n3 ) ；（图用邻 接矩阵表示） (3). Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。 上面不正确的是（ ）。【南京理工大学 2000 一、21 （1.5 分）】 A．(1),(2),(3) B．(1) C．(1),(3) D．(2),(3) 23．当各边上的权值( )时，BFS 算法可用来解决单源最短路径问题。【中科院计算所 2000 一、3 (2 分）】 A．均相等 B．均互不相等 C．不一定相等 24. 求解最短路径的 Floyd 算法的时间复杂度为( )。【合肥工业大学 1999 一、2 （2 分）】 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 25．已知有向图 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 【北京航空航天大学 2000 一、7 （2 分）】 26．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 （ ）。 A．存在 B．不存在【中科院计算所 1998 二、6 (2 分）】【中国科技大学 1998 二、6 （2 分）】 27．一个有向无环图的拓扑排序序列（ ）是唯一的。【北京邮电大学 2001 一、3 （2 分）】 A．一定 B．不一定 28. 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是 （ ）。 A．G 中有弧<Vi，Vj> B．G 中有一条从 Vi 到 Vj 的路径 C．G 中没有弧<Vi,Vj> D．G 中有一条从 Vj 到 Vi 的路径