作者ccapricorntw (11)
看板Grad-ProbAsk
標題Re: [理工] 台大電機丙 資結 104/105/106 對答案
時間Sat Dec 28 18:11:26 2019
※ 引述《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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1577527888.A.474.html
1F：推 mistel: 1.洪逸說選擇題要選符合上界的，看一些題目除非像電機丙1 12/28 18:16
2F：→ mistel: 04年的12b選項才不選 但真的蠻難分的 12/28 18:16
了解！不過洪逸說104 12b不選的原因是甚麼？
3F：→ mistel: 6 我也選A 12/28 18:16
4F：→ mistel: 8他是問of its largest clique，單純指最大的團吧 話說這 12/28 18:18
5F：→ mistel: 個子嘉那本圖論題庫最後面也有一樣的定義 12/28 18:18
所以是指largest clique有幾個vertex囉？ 我回去再翻一下小黃的書
6F：推 mistel: 12的B就不知道了，但我想不出來要怎麼用potential method 12/28 18:22
7F：→ mistel: 證logn，因為我們不能預期BST長怎樣，所以我覺得這個是錯 12/28 18:22
8F：→ mistel: 的 12/28 18:22
9F：推 mistel: 15應該只有B吧，你是不是沒有考慮到兩棵merge後出來的新t 12/28 18:28
10F：→ mistel: ree可能會跟另一棵繼續merge? 12/28 18:28
我是有想到 不過細節要怎麼merge有點想不出來 不過以符合上界來講應該是對的
11F：→ mistel: 16A是對的 12/28 18:28
12F：推 FRAXIS: 12 (A) 是錯的 (B) 應該是錯的 但是題義不是很清楚 12/28 22:46
13F：→ FRAXIS: 你沒有辦法保證對於所有的 random BST, amortized O(lgn) 12/28 22:47
14F：→ FRAXIS: 雖然有很高的機率 amortized O(lg n) 12/28 22:48
原來如此！先謝過m大跟F大~
15F：→ mistel: 請問F大，12的A要怎麼改才會是正確的敘述？ 12/28 23:14
16F：推 mistel: 其實104 12b我也不確定...我是看到如果符合上界我就選啦Q 12/28 23:17
17F：→ mistel: Q不然根本跟觀落音一樣 12/28 23:17
其實考研就是在觀落陰啦
※ 編輯: ccapricorntw (180.176.55.182 臺灣), 12/28/2019 23:26:48
18F：→ jeremyyuan: 12A 把上界拿掉就對了 12/28 23:33
19F：→ mistel: j大說的上界是？ ceiling？ 請問有來源可以參考嗎>< 12/29 18:15
20F：推 bochengchen: 想請問大大為什麼14題的Ｃ不選 01/20 14:27