[理工] 101 台大資工 軟體 數題

[s1020824 (help_qq)]

大家晚安

想請問一下第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://www.ptt.cc/bbs/Grad-ProbAsk/M.1514469004.A.FFD.html
推 TampaBayRays: 4-2 洪逸說c
推 TampaBayRays: 1-2 不是k+1嗎？
我也覺得是k+1 不過看到之前的討論讓我有點不確定
推 winiel559: 1.(2)不就是height=n+1的full bt的leaf數嗎
→ winiel559: 說錯Height=k+1，然後就跟下面證明nlogn下界串起來了
請問要從哪裡串起來 有點不太懂
推 sarsman: 1-3應該可以用decision tree證
好的 我試試看
※ 編輯: 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
→ winiel559: 就是1-3的證明，看一下就知道了@@
好的 謝謝~
推 FRAXIS: 4-2 是C, 因為不用知道元素個數 當插入元素太多的時候
→ FRAXIS: 就把 underlying 的 array 大小加倍之後作 rehash
想順便問一下 如果採rehashing
H1(A)發生overflow 而使用H2(A)
那找B的時候是要用H1(B)還是H2(B)呢
推 kobebset105: 想問4-2 a跟b哪裡錯
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