[理工] 105交大資演

[justlike68 (DAY)]

已經在板上爬過文
但有幾題還是有疑問想請教各位~

(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://www.ptt.cc/bbs/Grad-ProbAsk/M.1515240631.A.3FB.html
推 djmez: 23題c選項錯在first one
X!懂了感謝d大~
→ NCTUFAIWEN: 最後的E就是在考SAT轉3-SAT的證明啊 不是全部的variab
我了解了!我npc證明看得很少XD，原來還可以這樣考，謝謝回答!!
→ NCTUFAIWEN: le都從原先的SAT來 會加入Y和~Y 請去翻證明
→ NCTUFAIWEN: 然後25題前面才一篇... 這題在考找共同祖先 不是SCC
推 djmez: BFS跑完一輪就是找到一個聯通 還有剩下的點還是白色就是其
我一開始也是這樣想XD不過我覺得樓下N大講得也很對!!謝謝回答
→ djmez: 他的component在繼續跑BFS這樣
→ NCTUFAIWEN: DFS和BFS的確都可以找到共同祖先 只要遍歷一遍就知道
我懂了!謝謝N大
→ NCTUFAIWEN: 路上有誰了
※ 編輯: justlike68 (36.239.61.156), 01/06/2018 21:38:35
※ 編輯: justlike68 (36.239.61.156), 01/06/2018 21:40:58
推 winiel559: 23-a是說如果primary key一樣，要再比secondary key才
→ winiel559: 可插入pivot
※ 編輯: 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
推 moneylon: 23-c 我跟樓主的問題一樣 但我還沒想通><"
因為有相同key值的話他會跨過去就不是stable了~謝謝樓下w大!
推 sarsman: 32我是理解成再插入一個元素需要1/(1-n/m)的空間(cost)
推 moneylon: 是因為"等於"的時候也會插進去 的關係嗎
推 sarsman: 題目有假設是uniform hash，所以應該不用擔心碰撞問題
推 nat99up: 32 uniform不是不碰撞 perfect才是
→ nat99up: 令a=n/m
→ nat99up: 那你的insert cost就會是
→ nat99up: 1+a+a^2+a^3+...
→ nat99up: 因為在open addr情況下再分配都會有a的機率再碰撞
→ nat99up: 答案就是等比公式1/1-a
推 nat99up: 60的A就是定義而已可以去翻書
→ nat99up: E是錯在最後一句all from original clause
→ nat99up: 因為任何CNF要轉3-CNF都需要自己加新的logic var進去
→ nat99up: 更正是任何>3的CNF
→ nat99up: 沒看到上面有人講60獻醜了QQ
推 wsp50317: 回樓上 23的c舉一個有同個primary key的例子去排 例如 1
→ wsp50317:  5 5* 會發現j指標應該要指向5才不會unstable 而照題意j
→ wsp50317: 指標指向的是1 所以是false
感謝以上各位大大回答!!!就不一一回覆了抱歉><
※ 編輯: 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
→ sarsman: 原來是等比數列，謝謝n大!
推 Dora5566: 24我也想知道