[理工] [資演] 103-台大電機-丙討論

看板Grad-ProbAsk作者ken52011219 (呱)時間9年前 (2017/01/13 15:19)推噓8(8推 0噓 30→)

留言38則, 4人參與討論串1/1

大家好，因為看板上 103 台大電機丙 - 資演好像沒甚麼人在討論因此想來跟大家討論一下各題想法。 1.(20%) http://imgur.com/a/0RmQ3 依題目所提示可以得出以下重點： 1.該 Data Structrue 共兩種 function (1) : insert() (2) : median() // 不用刪除 2.目前總共有 n 個 element in the data structure 3.對於 n 為奇數而言， median() = (n+1) / 2 為偶數而言， median() = n / 2 4.( n/2 + 1 ) th 是最小元素問題【1】，請敘述該 Data Structure 對於該Data Structure而言，分成兩部分討論 1. Insertion()中會包含著判定是否為最小值，若是則會被 insert (n/2+1)th 反之則會將原本的值將插入 n+1 th、，原本minmum swap to (n/2 + 1)th 2. median() 則為上述重點3 的判別式問題【2】， n calls insertion(x) + 亂數calls O(n)次 median() 的時間複雜度 Insertion time complexity 共 n calls 為 O(1*n + x*n) x if 為 unsort array structure , search 為 O(n) if 為 unsort link list . search 為 O(1) if 為 binary search 為 O(log n) if code 有動態紀錄該式 n 的位子為 O(1) median time complexity 為 O(1) 共 n call , 為 O( 1 * n ) Ans O( 1*n + x*n + 1*n ) = O( xn )

推

FRAXIS

01/13 22:17,

01/13 22:17

2. (25%) http://imgur.com/a/Fe9lV (5%)問題【1】題目要將Double hashing 呈現像 linear hashing h(k) = (h_1(k) + ih_2(k)) % m => = (h_1(k) + i * 1 ) % m 令 h_2(k) = 1 即可 (5%)問題【2】 No, uniform 的意義為每個probe sequence 機率都是一樣的，若純談論 double hashing , 則為 yes ，但上題已經將 double hashing 改為 linear hashing 的效能了。 (15%)問題【3】 Pr{X ≧ i } = n/m * (n-1)/(m-1) * ... * (n-i+2) / (m-i+2) ≦ (n/m)^(i-1) = α^(i-1) ∞ m ∞ E[X] = Σ Pr {X ≧ i} = Σ Pr {X ≧ i} + Σ Pr {X ≧ i} i =1 i=1 i>m ∞ ≦ Σ α^(i-1) + 0 i=1 ∞ = Σ α^(i) = 1/ (1-α) 本題小弟已放棄解讀，其證明為楓葉本 11.4 274-275 un-succeful look up = 1/ (1-α) succeful look up = (1/α)ln(1/ (1-α)) 3.(20%) http://imgur.com/a/uLycl

推

FRAXIS

01/13 22:27,

01/13 22:27

→

FRAXIS

01/13 22:27,

01/13 22:27

4.(35%) http://imgur.com/a/kyxuN (5%)問題【a】原文書-312 題目最高比例為 2 ( root 為 1 Black , interal Red node 為 2 ) 最低比例為 0 (5%)問題【b】楓葉本-333 AVL tree of height h has at least F_h node O 0 1 2 3 4 5 6 ╱ ╲ F 1 1 2 3 5 8 13 O O ╱ ╲ ╱ ╲ AVL 高度最多為 5 O O O O ╱ ╲ ╱ ╲ O OO O ╱ O (5%)問題【c】楓葉本-333 AVL-Insert run on an n-node AVL take O(lgn) times and O(1)次 rotation (10%)問題【d】楓葉本-343 14 單元 - Augmenting data structure O(log n) (10%)問題【e】目前我想到的是以binary search AVL ，可是看起來應該沒有那麼簡單

→

FRAXIS

01/13 22:20,

01/13 22:20

O(log n) -- 　　有一個香錦囊，是從一個神話般的守軍的血屍頂上剝下的。那一次我們部隊遭受從未有過的頑強抵抗，我們犧牲了三個艦隊，一個裝甲師和無以數計小組推進的敢死排，才摧毀了那處隘口的碉堡。但是竟然發現，使我們遭受如此慘烈傷亡的守軍，總數只有一人。　　士兵們起鬨地在他胸前發現這枚香袋，大家都相信這是一枚具有神奇力量的護身符。我們把他的頭顱砍斷，取下香袋，剝開，　　裡面一張被血浸紅的宣紙竟用漢字娟娟秀秀四個整齊的楷書寫著－「盼君早歸。」 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.131.84.210 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484291998.A.088.html

→

ken52011219

01/13 15:26, , 1^F

01/13 15:26, 1^F

→

ken52011219

01/13 15:26, , 2^F

01/13 15:26, 2^F

→

ken52011219

01/13 15:27, , 3^F

01/13 15:27, 3^F