（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={1,v2>,1,v3>,1,v4>,2,v5>,3,v5>,3,v6>,4,v6>,5,v7>,6,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中有弧，vj>             b．g中有一条从vi到vj的路径                                               
c．g中没有弧            d．g中有一条从vj到vi的路径   
【南京理工大学 2000 一、9 （1.5分）】 
29. 在用邻接表表示图时，拓扑排序算法时间复杂度为(    )。
a. o(n)         b. o(n＋e)       c. o(n*n)      d. o(n*n*n) 
【合肥工业大学 2000 一、2 （2分）】【南京理工大学 2001 一、9 （1.5分）】
【青岛大学 2002 二、3 （2分）】
30. 关键路径是事件结点网络中（    ）。【西安电子科技大学 2001应用 一、4 （2分）】
a．从源点到汇点的最长路径        b．从源点到汇点的最短路径
c．最长回路                      d．最短回路
31. 下面关于求关键路径的说法不正确的是（    ）。【南京理工大学 1998 一、12 （2分）】
    a．求关键路径是以拓扑排序为基础的
    b．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
    c．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
    d．关键活动一定位于关键路径上
32．下列关于aoe网的叙述中，不正确的是（    ）。
a．关键活动不按期完成就会影响整个工程的完成时间
b．任何一个关键活动提前完成，那么整个工程将会提前完成
c．所有的关键活动提前完成，那么整个工程将会提前完成
d．某些关键活动提前完成，那么整个工程将会提前完成
【北方交通大学 1999 一、7 （3分）】【北京工业大学 1999 一、1 (2分)】