Re: [理工] 104台大電機丙資演對答案

[yaxauw (yaxauw)]

: 是非:

: 1.F(沒特別說要怎麼著色  應該False吧?)
寫F 但我的理由是 它取omega 所以k取大一點的話 就不滿足了

: 2.F

: 3.F

: 4.F(Fixed size讓我有點猶豫...)

: 5.F
是因為寫rarely called才選F嗎 我選T

: 6.??
我選T誒 感覺跟林立宇老師講的Tree上找diameter有點像
等下再問問她

: 7.F
感謝dddm49幫助釐清觀點
B-tree的External Nodes必須在同一level所以它寫can be less than or "equal to 1"
是錯的

: 8.T

: 9.T(嗎??)
感謝dddm49的解釋
Kn圖至少要砍n-1個邊才會不連通

: 10.Top-Down 2-3-4ok  但是2-3就不是很確定  希望高手畫一下  囧
T
感謝jerry031181、odanaga解釋
畫法照level-order是 7、35、9、12、4、6、8、10
*2-node 3-node指的是external node數

: 複選:

: 11.
: BCDE
感謝jerry031181解釋

: 12.
: CE
A DS說O(1) Algo說O(logn) =""= 我看了一下wiki後決定選了
D 就是Merge 2個BinomialTree 我有選

: 13.
: BC
: 不熟c++的寫法
: t+=(str[i]<<(i*2))
: 等於
: str[i] = 2*i
: t+=str[i]
: 嗎?
E說的沒錯吧 就新增加的100-199slot不會用到
其他不太確定orz

: 14.
: CE
: D應該是False吧?
D我有選誒 假如到leaf的path有長有短 那就是取max 求高手解釋

: 15.
: CE
: A:好像大於O(2^n)?
: D:因為黑白建期望為logn高度  所以反過來看應該也是50%而不會greter than?
A看不懂..
C是錯的 h=4時才會是7
E是錯的吧 level-order建樹 黑黑紅紅紅黑黑 不會是2*r+1
因此我有選D.. 但不會證

: 16.
: DE
: B:不太清楚,是八個嗎?
: E:感覺要用reduce 但是不知道怎麼設計
D覺得寫exponential怪怪的不敢選誒 求解釋

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.108
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455684841.A.C8F.html
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 12:59:44
推 dddm49: 15c沒定義root從0還1開始算 從0的話是正確的
推 dddm49: 9的話應該是問最少去掉多少邊才能使complete graph 不連通
→ dddm49:  所以應該是T
噢噢了解!
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 13:31:08
→ jerry031181: 10不是T嗎  2-node的意思不是branch factor為2嗎@@
對誒= = 2-3tree只有2-node或3-node
→ jerry031181: 1.我的想法是 他想問coloring是不是NPC吧lower bound
→ jerry031181: n^k是講是不是有polynomial解 可是2color有 所以選F
推 odanaga: 10是T
→ jerry031181: 5.binomial heap不是除了insert,Dec key外其他op都花
→ jerry031181: O(logn)  所以應該還是Logn吧
http://imgur.com/OzXrfqX Fibonacci Heap跟Binomial Heap好像還是有點差異
by wiki
→ jerry031181: 問一下為什麼14d 還要取log 到樹葉的path=leaf數吧
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:24:38
→ jerry031181: leaf 最多不是到約1/2的node 所以感覺O(max na,nb))
推 janus7799: 14(D)同樓上
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:25:53
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:29:22
→ janus7799: 在DS裡binomial heap是insert和combine "tree"是O(1) a
→ janus7799: ctual and amortized
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:35:05
→ jerry031181: 11b 還要maintain last還是O(n) E確認空只要O(1)
謝謝j大! b選項maintain last可以再解釋一下嗎
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:42:43
→ jerry031181: 把最大刪除=刪last node 但single link不知道前一點
→ jerry031181: 所以要花O(n)去找到下一個last node阿
再搭配筆記懂了 謝謝講解
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:48:02
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:49:42
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:51:08
推 dddm49: 感覺第5題還是沒有一個比較合理的解釋
應該就是O(1)?
http://imgur.com/QFe0KRe
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 15:22:06
推 dddm49: 他是問假設insert很少被called 那f heap 的各種operation
→ dddm49: 的amortized time complexity吧  還是我理解有誤
→ dddm49: 我知道insert是O(1)沒錯
→ yaxauw: 求其他高手解釋了qq
→ f1256421: 12題 merge要看是不是採用lazy merge吧QQ
推 f1256421: 第7題10~-2插入  再將-2,-1刪除
→ f1256421: http://i.imgur.com/9aSb9ts.jpg  應該長這樣?
推 dddm49: 你這樣external node就不在同一層啦
※ 編輯: yaxauw (140.112.7.214), 02/17/2016 18:28:06
推 goldflower: 高手好多  感動QQ
→ f1256421: 沒事  我腦殘了QQ  上面圖也是錯的
→ funboy820: F5應該是5唷  不是8
→ yaxauw: 對誒= = 我在講什麼
※ 編輯: yaxauw (140.112.25.108), 02/18/2016 00:06:53
→ yaxauw: 咦 那這樣的話要h=4 F6-1才會是7啊 ；；
推 FRAXIS: 如果 insert 很少被 call 那 heap 裡面根本沒什麼元素啊..
※ 編輯: yaxauw (140.112.25.108), 02/18/2016 00:45:28
推 dddm49: 那感覺就是O(1)了 謝謝F大
推 maxacre: http://mathworld.wolfram.com/CliqueNumber.html 16(B)