采用邻接表存储的图的深度优先遍历算法类似于树的()，而其广度优先遍历算法类似于树的()。【北京交通大学2007】

04】

A．对称矩阵

B．稀疏矩阵

C．三角矩阵

D．一般矩阵

0一、9(1．5分)】【江苏大学2006一、1(2分)】

A．G中有弧j>

B．G中有一条从Vi到Vj的路径

C．G中没有弧i，Vj>

D．G中有一条从Vj到Vj的路径

一个有向无环图的拓扑排序序列( )是唯一的。【北京邮电大学2001一、3(2分)】

A．一定

B．不一定

1998二、6(2分)】【中国科技大学1998二、6(2分)】

A．存在

B．不存在

已知有向图G=(V,E)，其中V={V1，V2，V3，V4，V5，V6，V7}，庐{1，V2>，1，V3>，1，V4>，2，V5>，3，V

A．V1，V3，V4，V6，V2，V5，V7

B．V1，V3，V3，V6，V4，V5，V7

C．V1，V3，V4，V5，V2，V6，V7

D．V1，V2，V5，V3，V4，V6，V7

分)】

A．O(n)

B．O(n+e)

C．O(n*n)

D．O(n*n*n)

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

A．均相等

B．均互不相等

C．不一定相等

际应用中无意义； (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．其他