[理工] 105交大資演

看板Grad-ProbAsk作者 (DAY)時間6年前 (2018/01/06 20:10), 6年前編輯推噓11(11推 0噓 19→)
留言30則, 8人參與, 6年前最新討論串5/10 (看更多)
已經在板上爬過文 但有幾題還是有疑問想請教各位~ (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
推
01/06 21:18, 6年前 , 1F
23題c選項錯在first one
01/06 21:18, 1F
X!懂了感謝d大~
→
01/06 21:19, 6年前 , 2F
最後的E就是在考SAT轉3-SAT的證明啊 不是全部的variab
01/06 21:19, 2F
我了解了!我npc證明看得很少XD，原來還可以這樣考，謝謝回答!!
→
01/06 21:19, 6年前 , 3F
le都從原先的SAT來 會加入Y和~Y 請去翻證明
01/06 21:19, 3F
→
01/06 21:21, 6年前 , 4F
然後25題前面才一篇... 這題在考找共同祖先 不是SCC
01/06 21:21, 4F
推
01/06 21:22, 6年前 , 5F
BFS跑完一輪就是找到一個聯通 還有剩下的點還是白色就是其
01/06 21:22, 5F
我一開始也是這樣想XD不過我覺得樓下N大講得也很對!!謝謝回答
→
01/06 21:22, 6年前 , 6F
他的component在繼續跑BFS這樣
01/06 21:22, 6F
→
01/06 21:22, 6年前 , 7F
DFS和BFS的確都可以找到共同祖先 只要遍歷一遍就知道
01/06 21:22, 7F
我懂了!謝謝N大
→
01/06 21:22, 6年前 , 8F
路上有誰了
01/06 21:22, 8F
※ 編輯: justlike68 (36.239.61.156), 01/06/2018 21:38:35 ※ 編輯: justlike68 (36.239.61.156), 01/06/2018 21:40:58
推
01/06 21:41, 6年前 , 9F
23-a是說如果primary key一樣，要再比secondary key才
01/06 21:41, 9F
→
01/06 21:42, 6年前 , 10F
可插入pivot
01/06 21:42, 10F
※ 編輯: 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
推
01/06 22:15, 6年前 , 11F
23-c 我跟樓主的問題一樣 但我還沒想通><"
01/06 22:15, 11F
因為有相同key值的話他會跨過去就不是stable了~謝謝樓下w大!
推
01/06 22:16, 6年前 , 12F
32我是理解成再插入一個元素需要1/(1-n/m)的空間(cost)
01/06 22:16, 12F
推
01/06 22:21, 6年前 , 13F
是因為"等於"的時候也會插進去 的關係嗎
01/06 22:21, 13F
推
01/06 22:31, 6年前 , 14F
題目有假設是uniform hash，所以應該不用擔心碰撞問題
01/06 22:31, 14F
推
01/07 01:33, 6年前 , 15F
32 uniform不是不碰撞 perfect才是
01/07 01:33, 15F
→
01/07 01:34, 6年前 , 16F
令a=n/m
01/07 01:34, 16F
→
01/07 01:35, 6年前 , 17F
那你的insert cost就會是
01/07 01:35, 17F
→
01/07 01:35, 6年前 , 18F
1+a+a^2+a^3+...
01/07 01:35, 18F
→
01/07 01:36, 6年前 , 19F
因為在open addr情況下再分配都會有a的機率再碰撞
01/07 01:36, 19F
→
01/07 01:37, 6年前 , 20F
答案就是等比公式1/1-a
01/07 01:37, 20F
推
01/07 01:40, 6年前 , 21F
60的A就是定義而已可以去翻書
01/07 01:40, 21F
→
01/07 01:41, 6年前 , 22F
E是錯在最後一句all from original clause
01/07 01:41, 22F
→
01/07 01:42, 6年前 , 23F
因為任何CNF要轉3-CNF都需要自己加新的logic var進去
01/07 01:42, 23F
→
01/07 01:43, 6年前 , 24F
更正是任何>3的CNF
01/07 01:43, 24F
→
01/07 01:46, 6年前 , 25F
沒看到上面有人講60獻醜了QQ
01/07 01:46, 25F
推
01/07 13:06, 6年前 , 26F
回樓上 23的c舉一個有同個primary key的例子去排 例如 1
01/07 13:06, 26F
→
01/07 13:06, 6年前 , 27F
5 5* 會發現j指標應該要指向5才不會unstable 而照題意j
01/07 13:06, 27F
→
01/07 13:06, 6年前 , 28F
指標指向的是1 所以是false
01/07 13:06, 28F
感謝以上各位大大回答!!!就不一一回覆了抱歉>< ※ 編輯: 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
→
01/07 22:05, 6年前 , 29F
原來是等比數列，謝謝n大!
01/07 22:05, 29F
推
01/09 14:32, 6年前 , 30F
24我也想知道
01/09 14:32, 30F
‣ 更多 justlike68 的文章
文章代碼(AID): #1QKBotFx (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 5 之 10 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共10篇)
‣ 更多 justlike68 的文章
文章代碼(AID): #1QKBotFx (Grad-ProbAsk)