当各边上的权值（)时，BFS算法可用来解决单源最短路径问题。【中科院计算所2000一、3（2分)】A．均相

际应用中无意义； (2)利用Dijkztra求每一对不同顶点之间的最短路径的算法时间是O(n3)(图用邻接矩阵表示)； (3)Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是( )。【南京理工大学2000一、21(1．5分)】

A．(1)，(2)，(3)

B．(1)

C．(1)，(3)

D．(2)，(3)

在具有n个顶点的图G中，若最小生成树不唯一，则( )。【电子科技大学2008一、2(1分)】

A．G的边数一定大于n-1

B．G的权值最小的边一定有多条

C．G的最小生成树的代价不一定相等

D．上述选项都不对

在求边稠密的图的最小代价生成树时，采用( )算法较合适。【上海交通大学2005四、7(2分)】

A．普里姆(Prim)

B．克鲁斯卡尔(Kruskal)

C．迪杰斯特拉(Dijkstra)

D．其他

】

A．O(n)

B．O(n+e)

C．O(n2)

D．O(n2)

此题为判断题(对，错)。

此题为判断题(对，错)。

该无向图一定是连通图。( )【中南大学2003一、18(1分)】

此题为判断题(对，错)。

下列有关图的说法错误的是( )。【中南大学2003二、19(1分)】

A．在有向图中，出度为0的结点称为叶子

B．用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度

C．按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的

D．若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点Vi必在结点Vj之前的话，则称为一个拓扑序列

分)】【哈尔滨工业大学2004二、3(1分)】

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动若提前完成，那么整个工程将会提前完成

下面关于求关键路径的说法不正确的是( )。【南京理工大学1998一、12(2分)】

A．求关键路径是以拓扑排序为基础的

B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

D．关键活动一定位于关键路径上