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