Re: [理工] 台大電機丙資結 104/105/106 對答案

看板Grad-ProbAsk作者ccapricorntw (11)時間4年前 (2019/12/28 18:11)推噓6(6推 0噓 14→)

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

※ 引述《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

-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.176.55.182 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577527888.A.474.html

推

Re: [理工] 台大電機丙 資結 104/105/106 對答案

Re: [理工] 台大電機丙資結 104/105/106 對答案