[理工] 104中央 資演

[ponwar87123 (干我屁事喔北七)]

1.第一題
https://i.imgur.com/7xfFccb.jpg
這題我很勉強選了B，
但其實我覺得BC都蠻可以的啊(?
而且有時候我覺得遞迴沒有很好懂就是了

2.第四題
https://i.imgur.com/a5WaKAd.jpg
這題我選E是因為算成full binary tree了
可是如果logn不為整數，那要算取多少？
上界還下屆？

3.第九題
https://i.imgur.com/5AMdnzP.jpg
想問這題該選A還是C?
兩個都可以做出DFS吧？但哪個比較優質我就不知道了

4.第十七題
https://i.imgur.com/2cPzkQp.jpg
這題有大大能解說一下該怎麼做嗎QQ
完全沒想法
-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 175.97.13.57 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1576383030.A.7FC.html
推 mistel: reduction那題是把欲sort的instance轉換成x軸上的坐標，x
→ mistel: 1->(x1,0) x2->(x2,0)...
推 mistel: 第四題應該要選D吧 3顆節點的complete BT高不是2？
→ zuchang: 17是演算法convex hill  課本有reduce過程
推 mistel: 樓上，這題是reduce到MST，應該不一樣喔
→ zuchang: 等等 不用那麼難 用kruskal reduce過去應該就好
→ mistel: 欲證明MST的lower bound應該是把sorting的instance轉換成
→ mistel: MST的
→ mistel: https://i.imgur.com/b6vIo28.jpg 供參
→ zuchang: 這題立宇有放在np的例題 mi大的想法比較好OAO
→ ponwar87123: 謝謝大家，那請問其他題呢
→ ponwar87123: 還有這題
→ ponwar87123: https://i.imgur.com/BOfXkmd.jpg
→ ponwar87123: 為何第十五題A要選？如果全為負不是return最大負值就
→ ponwar87123: 好了嗎
推 Aa841018: 1.rerecuresive很難設計和debug，因為通常一直遞下去，
→ Aa841018: 追蹤都有一定難度，何況設計或是除錯
推 mathtsai: 1.我覺得不好debug這點要看和啥比
→ mathtsai: 3.recursive就是用stack疊代
那這題該選哪個呢？

→ mathtsai: 15.return最大的 所以S'不就有一個負數了
※ 編輯: ponwar87123 (175.97.13.57 臺灣), 12/15/2019 22:11:07
→ mathtsai: 兩個都對吧 反正實作都能做出來
→ ponwar87123: 這樣考試該怎麼選XDD 它單選啊啊啊