大家好
因為問題規模都不大，整理在一起問好了，除了 103 那題 ...
1、101考題
http://i.imgur.com/2ywV1Fz.jpg
A 選項， sorted 過的 link list 搜尋時間可以到 O(logn)，所以這題應該是這個選項
錯
可是 E 選項刪除最大元素要找到最大元素的前一個是不是要 O(n)，找到之後才能改掉呢
？
2、102考題
http://i.imgur.com/VocGzRN.jpg
這題答案是 A 嘛？套用 Folyed 多項式時間就有解了，根據定義選 A 沒錯吧（bound不
緊不敢選 = =）
3、103考題
http://i.imgur.com/o7VXMnm.jpg
這題我沒什麼想法 >< 麻煩高手指點，我只想到多邊形判斷座標點在裡面還是在外面的方
法
4、104考題
http://i.imgur.com/tgoyxcc.jpg
這題我寫 B，我想的是著色他沒有要求最小著色數只要求相鄰顏色要不同，那就一個點一
個顏色給他，只要 O(1) 的時間即可。我這樣想會很危險嘛 @@
若不能這樣想麻煩糾正 感謝 ><

1. array才能用O(logn） A是對的2.B 不需要到2^n3.好像類似103台大資工的最後一題 我也不會orz

1(e) 如果 list 是可以修改的話 你只要把他下一個點的資料移到要被刪除的節點裡面 然後把下一個節點刪除就好了3 是 power diagramhttps://en.wikipedia.org/wiki/Power_diagram

4. 但不知道點與點有沒有相鄰啊 而且要給這個點顏色也要先經過它吧 不會是O(1)

4的話是 false 因為如果是 true 的話就等價 P != NP

p.s. 可以附一下年份 這樣之後的考生有相同問題的比較好找

我也想知道那種bound不夠緊的要不要選欸第二題我也是照定義選true

所以第一題是B嗎

疑想問一下第2題，我是分別用matrix和list表示來想的分別O(1)和O(e)都不是就選F了啊不對它是path我看錯了，不過這應該作DFS就夠了吧