作者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/cn.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