[理工] 101~104臺大電機丙組資結 4 題
大家好
因為問題規模都不大，整理在一起問好了，除了 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
→
02/16 23:33, , 1F
02/16 23:33, 1F
!!! 真假原來我觀念是錯的，感謝提醒 QQ
→
02/16 23:38, , 2F
02/16 23:38, 2F
→
02/16 23:42, , 3F
02/16 23:42, 3F
推
02/16 23:45, , 4F
02/16 23:45, 4F
→
02/16 23:45, , 5F
02/16 23:45, 5F
推
02/16 23:48, , 6F
02/16 23:48, 6F
→
02/16 23:48, , 7F
02/16 23:48, 7F
感謝 F 大提供第三題想法！來研究一下
→
02/16 23:53, , 8F
02/16 23:53, 8F
→
02/16 23:53, , 9F
02/16 23:53, 9F
推
02/16 23:54, , 10F
02/16 23:54, 10F
哦哦瞭解，我想法還太淺了 >< 感謝 F 大和 y 大！
→
02/17 00:25, , 11F
02/17 00:25, 11F
→
02/17 00:25, , 12F
02/17 00:25, 12F
Ok 已附上
推
02/17 01:43, , 13F
02/17 01:43, 13F
→
02/17 01:44, , 14F
02/17 01:44, 14F
嗯電機丙這種題目好像也不少 == 不過正常是照定義我想沒有錯只是他不提供參考答案
※ 編輯: kev72806 (180.206.8.121), 02/17/2016 09:11:41
推
02/17 14:28, , 15F
02/17 14:28, 15F
對。可是不是我那個想法 == 板上大神解釋這題考著色問題是不是多項式時間有解
推
02/17 17:08, , 16F
02/17 17:08, 16F
→
02/17 17:08, , 17F
02/17 17:08, 17F
推
02/17 17:40, , 18F
02/17 17:40, 18F
單純算有沒有路徑 DFS 或 BFS 好像是都可以沒錯
※ 編輯: kev72806 (101.14.48.238), 02/17/2016 23:30:15