Re: [理工] [資結]-台大98-軟體設計 對答

[taitin (小南)]

: 不好意思  因為文章太長他不給我貼  所以才砍一部分文章 sorry
: 想問一下這兩題 其中第3題的9-20格他不是都給ptr了嗎??
: 為何還要花O(n)啊??  還有22 跟 26格不是一個填A另一個就要B嗎
: 因為假設sort是遞增min就O(1) max不就要O(n)嗎
: 因為要從第一個一到最後一個ptr

3-9，10，13，14

題目說 delete(L,p) deletes a object point by p from L

因為是singlist

     A->X->B
若x為所指，想要刪除X必須知道前一個節點的位置
因此必須從兩端搜索，worst case是n/2

     A->link=p->link;
     delete p;
sort不sort是一樣的

而precessor要找到前一個節點，作法雷同。


至於9~20(除了9，10，13，14)
我本來就寫A阿，是O(1)


3-22，26

題目的第1.2行說
one root pointer one tail pointer
point to first and last node



: 至於最後一提的第3小提
: 還是不知道要選A or B以及選的理由
: 煩請解惑  謝謝

選A

因為A對每個邊都進行relax，這樣負值的邊也可以被考慮進去

而B每次選可到達但是最小的邊

如

             4
          -------
         /       \
         a---c---b
           5   -2


由a點開始，選擇ab為最小邊後，

依據該演算法，

output ab最短路徑為5

但實際上ab最短路徑應為3

由此可知此演算法在邊值有負值時，將會有問題發生。

若是不了解可以參考 dijkstra's algo 跟 bellman's algo

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.216.173.134
推 yesa315:請問你(5) (8) 我都寫(5)B 不是要還找前一個node嗎? (8)A
→ yesa315:問問看你的想法 謝謝@@
推 NOtWorThy:THX~!
→ taitin:(5)因為是unsort，所以直接在端點插入就好
→ taitin:(8)因為是sorted，最糟的清況會是在串列的中央，O(n)
→ taitin:sorted插入後要保持sort