※ 引述《a020304888a (張小台)》之銘言：
: Hi 大家早
: 昨日寫了近3年的資結
: 由於年份較近的考古題答案不太好找
: 想跟大家對一下答案順便討論
: 在此附上考題連結 (p.s.剛剛縮址不知道為啥縮不了 晚點再修)
: 106:
: http://140.112.115.12/exam/sites/default/files/exam/graduate/106g/106_graduate_407.pdf
: 105:
: http://140.112.115.12/exam/sites/default/files/exam/graduate/105/414_2016_graduate.pdf
: 104:
: http://140.112.115.12/exam/sites/default/files/exam//graduate/104/417_104graduate.pdf
: 以及附上我個人檢討過+網路上的答案
: 106年討論很少 我個人寫的應該有不少錯誤請見諒= =
小弟想討論關於106的部分
: 106:
: 是非 (A:True B:False)
: 1.A
我是選(B)
這題比較tight的big O應該是O((n+1)!)吧？
這樣好像就牽扯到題目big O不tight要不要選的問題
我的想法是有提到 "complexity" 的就要選tight的
沒提到的像 "It takes O(f(n)) time..." 或是 "f(n)=O(g(n))"這類比較的就可以選不tight的
不知道這個想法有沒有問題... 懇請理論派的演算法大師們開示一下
: 2.B
: 3.A
: 4.B
: 5.B
: 6.B
這不是(A)嗎？
: 7.A
: 8.A
不太知道cadinality到底是指 "有幾個largest clique"
還是指 "largest clique裡面有幾個vertex"
如果是前者的話這題應該是(B)吧？
: 9.A
: 10.B
: 複選
: 11.C
: 12.D(E)
: E選項不知道該不該選, 爬文有人提到可以在O(N)甚至O(1)完成
我是選(B)(D)(E)
看到之前FRAXIS大大有講解 不過還是有點疑問
(A)說要在n = 2^k-1的情況下balenced的機率很小 所以F大在 #1SH42OOb應該是打錯了？
(B)amortized應該是一串差不多複雜度的operation 突然出現一個worst case可以忽略的
意思吧？
#1QFdFK8A 這篇中F大好像講相反了？
所以我認為BST insertion只要不要變成斜曲樹 應該大部分都還是O(logn)吧？
: 13.AB
https://imgur.com/RAjnqss
我是畫這樣 答案一樣是AB 應該是對的吧？
: 14.E
: 15.E
: 我用Lazy merge下去想的
答案不確定 有人是選只選(B)
但(B)worst case下兩個binomial heap各有log na和log nb顆子樹 然後同order的由小到
大兩兩做merge 不是應該最多是merge O(log(max(na, nb)))次嗎？
(D)感覺錯 但正確不知道是什麼 好像也不是O(log(na+nb))
(E)感覺是錯的 如果ra跟rb在order一樣的子樹merge完會在同一顆
: 16.BE
(A)是對的吧？ https://imgur.com/bZAl1mW