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

[joywilliamjo (joywilliamjoy)]

重新整理一下
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: 第三題2不能選嗎OAO? o(nn^1/2)應該大於nlogn惹?
那這樣答案就要變245了，哭啊= =根本在考文字遊戲的感覺
→ try66889: 9-3 如果是right skewed BST的話找最大值應該是O(n)?
我改一下= =沒看到worst case，感謝
※ 編輯: joywilliamjo (223.140.6.98 臺灣), 01/29/2021 12:14:13
→ try66889: 希望今年考試可以寫清楚要不要tightness QQ 123題
→ try66889: 真的不知道要怎麼選~"~
不寫又沒有正確答案，哭啊
推 lin130917: 14題a我覺得是false因為diameter是要取最大的只有一個
→ lin130917: 值
→ lin130917: 14b我也覺得是false因為tree的center最多兩個
→ lin130917: 阿抱歉14a應該是true如果他的定義是path的話
我對題目理解是同長度不同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: 你畫的b不是tree吧tree不能有cycle
推 lin130917: https://reurl.cc/o9e0MV
→ lin130917: https://reurl.cc/E2pG5A
感謝QQ
※ 編輯: joywilliamjo (223.140.6.98 臺灣), 01/29/2021 13:34:13
推 Henry658: 109 台大清大都考center聯合出題484
推 nasa930022: 10-3把新的點插入leaf再連到null的黑點之後就離開了
→ nasa930022: 這樣不會改變root到leaf之間的black node數量吧?
我個人是覺得3不用選QQ，畢竟就是插 一個紅的進去一個本來就是正常的紅黑樹，不會影
響路徑上的黑node 數，我改個
※ 編輯: joywilliamjo (223.137.255.128 臺灣), 01/31/2021 12:10:29