作者IDontBite (IDontBite)
看板Grad-ProbAsk
标题[理工] [资结]-95中正-资结(graph)
时间Sun Jan 24 16:04:52 2010
Which are correct?
(A)We can use Dijkstra's shortest path algorihtm to solve the all pair
shortest path problem.
(B)A Priority Queue is a kind of Queue data structure.
(C)Heapsort is a stable sorting algorithm.
(D)A graph has only one minimum cost spanning tree.
(E)A biconnected graph does not contain articulation points.
洪逸书上给的答案是BE, A争议(基本上对,但应该强调是利用single source),
而B选项我觉得应该反过来说才对,
Queue是一种以进入时间为priority的Priority Queue,
而Priority Queue不一定符合Queue的FIFO规则, 所以不能算是一种Queue.
各位觉得呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.32.189.59
1F：推 polomoss:B没错，P_Queue为Q的其中一种变形~ 01/24 20:07
2F：推 FRAXIS:A是错的 因为Dijkstra只能解没有负边的图 01/24 21:03
3F：→ taitin:有争议的原因应该是johnson演算法 01/24 22:15
4F：→ taitin:利用加权重的方法可以消去负边，这样dijk就可以用了 01/24 22:16
5F：推 FRAXIS:那就看阅卷老师接不接受这种解释了.. 01/25 09:37