Re: [理工] 交大 101 資演

看板Grad-ProbAsk作者kather (Kather)時間10年前 (2014/02/11 00:07)推噓7(7推 0噓 7→)

留言14則, 5人參與討論串2/3 (看更多)

※ 引述《olderbrother (大蜘蛛)》之銘言： : 題目 : http://www.lib.nctu.edu.tw/attach/download/id-1532/ : 問題.. 有點多 : 爬文找不到，自己想不通.. 好不容易打完沒有儲存就關掉了哭哭Q_Q 也有一些不會的，請神人補充 : 5. (13)B (14)C (15)C 請問這些複雜度是怎麼求出來的？ (13) 結構如下 node->node->node-> ... ->node 每個node有m/2個元素假設有y個node 且 y * m/2 = n (總個數) 首先要找到x是在哪個node裡面 link-list你只能一個一個找看x值落在哪邊就是哪個node =>O(y) = O(n/m) 找到在哪個node之後因為他是排序過的我們可以用二分法找值看中間的大於等於還是小於x 就決定對左邊還是右邊繼續找找或是return =>O(log(m/2))=O(logm) 共O(n/m + logm) (14) 現在要插入x到此結構中首先一樣先找該插入哪個node =>O(n/m) 再來因為他是array,你插入值之後還要整理 (例如插入0,那麼1,2,3,4...m都要往後位移一格) =>O(m/2) 共O(m+n/m) (15) 同上刪除也要整理 O(m+n/m) : 14. (40)A (41)E (42)B 一樣，這些複雜度是怎麼求出來的？ (40) 先排序 =>O(nlogn) 兩兩相減找最小值 =>O(n) 共O(nlogn) (41) 掃過整條,找最大跟最小值共O(n) (42) 一樣用二分法找值但是多一道程序每次找值都把該值與目標值相減,若比先前減出來的結果還小,儲存該值與結果該值大於小於或等於目標值則往左邊list或右邊list或直接return 如此一來做完後共O(logn) : 16. (46)C (47)B (48)B 這些答案不知道怎麼出來的 @@ 題目說最短路徑中相距最長的兩個點為optmal(這兩點要能相連) (46) 單源最短路徑 Dijstra=>greedy=>C (47) 用floyd-warshal推出來應該是B (48) 1到4已經是2了就算繞路走最好也只會是1+1 選2即可不必再用f-w推.. : 17. (49)B (50)E (51)E N=10 就湊不出答案了@@ 不知道這答案怎麼出來的不知道原理是甚麼,但是列表湊數字可以找到兩題的答案請神人補充... (49) a=5 , Bino(a,3)=10 b=1 , Bino(b,2)=0 c=0 , Bino(c,1)=0 相加=10 a>b>c>=0 選B:a+b=6 (50) a=5 , 10 b=4 , 6 c=2 , 2 相加=18 a>b>c>=0 選E:b=4 (51) 觀察下來E應該是錯的,但是不知道原理 : 18. (52)D 這個 mystery 是 Prim 嘛？ : (53)A 這樣換的話會變成 Dijkstra 嘛？ : (54)E 如果他是 Prim 的話應該是 O(n^2) 那 O(n^2 + (m+n)) 是？ (52) 整份code看下來是Prim的演算法 (53) code變成 v=起始點s 對於v的每個鄰居點w 若w的weight > v的weight+v與w的距離把w的weight更新成 v的weight+v與w的距離把v標記起來 (由於v一開始就是起始點s , v的weight即是v與起始點的距離) 然後再找距離最小且沒有標記的點當v繼續做直到全部的v都標記為止這樣會找到全部的點跟起始點s的距離 (54) 題目應該是要算沒改的那份code 因為他要求精確的值,我們就去追code 第一個for迴圈 =>n次看while while內第一個for迴圈,當整個while做完,會把全部的邊都跑一遍 =>m次 while內第二個for迴圈,這個迴圈跑n次,當整個while(while也n次)做完 =>n^2次共O(n^2+n+m) : 19. (55)E (56)C (57)D 這些答案不知道怎麼出來的？ : 不好意思問題有點多，麻煩大家了 <(_ _)> 看無= = 請神人補充... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.237.41.72 ※ 編輯: kather 來自: 36.237.41.72 (02/11 00:49)

推

h56999

02/11 01:51, , 1^F

02/11 01:51, 1^F

→

h56999

02/11 01:52, , 2^F

02/11 01:52, 2^F

→

h56999

02/11 01:56, , 3^F

02/11 01:56, 3^F