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

作者: kev72806 (Taipei 101)   2016-01-28 23:21:03
想請教一下這題,
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
作者: sm02188612 (The Children 01)   2016-01-28 23:35:00
14,15插刪,node的array元素要挪移 ; flow那題capacity相異cut也不唯一,故意找例子看,比如讓流出s跟流入t剛好都是max flow
作者: odanaga (PixiyON)   2016-01-28 23:37:00
58 就一條6後面接123 那6和123都是min cut10交大有更正答案是e
作者: dslin (Magic)   2016-01-28 23:43:00
13題是先找到x位於那個node,有n/m個,所以時間是O(n/m),再對node內的m個data做binary search時間是O(logm),所以為O(logm+n/m);14,15題先找到x位於那個node,時間O(n/m),插入刪除後要考慮到node內m個元素的調整(因為是array),所以是O(m)

Links booklink

Contact Us: admin [ a t ] ucptt.com