作者justlike68 (DAY)
看板Grad-ProbAsk
标题[理工] 105交大资演
时间Sat Jan 6 20:10:28 2018
已经在板上爬过文
但有几题还是有疑问想请教各位~
(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
先谢谢各位神人了~~
-----
Sent from JPTT on my Samsung SM-J710GN.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.239.61.156
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1515240631.A.3FB.html
1F：推 djmez: 23题c选项错在first one01/06 21:18
X!懂了感谢d大~
2F：→ NCTUFAIWEN: 最後的E就是在考SAT转3-SAT的证明啊 不是全部的variab01/06 21:19
我了解了!我npc证明看得很少XD，原来还可以这样考，谢谢回答!!
3F：→ NCTUFAIWEN: le都从原先的SAT来 会加入Y和~Y 请去翻证明01/06 21:19
4F：→ NCTUFAIWEN: 然後25题前面才一篇... 这题在考找共同祖先 不是SCC01/06 21:21
5F：推 djmez: BFS跑完一轮就是找到一个联通 还有剩下的点还是白色就是其01/06 21:22
我一开始也是这样想XD不过我觉得楼下N大讲得也很对!!谢谢回答
6F：→ djmez: 他的component在继续跑BFS这样 01/06 21:22
7F：→ NCTUFAIWEN: DFS和BFS的确都可以找到共同祖先 只要遍历一遍就知道01/06 21:22
我懂了!谢谢N大
8F：→ NCTUFAIWEN: 路上有谁了01/06 21:22
※ 编辑: justlike68 (36.239.61.156), 01/06/2018 21:38:35
※ 编辑: justlike68 (36.239.61.156), 01/06/2018 21:40:58
9F：推 winiel559: 23-a是说如果primary key一样，要再比secondary key才01/06 21:41
10F：→ winiel559: 可插入pivot01/06 21:42
※ 编辑: justlike68 (36.239.61.156), 01/06/2018 21:42:50
※ 编辑: justlike68 (36.239.61.156), 01/06/2018 21:43:35
※ 编辑: justlike68 (36.239.61.156), 01/06/2018 21:44:23
11F：推 moneylon: 23-c 我跟楼主的问题一样 但我还没想通><"01/06 22:15
因为有相同key值的话他会跨过去就不是stable了~谢谢楼下w大!
12F：推 sarsman: 32我是理解成再插入一个元素需要1/(1-n/m)的空间(cost)01/06 22:16
13F：推 moneylon: 是因为"等於"的时候也会插进去 的关系吗01/06 22:21
14F：推 sarsman: 题目有假设是uniform hash，所以应该不用担心碰撞问题01/06 22:31
15F：推 nat99up: 32 uniform不是不碰撞 perfect才是01/07 01:33
16F：→ nat99up: 令a=n/m01/07 01:34
17F：→ nat99up: 那你的insert cost就会是01/07 01:35
18F：→ nat99up: 1+a+a^2+a^3+...01/07 01:35
19F：→ nat99up: 因为在open addr情况下再分配都会有a的机率再碰撞01/07 01:36
20F：→ nat99up: 答案就是等比公式1/1-a01/07 01:37
21F：推 nat99up: 60的A就是定义而已可以去翻书01/07 01:40
22F：→ nat99up: E是错在最後一句all from original clause01/07 01:41
23F：→ nat99up: 因为任何CNF要转3-CNF都需要自己加新的logic var进去01/07 01:42
24F：→ nat99up: 更正是任何>3的CNF01/07 01:43
25F：→ nat99up: 没看到上面有人讲60献丑了QQ01/07 01:46
26F：推 wsp50317: 回楼上 23的c举一个有同个primary key的例子去排 例如 101/07 13:06
27F：→ wsp50317: 5 5* 会发现j指标应该要指向5才不会unstable 而照题意j01/07 13:06
28F：→ wsp50317: 指标指向的是1 所以是false01/07 13:06
感谢以上各位大大回答!!!就不一一回覆了抱歉><
※ 编辑: justlike68 (1.175.153.74), 01/07/2018 13:13:14
※ 编辑: justlike68 (1.175.153.74), 01/07/2018 13:13:46
※ 编辑: justlike68 (1.175.153.74), 01/07/2018 13:38:56
29F：→ sarsman: 原来是等比数列，谢谢n大! 01/07 22:05
30F：推 Dora5566: 24我也想知道 01/09 14:32