[理工] 95台大資結 對答案

[KBZhangJike (鍵盤張繼科)]

附上我不確定的題目
https://i.imgur.com/WOL7C3Y.png

1. C
2. E
3. C
4. B
5. A
6. C
題目是說隨意的BST，worst case到底要選O(n)還是O(logn)好
7. E
8. D
ω(G)是說graph裡最大clique的node數，還是最大clique的數量
9. BCE
10. C
11. ABDE
12. CD
13. A
14. ABCE
這題是看洪逸的題庫，但DE不太明白
15. BCD
洪逸的答案沒有D
16. AB
17. AD
18. ADE
看聖經本的Fibonacci heap的insert是O(1)，不知道我有沒有看錯

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.216.43
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548645691.A.B9B.html
推 Fanchien: Fib heap大多數情況是O(1) 少部分worst case情況下是O(L
→ Fanchien: ogn) 採分攤成本來看就是O(1)
推 luw501: 4.我選B，我想說如果是(2)的情況，那紀錄下來的時候應該
→ luw501: 是a指b、b指a，這樣不就會形成cycle了嗎
推 luw501: 8.我是是由4個vertex組成，那cardinality應該是4吧…
→ luw501: 14.我選ABC，D我試著想說若p(n)=n!，那它的big O就不只c
→ luw501: ^n。E的話也不懂，困擾很久
→ KBZhangJike: 感謝大家～