Dijkstra算法可以求解任何条件下的最短路问题。（)

以下几种算法中可以求解起讫点不同的单一路径规划(最短路径问题)的是( )。

A．扫描法

B．表上作业法

C．单纯形法

D．Dijkstra算法

下列不属于起讫点不同的单一路径规划(最短路线问题)中的算法的是( )。

A．Dijkstra算法

B．逐次逼近法

C．Floyd算法

D．表上作业法

下列方法中（）是求解最短路问题的解法。

A.表上作业法

B.DIJKSTRA法

C.单纯形法

D.破圈法

A、如果赋权有向图D中不含负回路，那么从vs到任一点的最短路最多包含p-2个中间点，图中其它的任一点，可以在最短路上出现一次以上；

B、如果赋权有向图D中不含负回路，那么从vs到任一点的最短路最多包含p-1个中间点，图中其它的任一点，不可能在最短路上出现一次以上；

C、如果赋权有向图D中不含负回路，那么从vs到任一点的最短路必为初等路，最多包含p-2个中间点，图中其它的任一点，不可能在最短路上出现一次以上；

D、如果赋权有向图D中不含负回路，那么从vs到任一点的最短路必为初等路，最多包含p-2个中间点，图中其它的任一点，不可能在最短路上出现一次以上；

A、最短路径一定是简单路径。

B、迪杰斯特拉（Dijkstra）算法不适用于有回路的有向网。

C、迪杰斯特拉（Dijkstra）算法是按路径长度递增次序依次来产生从单源点到其余各顶点的最短路径的。

D、弗洛伊德（Floyd）算法求任意两顶点间的最短路径时，一定是的子集。

E、在迪杰斯特拉（Dijkstra）算法中，若存在某些弧的代价为负值则将导致无限循环。

F、当有向图中所有弧的代价均相等时，广度优先搜索（BFS）也可用于求解最短路径问题。

下列关于广度优先算法的说法正确的是（ ）。I当各边的权值相等时，广度优先算法可以解决单源最短路径问题II当各边的权值不等时，广度优先算法可用来解决单源最短路径问题III广度优先遍历算法类似于树中的后序遍历算法Ⅳ实现图的广度优先算法时，使用的数据结构是队列

A．I、Ⅳ

B．II、III、Ⅳ

C．II、Ⅳ

D．I、III、Iv

阅读以下关于OSPF动态路由协议的技术说明，结合网络拓扑图回答相关问题1至问题4。

【说明】

最短路径优先(SPF)算法(也称为Dijkstra算法)是OSPF路由协议的基础。SPF算法将每一个路由器作为根(root)来计算其到每一个目的路由器的距离，每一个路由器根据一个统一的数据库计算出路由区域的拓扑结构图(最短路径树)。为提高网络的通信安全，需在路由广播时采用相应的安全授权机制。在图4-10所示的网络拓扑图中，在Router1和Router2的区域0上使用了基于MD5算法的身份验证技术。

当路由器Router1启用OSPF协议后，将每10秒钟向它的各个接口发送Hello分组，接收到Hello分组的路由器就知道了邻居的存在。如果在40秒内没有从特定的邻居接收到这种分组，路由器就认为那个邻居不存在了。

OSPF邻接建立过程主要经过关闭(Down)、尝试(Attempt)、初始(Init)、双向(Two-Way)、启动 (ExStart)、交换(Exchange)、装入(Loading)、完成(Full)等状态。请用试题中的相关术语将图4-11中(1)～(5)空缺处的内容填写以形成一张完整的OSPF邻居状态机图。

A、城市间最短航线问题

B、农夫过河问题

C、哥尼斯堡七桥问题

D、中国邮递员问题

以下不是贪心法求解的是_____。

• A、

  最短路径

• B、

  删除问题

• C、

  货币支付

• D、

  最小生成树

下列属于最小费用流问题的为()

A、运输和指派

B、转运问题

C、最大流问题

D、最短路问题