› 看板 Grad-ProbAsk 關於我們 聯絡資訊
作者Byzantin (拜占庭)
看板Grad-ProbAsk
標題Re: [理工] 100成大資工 DS＆Algo(資結)
時間Thu Jan 12 21:54:50 2012
※ 引述《genius945 (添財)》之銘言： : http://0rz.tw/SkLcE 題目 : 看板上好像只有去年考完有人討論... : 一堆都不會...整個亂寫 : 答案 PO上來請各位幫忙修正&指導 = = : 1. : (a)Binary search tree 我覺得是AVL-tree : (b)B tree of order 3 (2-3 tree) : (c)Max Heap(binary) : 2. : (a) 不會...瞎寫了一個code後來發覺不是O(lgn) : 所以(b)也不甭提了... : 3. : 這題好難,我幾乎沒一個是確定的都亂矇 : a-6 : b-2 : c-9 : d-7 我也都不太確定 但只有(d)跟你不同我選(1) : e-4 : f-3 : 4.θ(nloglogn) : 5. : 這題應該會有不同答案吧 : 給左右給0或1或是合併次序 : 我做的是 : a:01 : b:0000 : c:001 : d:101 : e:11 : f:0001 : g:100 : 6. : 不會 : 一開始看到複雜度想說先做kruskal's algo O(V^2logV) : 再搭個BFS之類的 : 但後來想想有邊在MST並不能保證此邊是這兩點的最短距離= = : 我就掰了 Orz 應是Johnson's algorithm : 7. : 我的想法是 : step1.做類似counting sort的動作,計算1~k各有幾個 : 假設這n個int存在int[n] : 建count[k],初值皆為0 : for i = 1 to n : count[int[i]]++ : O(n) : step2.建立一個sum[k],存count[1]+....+count[i]之sum : sum[1]=count[1] : for i = 2 to k : sum[i]=sum[i-1]+count[i] : O(k) : 時間複雜度為O(n+k) : 若要知道多少個int在range a~b : 則只要 return (sum[b]-sum[a-1])即可 故為O(1) 其餘沒回覆的，你有寫的我的答案都相同，你不會的我也不會囧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.104.205
推 justbelieve:AVL+1,BST不是長a這個樣子 01/12 22:01
※ 編輯: Byzantin 來自: 118.169.104.205 (01/12 22:02)
推 genius945:YES 是AVL 感謝感謝 01/12 22:04
→ genius945:剛又看了一下,3.d確實應該選1@@" 我錯好慘= = 01/12 22:06
推 pikachu123:2.那題是corman習題 在CH14 解答很長... 01/12 22:16
→ pikachu123:每個node要記錄 3個東西 Mingap[x] Minval[x] 01/12 22:18
→ pikachu123:maxval[x] 01/12 22:19
→ pikachu123:上有有證明加入額外資訊不會讓 紅黑樹的插入來到 01/12 22:20
→ pikachu123:超過O(logn) 你在插入的時候就會一並更心這些資訊 01/12 22:21
推 pikachu123:當初看到這題完全沒感覺.... 跑去看解答= = 01/12 22:26
→ Byzantin:第二題考試碰到直接放棄了吧XD 01/12 22:30
推 genius945:第二題我也決定放棄! 平時看看就好考試無法= = 01/12 22:31
→ genius945:剛借到書了XD 我想問一下Johnson's algo那題兩位會怎麼 01/12 22:31
→ genius945:寫? 有負邊的解決方式也會寫嗎..... 01/12 22:32
推 pikachu123:6.我覺得是dijkstra 他用Fibonacci Heap mantain 01/12 22:34
→ pikachu123:它的複雜度O(E+VlogV) 每個點都跑一次就 O(VE+V^2logV) 01/12 22:36
→ Byzantin:第六題有說是all pairs哦 01/12 22:37
→ Byzantin:阿沒看到你說每個點跑一次@@ 01/12 22:38
推 pikachu123:你dijkstra每個點都跑一次不就all pair 01/12 22:38
推 pikachu123:其實joshson就是bellman-ford先把負邊改掉 01/12 22:48
→ pikachu123:再用我說的每個點都跑一次dijkstra 01/12 22:49
推 genius945:負邊怎麼改那邊看不太懂欸..所以才問說大大是不是都寫QQ 01/12 22:57
推 pikachu123:負邊你先跑bellman-ford會得到S到所有點的距離 01/12 22:59
→ pikachu123:然後每個邊W(u,v)+u,v 2個最短距離的差值 01/12 23:01
→ genius945:好像有點懂 感謝了!! 01/12 23:37
→ sneak: AVL+1,BST不是 https://daxiv.com 09/11 14:45