已经在板上爬过文
但有几题还是有疑问想请教各位~
(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我也想知道