Re: [理工] 100&101台大電機丙-DS

[cocoyan (摳摳厭)]

和大家討論一下101年的答案，100年還沒寫
※ 引述《BuliBuchi (不離不棄)》之銘言：
: http://tinyurl.com/cpkzwuq 101
: http://tinyurl.com/cd77xza 100
: 想跟大家對個答案
: 不過寫起來蠻不順的
: 所以有錯請大大指教
: 101
: 單選
: 1~5.AECBD
: 多選
: 6.AD
其實A有一點小瑕疵
因為有可能program A=n^2=O(n^d)
                  B=n=O(c^n)
不過當初問洪兔他說應該沒有那麼心機
可是我還是覺得台大電機就想考這個XD
: 7.CDE
C真的很鳥
又給max-heap
又給GET(u,v)
如果規定這個max-heap只能用GET(u,v)來acess的話那就不是O(1)
如果可以隨意存取那就是O(1)

D是錯的
因為有可能形成k個complete graph
例如：(a,b),(b,c),(c,a),(d,e),(e,f),(f,g)
=>     a      d
      / \    / \
      b－c   e－f
: 8.AB
: 9.ADE
E是錯的
http://www.cs.usfca.edu/~galles/visualization/RedBlack.html
: 10.CDE
: 11.AB

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.162.30
→ olderbrother:問一下 6 的 B=n=O(c^n) 的 c 要帶哪個值阿？
只要大於1就可以了
※ 編輯: cocoyan         來自: 1.161.163.229        (02/23 17:30)
→ olderbrother:所以你是要說 n=O(2^n), n != theta(2^n) ?
是的
※ 編輯: cocoyan         來自: 1.161.163.229        (02/23 18:08)
→ w781204:ㄜ我是覺得6A就很單純，不用想那麼多@@
→ w781204:我們系上的老師感覺沒那麼無聊去玩心機@@
→ w781204:7C我也覺得他只是單純單純想考max heap取最大值的概念而已
→ w781204:7D我想法和你一樣，覺得是錯的