作者:
mistel (Mistel)
2019-12-23 17:02:48硬體直接崩潰，就不對答案了..
1.F
2.T
3.F
4.T
5.T
6.F
7.T
8.F
9.F
10.F
11.ABCDE
12.BCDE
13.BCD
14.BC
15.CD
16.AB
最後一題B選項完全不知道是什麼
另外也不清楚是非題第7題這樣敘述該是對還是錯
12 E AVL tree delete rotation 是O(n)14 ABD 都會因為一開始是小到大或大到小而sensitive所以是CE吧其他的我13選BE 15選CE 16選ABD 然後是非都跟你一樣13 14你應該沒錯 我看錯了16 AB沒錯目前不一樣的就是 15 D quadratic 會有probe不到的問題 E 我也不確定拍謝剛剛邊吃飯邊看 現在才回到家找之前寫的答案 所以錯有點多XD 你可以修掉沒關係
我覺得 4 是 F (平均約n) ,6 T16 這樣的話好像只剩 A，但又覺得好像不包含合併時間又或是 cut the problem 的時間已經包含合併的時間了?
作者:
mistel (Mistel)
2019-12-24 12:02:00答案晚上一併更新~
4. 的確，之前說n有點太隨便了，不過題目是說 1/4 of n(n+1)/2 的話接近 n*(1/2)，不知道這有沒有差6 的話改善 hash function 應該同 rehashing ?
沒人寫得完CLRS吧，沒意義4.題意看起來是說n/4？還是我搞錯了
作者:
mistel (Mistel)
2019-12-24 12:51:00我是想說單純只論insert和delete，link list跟array比較的話，前者只要O(1)後者要O(n)，但仔細看看題目說到n/4好像主要錯在這邊？
作者: Fanchien (本丸好可愛) 2019-12-24 13:56:00
可是我在網路上看Horner’s method是n^2耶QQ16的A 網路上也有PPT是寫logn
恩恩 4應該是錯在n/4了 Horner best 是O(logn) worst才是n^2*O(nlogn)