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

看板Grad-ProbAsk作者 (yaxauw)時間9年前 (2016/02/17 12:54), 9年前編輯推噓12(12推 0噓 22→)
留言34則, 10人參與, 最新討論串2/3 (看更多)
: 是非: : 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
推
02/17 13:11, , 1F
15c沒定義root從0還1開始算 從0的話是正確的
02/17 13:11, 1F
推
02/17 13:22, , 2F
9的話應該是問最少去掉多少邊才能使complete graph 不連通
02/17 13:22, 2F
→
02/17 13:22, , 3F
所以應該是T
02/17 13:22, 3F
噢噢了解! ※ 編輯: yaxauw (140.112.25.108), 02/17/2016 13:31:08
→
02/17 14:02, , 4F
10不是T嗎 2-node的意思不是branch factor為2嗎@@
02/17 14:02, 4F
對誒= = 2-3tree只有2-node或3-node
→
02/17 14:04, , 5F
1.我的想法是 他想問coloring是不是NPC吧lower bound
02/17 14:04, 5F
→
02/17 14:05, , 6F
n^k是講是不是有polynomial解 可是2color有 所以選F
02/17 14:05, 6F
推
02/17 14:09, , 7F
10是T
02/17 14:09, 7F
→
02/17 14:10, , 8F
5.binomial heap不是除了insert,Dec key外其他op都花
02/17 14:10, 8F
→
02/17 14:11, , 9F
O(logn) 所以應該還是Logn吧
02/17 14:11, 9F
http://imgur.com/OzXrfqX
Fibonacci Heap跟Binomial Heap好像還是有點差異 by wiki
→
02/17 14:17, , 10F
問一下為什麼14d 還要取log 到樹葉的path=leaf數吧
02/17 14:17, 10F
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:24:38
→
02/17 14:18, , 11F
leaf 最多不是到約1/2的node 所以感覺O(max na,nb))
02/17 14:18, 11F
推
02/17 14:24, , 12F
14(D)同樓上
02/17 14:24, 12F
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:25:53 ※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:29:22
→
02/17 14:28, , 13F
在DS裡binomial heap是insert和combine "tree"是O(1) a
02/17 14:28, 13F
→
02/17 14:28, , 14F
ctual and amortized
02/17 14:28, 14F
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:35:05
→
02/17 14:36, , 15F
11b 還要maintain last還是O(n) E確認空只要O(1)
02/17 14:36, 15F
謝謝j大! b選項maintain last可以再解釋一下嗎 ※ 編輯: yaxauw (140.112.25.108), 02/17/2016 14:42:43
→
02/17 14:45, , 16F
把最大刪除=刪last node 但single link不知道前一點
02/17 14:45, 16F
→
02/17 14:46, , 17F
所以要花O(n)去找到下一個last node阿
02/17 14:46, 17F
再搭配筆記懂了 謝謝講解 ※ 編輯: 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
推
02/17 15:04, , 18F
感覺第5題還是沒有一個比較合理的解釋
02/17 15:04, 18F
應該就是O(1)? http://imgur.com/QFe0KRe
※ 編輯: yaxauw (140.112.25.108), 02/17/2016 15:22:06
推
02/17 15:46, , 19F
他是問假設insert很少被called 那f heap 的各種operation
02/17 15:46, 19F
→
02/17 15:46, , 20F
的amortized time complexity吧 還是我理解有誤
02/17 15:46, 20F
→
02/17 15:47, , 21F
我知道insert是O(1)沒錯
02/17 15:47, 21F
→
02/17 16:16, , 22F
求其他高手解釋了qq
02/17 16:16, 22F
→
02/17 17:30, , 23F
12題 merge要看是不是採用lazy merge吧QQ
02/17 17:30, 23F
推
02/17 17:41, , 24F
第7題10~-2插入 再將-2,-1刪除
02/17 17:41, 24F
→
02/17 17:42, , 25F
應該長這樣?
02/17 17:42, 25F
推
02/17 18:13, , 26F
你這樣external node就不在同一層啦
02/17 18:13, 26F
※ 編輯: yaxauw (140.112.7.214), 02/17/2016 18:28:06
推
02/17 19:14, , 27F
高手好多 感動QQ
02/17 19:14, 27F
→
02/17 19:53, , 28F
沒事 我腦殘了QQ 上面圖也是錯的
02/17 19:53, 28F
→
02/18 00:01, , 29F
F5應該是5唷 不是8
02/18 00:01, 29F
→
02/18 00:06, , 30F
對誒= = 我在講什麼
02/18 00:06, 30F
※ 編輯: yaxauw (140.112.25.108), 02/18/2016 00:06:53
→
02/18 00:11, , 31F
咦 那這樣的話要h=4 F6-1才會是7啊 ；；
02/18 00:11, 31F
推
02/18 00:35, , 32F
如果 insert 很少被 call 那 heap 裡面根本沒什麼元素啊..
02/18 00:35, 32F
※ 編輯: yaxauw (140.112.25.108), 02/18/2016 00:45:28
推
02/18 12:53, , 33F
那感覺就是O(1)了 謝謝F大
02/18 12:53, 33F
推
02/19 21:11, , 34F
02/19 21:11, 34F
‣ 更多 yaxauw 的文章
文章代碼(AID): #1Mm_pfoF (Grad-ProbAsk)
‣ 更多 yaxauw 的文章
文章代碼(AID): #1Mm_pfoF (Grad-ProbAsk)