[理工] 資演 成大109 資料結構第二題+對答案

[try66889 (貓貓只求黑琴ㄍㄟˋ婚 )]

發現版上好像沒有參考答案想說和大家對答案看看 > <
題目:https://reurl.cc/OqZDAA

A.資料結構

1.TFFFT
2.這題不知道怎麼做QQ 在想題目的意思是不是在問u個key K
  放到m個bucket發生碰撞的機率?
  自己是寫1-[m(m-1)(m-2)...(m-u+1)]/m^u
  不過不是很有信心...QQ
3.64

B.演算法

1.TF
2.θ(nloglogn)
3.median-of-medians做
4.<0,1,0,1,0,1>
5.不適用Master Theory，用展開帶入法 θ(n^3˙loglogn)

有錯誤的地方再麻煩大家指正惹> <
謝謝大家~


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.191.76 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1608212284.A.1F8.html
※ 編輯: try66889 (114.32.191.76 臺灣), 12/17/2020 21:42:47
推 jay010540: 我也有寫答案跟你的都一樣 不過資結第二題我的答案是(n
→ jay010540: -u)/(n*m^u)
→ jay010540: 但是我覺得我應該是錯的@@
感謝j大 OWO 方便請問j大資結第二題是怎麼考慮的嗎 > <?
想說聽聽看大家的想法 > <
※ 編輯: try66889 (114.32.191.76 臺灣), 12/17/2020 23:30:47
→ mathtsai: 想問B.2是怎麼算的
→ mathtsai: 順便請問5是怎麼算的QQ
第二題我是這樣做～
https://i.imgur.com/tePGKIs.jpg
第五題～
https://i.imgur.com/klUzXiW.jpg
※ 編輯: try66889 (114.32.191.76 臺灣), 12/18/2020 01:48:44
→ mathtsai: 感謝!
推 jimmylin1024: 想問資結第一題的第一小題為什麼是True呢？open add
→ jimmylin1024: ressing 的comparison次數是 1/alpha x ln(1/1-alph
→ jimmylin1024: a) ，alpha是load factor 。這樣的話如果load facto
→ jimmylin1024: r接近1 ，comparison 次數不就會變得比O(n)大很多嗎
→ jimmylin1024: （假設n是已經存入hash table的element次數）
不過全部insert的Data是n個，最壞應該就把每個Data search一次~
※ 編輯: try66889 (114.32.191.76 臺灣), 12/18/2020 10:35:48