已經在板上爬過文
但有幾題還是有疑問想請教各位~
(23)(Solved)
http://i.imgur.com/yt7YJqG.jpg
想問的是 :
(a)敘述完全不太清楚他想說什麼
(c)敘述 insertion sort不就是像他說的，插入到前一個比他大的後面嗎，感覺是對的?
(24)
http://i.imgur.com/OnKLHOf.jpg
想問的是上面那兩個圈起來的(c)(d)
(c)是說可用decision tree來考慮comparsion base的sorting 演算法嗎?
(d)non-linear operators不知道想表達什麼?
(25)(Solved)
http://i.imgur.com/EiTi8dw.jpg
想問的是:
(a)爬過文是說因為breath first search可以用來找connect conponent，可以當成一個dis
(32)
http://i.imgur.com/7vFSMgT.jpg
想問的是
我知道hash到空的地方機率是1-n/m，但倒數就不知道是什麼意思了?
(60)(Solved)
http://i.imgur.com/Vr86T7y.jpg
想問的是
(A) A≦B 是指A不會比B難我知道，想問的是這也可以套用在所有情況嗎 ? 像是題目的P≦N
(E)不太明白敘述想考什麼?
對不起問題很多><因為跨考沒有人可以問QQ
先謝謝各位神人了~~

23題c選項錯在first one

最後的E就是在考SAT轉3-SAT的證明啊 不是全部的variable都從原先的SAT來 會加入Y和~Y 請去翻證明然後25題前面才一篇... 這題在考找共同祖先 不是SCC

BFS跑完一輪就是找到一個聯通 還有剩下的點還是白色就是其他的component在繼續跑BFS這樣

DFS和BFS的確都可以找到共同祖先 只要遍歷一遍就知道路上有誰了

23-a是說如果primary key一樣，要再比secondary key才可插入pivot

23-c 我跟樓主的問題一樣 但我還沒想通><"

32我是理解成再插入一個元素需要1/(1-n/m)的空間(cost)

是因為"等於"的時候也會插進去 的關係嗎

題目有假設是uniform hash，所以應該不用擔心碰撞問題

32 uniform不是不碰撞 perfect才是令a=n/m那你的insert cost就會是1+a+a^2+a^3+...因為在open addr情況下再分配都會有a的機率再碰撞答案就是等比公式1/1-a60的A就是定義而已可以去翻書E是錯在最後一句all from original clause因為任何CNF要轉3-CNF都需要自己加新的logic var進去更正是任何>3的CNF沒看到上面有人講60獻醜了QQ

回樓上 23的c舉一個有同個primary key的例子去排 例如 15 5* 會發現j指標應該要指向5才不會unstable 而照題意j指標指向的是1 所以是false

原來是等比數列，謝謝n大!

24我也想知道