作者s1020824 (help_qq)
看板Grad-ProbAsk
標題[理工] 101 台大資工 軟體 數題
時間Thu Dec 28 21:50:00 2017
大家晚安
想請問一下第2. 3. 4-2. 5題
http://i.imgur.com/Y7gDbtU.jpg
第二題我算是(K+1)!
但爬文看了先前的討論看到有些人也覺得答案可能是2^k
不知道哪一個才是正確的呢
第三題是直接找一個comparison based的sorting解嗎
第4-2題我覺得是c
不過看之前的討論似乎也沒有定論
http://i.imgur.com/FrmrxQo.jpg
第五題就不知道在幹嘛qq
請大大們解答了
大家加油
-----
Sent from JPTT on my HTC_M9u.
--
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.225.88
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1514469004.A.FFD.html
1F：推 TampaBayRays: 4-2 洪逸說c 12/28 22:05
2F：推 TampaBayRays: 1-2 不是k+1嗎？ 12/28 22:20
我也覺得是k+1 不過看到之前的討論讓我有點不確定
3F：推 winiel559: 1.(2)不就是height=n+1的full bt的leaf數嗎 12/28 22:31
4F：→ winiel559: 說錯Height=k+1，然後就跟下面證明nlogn下界串起來了 12/28 22:32
請問要從哪裡串起來 有點不太懂
5F：推 sarsman: 1-3應該可以用decision tree證 12/28 22:50
好的 我試試看
※ 編輯: s1020824 (218.187.81.127), 12/28/2017 23:12:01
※ 編輯: s1020824 (218.187.81.127), 12/28/2017 23:14:22
※ 編輯: s1020824 (218.187.81.127), 12/28/2017 23:14:42
6F：→ winiel559: 就是1-3的證明，看一下就知道了@@ 12/29 00:06
好的 謝謝~
7F：推 FRAXIS: 4-2 是C, 因為不用知道元素個數 當插入元素太多的時候 12/29 07:51
8F：→ FRAXIS: 就把 underlying 的 array 大小加倍之後作 rehash 12/29 07:52
想順便問一下 如果採rehashing
H1(A)發生overflow 而使用H2(A)
那找B的時候是要用H1(B)還是H2(B)呢
9F：推 kobebset105: 想問4-2 a跟b哪裡錯 12/29 09:49
a跟b是正確的
※ 編輯: s1020824 (60.251.225.88), 12/29/2017 10:04:09
※ 編輯: s1020824 (60.251.225.88), 12/29/2017 10:08:48
※ 編輯: s1020824 (60.251.225.88), 12/29/2017 10:09:12