作者KBZhangJike (键盘张继科)
看板Grad-ProbAsk
标题[理工] 95台大资结 对答案
时间Mon Jan 28 11:21:28 2019
附上我不确定的题目
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548645691.A.B9B.html
1F：推 Fanchien: Fib heap大多数情况是O(1) 少部分worst case情况下是O(L 01/28 16:23
2F：→ Fanchien: ogn) 采分摊成本来看就是O(1) 01/28 16:23
3F：推 luw501: 4.我选B，我想说如果是(2)的情况，那纪录下来的时候应该 01/28 23:20
4F：→ luw501: 是a指b、b指a，这样不就会形成cycle了吗 01/28 23:20
5F：推 luw501: 8.我是是由4个vertex组成，那cardinality应该是4吧… 01/28 23:24
6F：→ luw501: 14.我选ABC，D我试着想说若p(n)=n!，那它的big O就不只c 01/28 23:30
7F：→ luw501: ^n。E的话也不懂，困扰很久 01/28 23:30
8F：→ KBZhangJike: 感谢大家～ 01/29 10:54