[理工] 臺大電機丙組資結 4 題

[kev72806 (想太多oo)]

大家好
因為問題規模都不大，整理在一起問好了，除了 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) 的時間即可。我這樣想會很危險嘛 @@
若不能這樣想麻煩糾正 感謝 ><

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.64.216
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455636232.A.E5E.html
※ 編輯: kev72806 (49.216.64.216), 02/16/2016 23:27:17
→ yaxauw: 1. array才能用O(logn） A是對的
!!! 真假原來我觀念是錯的，感謝提醒 QQ
→ yaxauw: 2.B 不需要到2^n
→ yaxauw: 3.好像類似103台大資工的最後一題 我也不會orz
推 FRAXIS: 1(e) 如果 list 是可以修改的話 你只要把他下一個點的
→ FRAXIS: 資料移到要被刪除的節點裡面 然後把下一個節點刪除就好了
推 FRAXIS: 3 是 power diagram
→ FRAXIS: https://en.wikipedia.org/wiki/Power_diagram
感謝 F 大提供第三題想法！來研究一下

→ yaxauw: 4. 但不知道點與點有沒有相鄰啊 而且要給這個點顏色也
→ yaxauw: 要先經過它吧 不會是O(1)
推 FRAXIS: 4的話是 false 因為如果是 true 的話就等價 P != NP
哦哦瞭解，我想法還太淺了 >< 感謝 F 大和 y 大！
→ yaxauw: p.s. 可以附一下年份 這樣之後的考生有相同問題的比較
→ yaxauw: 好找
Ok 已附上
推 irenelove: 我也想知道那種bound不夠緊的要不要選欸
→ irenelove: 第二題我也是照定義選true
嗯電機丙這種題目好像也不少 == 不過正常是照定義我想沒有錯只是他不提供參考答案
※ 編輯: kev72806 (180.206.8.121), 02/17/2016 09:11:41
推 leoturkey: 所以第一題是B嗎
對。可是不是我那個想法 == 板上大神解釋這題考著色問題是不是多項式時間有解
推 dary856974: 疑想問一下第2題，我是分別用matrix和list表示來想的
→ dary856974: 分別O(1)和O(e)都不是就選F了
推 dary856974: 啊不對它是path我看錯了，不過這應該作DFS就夠了吧
單純算有沒有路徑 DFS 或 BFS 好像是都可以沒錯
※ 編輯: kev72806 (101.14.48.238), 02/17/2016 23:30:15