数据结构考研分类复习真题 第七章 图[7]

() 求从指定源点到其余各顶点的迪杰斯特拉(Dijkstra)最短路径算法中弧上权不能为负的原因是在实际应用中无意义

() 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n ) (图用邻接矩阵表示)

() Floyd求每对不同顶点对的算法中允许弧上的权为负但不能有权和为负的回路

上面不正确的是( )【南京理工大学 一 (分)】

A．()()() B．() C．()() D．()()

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

A．均相等 B．均互不相等 C．不一定相等

求解最短路径的Floyd算法的时间复杂度为( )【合肥工业大学 一 (分)】

A．O(n) B O(n+c) C O(n*n) D O(n*n*n)

．已知有向图G=(VE)其中V={VVVVVVV}

E={<VV><VV><VV><VV><VV><VV><VV><VV><VV>}G的拓扑序列是( )【北京航空航天大学 一 (分)】

A．VVVVVVV B．VVVVVVV

C．VVVVVVV D．VVVVVVV

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []