Re: [理工] 100&101台大電機丙-DS

看板Grad-ProbAsk作者 (神奇)時間13年前 (2013/01/24 00:53), 編輯推噓16(16推 0噓 27→)
留言43則, 10人參與, 最新討論串3/19 (看更多)
※ 引述《BuliBuchi (不離不棄)》之銘言： : http://tinyurl.com/cpkzwuq 101 : http://tinyurl.com/cd77xza 100 : 想跟大家對個答案 : 不過寫起來蠻不順的 : 所以有錯請大大指教 : 101 : 單選 : 1~5.AECBD : 多選 : 6.AD : 7.CDE : 8.AB : 9.ADE : 10.CDE : 11.AB : 100 : 單選 : 1~5.EACBD 6看不懂題目.. : 多選 : 7.CDE : 8.BC : 9.E : 10.CDE : 11.ABCD : 12.AE : 13.E : 14.ABCD : 15.ABE : 16.B 我今天寫完101資結 跟大大有不一樣的地方是 單選的第二題: 我選的是A 我的想法是 A應該可以用所謂的Skip List讓他達到O(logn)的時間 至於大大選的E 我想如果HEAD已經是最大排序好的值 的確可以在O(1)時間刪除 還有第七題多選題 我多選了一個A 因為我覺得題目敘述上沒有錯 Quick sort本來就是不穩定 是因為學生ID不會重複 所以沒差嗎哈哈@@ 剩下的都一樣了 至於紅黑樹的刪除 我還是不會 有大大能提供方法嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.36.66.208
推
01/24 01:10, , 1F
第二題我知道問題在哪了 感謝
01/24 01:10, 1F
推
01/24 01:26, , 2F
我查到跳表的插入是O(logn)耶 這麼說2.(D)應該也是錯的?
01/24 01:26, 2F
他這裡沒有特別說的話 我覺得應該就算正常的 所以應該可以吧@@ ※ 編輯: pig456654 來自: 114.36.66.208 (01/24 01:28)
推
01/24 13:23, , 3F
可是學生的id都是不相同吧 這樣就不會有穩不穩定的問題吧?
01/24 13:23, 3F
→
01/24 14:28, , 4F
我也是這樣想 所以快速排序可以用了？
01/24 14:28, 4F
推
01/24 16:28, , 5F
不好意思順便請問一下為什麼3是C阿？@@
01/24 16:28, 5F
→
01/24 16:30, , 6F
請問是因為goo本身就是n 套上最外面的loop所以是n^2嗎？
01/24 16:30, 6F
推
01/24 17:06, , 7F
內層做O(i(1+1/2+1/4+...))=O(2i)
01/24 17:06, 7F
→
01/24 17:08, , 8F
外層就做O(2(1+2+...+n))=O(n^2)
01/24 17:08, 8F
推
01/24 17:57, , 9F
請問7.(B)為何是錯的呢? 要先搜到那學生的資料不就要O(n)嗎?
01/24 17:57, 9F
→
01/24 18:15, , 10F
因為DLL知道前跟後的node 所以直接修改指標即可
01/24 18:15, 10F
推
01/24 18:30, , 11F
我突然覺得第二題是D耶XD
01/24 18:30, 11F
→
01/24 18:30, , 12F
如果A錯 不就表示可以在O(logn)實作
01/24 18:30, 12F
推
01/24 18:48, , 13F
而且link list不是本來就不能做binary search嗎
01/24 18:48, 13F
→
01/24 18:49, , 14F
題目又有說一句any list operation都kept O(1)
01/24 18:49, 14F
推
01/24 19:01, , 15F
覺得是E 因為是singly linked list
01/24 19:01, 15F
→
01/24 19:02, , 16F
是可以直接找到tail 但如果直接刪除tail就沒tail了
01/24 19:02, 16F
→
01/24 19:03, , 17F
需要花O(n)的時間從head找到tail前一個當tail才有
01/24 19:03, 17F
→
01/24 19:13, , 18F
應該是E 我後來又想了一下因為題目説最大在tail
01/24 19:13, 18F
→
01/24 19:14, , 19F
所以要先找到第二大的接地 應該是O(n）
01/24 19:14, 19F
推
01/24 19:22, , 20F
原來如此
01/24 19:22, 20F
→
01/24 19:23, , 21F
D選項我覺得如果要差入在最大的前一個還是要O(n)
01/24 19:23, 21F
→
01/24 19:24, , 22F
他説的list operation應該是指指標的刪除挪動之類的吧
01/24 19:24, 22F
推
01/24 21:32, , 23F
同意2是E p大你說7B錯的原因我還是看不太懂...
01/24 21:32, 23F
→
01/24 21:34, , 24F
你是說不用考慮去找那學生的record所花的時間嗎?
01/24 21:34, 24F
→
01/24 22:21, , 25F
要循序找是因為不知道前一個節點是誰 但DLL可以直接知道
01/24 22:21, 25F
→
01/24 22:24, , 26F
前一個節點 找到那比原本要刪的資料時間要算嗎QQ
01/24 22:24, 26F
→
01/24 22:25, , 27F
如果要我也不知道了耶 感覺題目重點不是在問這個XD
01/24 22:25, 27F
→
01/24 22:40, , 28F
是喔 我是有算進去所以覺得B對啦 選項也看不出算不算...
01/24 22:40, 28F
→
01/24 23:16, , 29F
第七我是選A錯，B對..
01/24 23:16, 29F
→
01/24 23:23, , 30F
覺得A錯是覺得不是因為是unstable 而是因為以排序好了
01/24 23:23, 30F
→
01/24 23:23, , 31F
用quick sort會O(n^2)
01/24 23:23, 31F
→
01/24 23:24, , 32F
認為B對的原因：雖然是Double linked list
01/24 23:24, 32F
→
01/24 23:24, , 33F
但不知道是刪除哪個 還是要線性搜尋到該點
01/24 23:24, 33F
→
01/24 23:25, , 34F
所以是O(n)+O(1) => O(n)
01/24 23:25, 34F
推
01/25 13:49, , 35F
c大的想法跟我一樣
01/25 13:49, 35F
→
01/25 14:00, , 36F
問個笨問題，請問一下第六題的C 哪裡錯啊??
01/25 14:00, 36F
推
01/26 22:40, , 37F
可以問一下第5題嗎 101的 有點搞不懂他的需求
01/26 22:40, 37F
推
01/26 23:14, , 38F
6c foo(i*i)需要O(n^4) 所以總共要O(n^5)喔
01/26 23:14, 38F
推
01/26 23:15, , 39F
101第9題似乎沒有E 我用之前有人講的那個程式去try的
01/26 23:15, 39F
→
01/26 23:17, , 40F
delete 10之後 32 44 50 是紅的
01/26 23:17, 40F
→
01/27 00:49, , 41F
還是不知道怎做T__T
01/27 00:49, 41F
推
01/27 20:36, , 42F
想請問最後一題(11)的 要怎麼解出來 想好久@@
01/27 20:36, 42F
→
01/27 20:38, , 43F
是比他小的英文 都可以加進來嗎?
01/27 20:38, 43F
‣ 更多 pig456654 的文章
文章代碼(AID): #1H01M5GM (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 3 之 19 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共19篇)
‣ 更多 pig456654 的文章
文章代碼(AID): #1H01M5GM (Grad-ProbAsk)