[理工] 101交大 OS & DS 三題

[kev72806 (想太多oo)]

想請教一下這題，
13題我的想法是搜尋一個在 link list 中的 node 需要的複雜度，有 n/m 個點，每個點
內的 data 以陣列形式儲存所以搜到的複雜度是 logm
可是這樣看 14 worst case 及 15 Delete node 好像就出問題了 ... 想請教一下正確的
分析
http://i.imgur.com/mZG2Zrl.jpg

58 題答案是 D，是說 minimum cut 必定唯一存在所以邊不需要是相異的嘛？還是說因為
沒有限制住邊要是整數所以 minimum cut 未必可解呢？
http://i.imgur.com/3M9rP7L.jpg

10 這題是 OS 考卷上的，答案是 C，可是我怎麼想都怪怪的，麻煩解釋一下了 ><
http://i.imgur.com/o1QM46q.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 175.96.216.54
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1453994466.A.7EC.html
→ sm02188612: 14,15插刪,node的array元素要挪移 ; flow那題capacity
→ sm02188612: 相異cut也不唯一,故意找例子看,比如讓流出s跟流入t剛
→ sm02188612: 好都是max flow
原來如此！！被題目沖昏頭了想到太遠的地方去，謝謝 s 大說明
推 odanaga: 58 就一條6後面接123 那6和123都是min cut
→ odanaga: 10交大有更正答案是e
忘了要多看一下勘誤表 -....- 謝謝 o 大的提醒跟反例！
推 dslin: 13題是先找到x位於那個node,有n/m個，所以時間是O(n/m),再
→ dslin: 對node內的m個data做binary search時間是O(logm),所以為O(l
→ dslin: ogm+n/m);14,15題先找到x位於那個node,時間O(n/m)，插入刪
→ dslin: 除後要考慮到node內m個元素的調整(因為是array),所以是O(m)
對吼要挪動，解說很詳細這樣我清楚了^^ 謝謝 d 大
※ 編輯: kev72806 (49.214.48.194), 01/29/2016 09:38:27