: 是非:
: 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怪怪的不敢選誒 求解釋

15c沒定義root從0還1開始算 從0的話是正確的9的話應該是問最少去掉多少邊才能使complete graph 不連通所以應該是T

10不是T嗎 2-node的意思不是branch factor為2嗎@@1.我的想法是 他想問coloring是不是NPC吧lower boundn^k是講是不是有polynomial解 可是2color有 所以選F

10是T

5.binomial heap不是除了insert,Dec key外其他op都花O(logn) 所以應該還是Logn吧問一下為什麼14d 還要取log 到樹葉的path=leaf數吧leaf 最多不是到約1/2的node 所以感覺O(max na,nb))

14(D)同樓上在DS裡binomial heap是insert和combine "tree"是O(1) actual and amortized

11b 還要maintain last還是O(n) E確認空只要O(1)把最大刪除=刪last node 但single link不知道前一點所以要花O(n)去找到下一個last node阿

感覺第5題還是沒有一個比較合理的解釋他是問假設insert很少被called 那f heap 的各種operation的amortized time complexity吧 還是我理解有誤我知道insert是O(1)沒錯

求其他高手解釋了qq

12題 merge要看是不是採用lazy merge吧QQ第7題10~-2插入 再將-2,-1刪除http://i.imgur.com/9aSb9ts.jpg 應該長這樣?

你這樣external node就不在同一層啦

高手好多 感動QQ

沒事 我腦殘了QQ 上面圖也是錯的

F5應該是5唷 不是8

對誒= = 我在講什麼咦 那這樣的話要h=4 F6-1才會是7啊 ；；

如果 insert 很少被 call 那 heap 裡面根本沒什麼元素啊..

那感覺就是O(1)了 謝謝F大

http://mathworld.wolfram.com/CliqueNumber.html 16(B)