找考题网-背景图
单项选择题

A.（1）是（2）可能（3）可能B.（1）否（2）可能（3）可能C.（1）是（2）不可能（3）不可能D.（1）……

许多人小时候都做过“农夫，狼、羊和白菜”过河的智力题。这里就假设大家都是知道规则的。现在我们虚构一个农夫和5样动物（称它们为A，B，C，D，E）过河的题目。假设没农夫在场的时候，A要吃B，B要吃C，C要吃D，D要吃E；没有其他吃的关系了。同时还假设那条船上除了农夫外，还可以容纳最多2个动物。有人设计了一个让它们过河的算法如下：

此题有三问：（）
（1）这个算法是否成功地将它们都带过河了？
（2）如果那条小船除农夫外，最多还只能容纳1个动物，有可能设计一个成功的算法吗？
（3）假设小船除农夫外，最多还可以容纳2个动物，但总共有6个动物（还是那种链式吃关系），有可能设计一个成功的算法吗？



A.（1）是（2）可能（3）可能
B.（1）否（2）可能（3）可能
C.（1）是（2）不可能（3）不可能
D.（1）否（2）不可能（3）不可能

<上一题 目录 下一题>
热门试题

单项选择题假设有A（7升）、B（5升）两个桶。有人给出了一个算法，请问它的执行将导致的结果（）。

A.A=6，B=0
B.A=3，B=0
C.A=0，B=3
D.算法描述不清楚

多项选择题下图中，i-j的路径是经过单源路径算法（Dijkstra）或多源路径算法（Floyd）得到的最短路径，中间节点包含节点v1，v2，…vk。对于单源路径算法，i表示源点（s），对于多源路径算法，i可以是任意节点。请选择以下正确的选项（）。

A.采用Floyd算法，能保证点i-j间的中间节点v1，v2，…vk，包括i，j中任意节点对之间都是最短路径
B.采用Dijkstra算法，能保证源点i到所有中间节点v1，v2，…vk，以及j是最短路径，不能确保这些节点之间也一定是最短路径
C.采用Dijkstra算法，能保证源点i-j是最短路径，不能确保路径中其他节点对之间也一定是最短路径
D.采用Dijkstra算法，能保证源点i-j间的中间节点v1，v2，…vk，包括i，j中任意节点对之间都是最短路径

多项选择题‍下图是采用课程介绍的多源路径算法得到最短路径前驱点矩阵，利用该矩阵选择如下正确的最短路径（）。

A.D-A的最短路径是，D-C-B-A
B.A-B的最短路径是，A-C-B
C.E-C的最短路径是，E-D-B-C
D.E-D的最短路径是，E直接连接到D

单项选择题下图是一个4节点的有向图，利用Floyd多源最短路径算法依次经过节点A、B、C、D中转后，得到最短路径矩阵。编程实现多源最短路径算法，并列出A-D、B-D的路径值在经过中转点A、B、C、D后的更新值（）。

A.A-D的更新过程：->->->9，B-D的更新过程过程：9->9->9->8
B.A-D的更新过程：->->10->9，B-D的更新过程过程：9->9->8->8
C.A-D的更新过程：->10->9->9，B-D的更新过程过程：9->9->8->8
D.A-D的更新过程：->->->9，B-D的更新过程过程：9->8->8->8

多项选择题下图是一个7节点连通图，权值如图所示。尝试利用Dijkstra算法思路手工计算源点A到其他点的最短路径，并选择以下正确的选项（）。

A.当节点集S={A ，C ，F ，B}，时，下一个进入S的节点是E
B.当节点集S={A ，C ，F ，B}，时，下一个进入S的节点是D
C.A-G最短路径的前驱节点是E
D.A-G最短路径的前驱节点是D