Re: [理工] 台大資工 109 資演對答案+問問題

看板Grad-ProbAsk作者joywilliamjo (joywilliamjoy)時間3年前 (2021/01/29 11:02)推噓6(6推 0噓 8→)

留言14則, 4人參與討論串2/2 (看更多)

重新整理一下 1. 有爭議，最tight是3，但是因為是多選題，也沒有說最tight，所以45不知道該不該選 2. 有爭議，沒有給最小的min(n,m)導致這題唯一可能的解是3，也可能是none 3. none，是小o，sorting有機會等於nlgn 4. 1245 5. 1245，3一樣是tight不tight不知道該不該選= = 6. 345，感謝版友提供，clrs有類似題 7. 13 8. 12吧， 4應該是常數，從小到大進去就不一定會是i了，5太緊 9. 145， 2會太緊，skewed的狀況會變O(n)，3也是 10. 45 11. merge sort變形，O(1.5n) 12. 題目 total revenue = l_i+l_j這一段看不懂 13. a) 版友提供，測是否連通無cycle 14. 我自己的圖是長這樣啦，拜託錯了告訴我QQ 感謝版友 a是TRUE b是False https://i.imgur.com/gBqcmPz.jpg

證明用矛盾證法 15. vertex cover reduce to set cover 前三題最簡單卻也最像猜猜樂QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.228.118.3 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1611889360.A.89B.html ※ 編輯: joywilliamjo (223.140.6.98 臺灣), 01/29/2021 11:03:41

推

try66889

01/29 12:03, 3年前 , 1^F

01/29 12:03, 1^F

那這樣答案就要變245了，哭啊= =根本在考文字遊戲的感覺

→

try66889

01/29 12:10, 3年前 , 2^F

01/29 12:10, 2^F

我改一下= =沒看到worst case，感謝 ※ 編輯: joywilliamjo (223.140.6.98 臺灣), 01/29/2021 12:14:13

→

try66889

01/29 12:23, 3年前 , 3^F

01/29 12:23, 3^F

→

try66889

01/29 12:23, 3年前 , 4^F

01/29 12:23, 4^F

不寫又沒有正確答案，哭啊

推

lin130917

01/29 12:37, 3年前 , 5^F

01/29 12:37, 5^F

→

lin130917

01/29 12:37, 3年前 , 6^F

01/29 12:37, 6^F

→

lin130917

01/29 12:38, 3年前 , 7^F

01/29 12:38, 7^F

→

lin130917

01/29 12:40, 3年前 , 8^F

01/29 12:40, 8^F

我對題目理解是同長度不同path，B的話我畫的那個圖算tree嗎？對center的定義不太熟悉 ※ 編輯: joywilliamjo (223.140.6.98 臺灣), 01/29/2021 12:42:04 ※ 編輯: joywilliamjo (223.140.6.98 臺灣), 01/29/2021 12:42:37

推

lin130917

01/29 12:45, 3年前 , 9^F

01/29 12:45, 9^F

推

lin130917

01/29 12:50, 3年前 , 10^F

01/29 12:50, 10^F

→

lin130917

01/29 12:52, 3年前 , 11^F

01/29 12:52, 11^F