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

[pig456654 (神奇)]

※ 引述《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
推 BuliBuchi:第二題我知道問題在哪了 感謝
推 lexa:我查到跳表的插入是O(logn)耶 這麼說2.(D)應該也是錯的?
他這裡沒有特別說的話 我覺得應該就算正常的
所以應該可以吧@@
※ 編輯: pig456654       來自: 114.36.66.208        (01/24 01:28)
推 QDR18:可是學生的id都是不相同吧 這樣就不會有穩不穩定的問題吧?
→ pig456654:我也是這樣想 所以快速排序可以用了？
推 monkeyleo:不好意思順便請問一下為什麼3是C阿？@@
→ monkeyleo:請問是因為goo本身就是n 套上最外面的loop所以是n^2嗎？
推 BuliBuchi:內層做O(i(1+1/2+1/4+...))=O(2i)
→ BuliBuchi:外層就做O(2(1+2+...+n))=O(n^2)
推 lexa:請問7.(B)為何是錯的呢? 要先搜到那學生的資料不就要O(n)嗎?
→ pig456654:因為DLL知道前跟後的node 所以直接修改指標即可
推 BuliBuchi:我突然覺得第二題是D耶XD
→ BuliBuchi:如果A錯 不就表示可以在O(logn)實作
推 BuliBuchi:而且link list不是本來就不能做binary search嗎
→ BuliBuchi:題目又有說一句any list operation都kept O(1)
推 cksh8008:覺得是E 因為是singly linked list
→ cksh8008:是可以直接找到tail 但如果直接刪除tail就沒tail了
→ cksh8008:需要花O(n)的時間從head找到tail前一個當tail才有
→ pig456654:應該是E 我後來又想了一下因為題目説最大在tail
→ pig456654:所以要先找到第二大的接地 應該是O(n）
推 BuliBuchi:原來如此
→ pig456654:D選項我覺得如果要差入在最大的前一個還是要O(n)
→ pig456654:他説的list operation應該是指指標的刪除挪動之類的吧
推 lexa:同意2是E  p大你說7B錯的原因我還是看不太懂...
→ lexa:你是說不用考慮去找那學生的record所花的時間嗎?
→ pig456654:要循序找是因為不知道前一個節點是誰 但DLL可以直接知道
→ pig456654:前一個節點 找到那比原本要刪的資料時間要算嗎QQ
→ pig456654:如果要我也不知道了耶 感覺題目重點不是在問這個XD
→ lexa:是喔  我是有算進去所以覺得B對啦  選項也看不出算不算...
→ cksh8008:第七我是選A錯，B對..
→ cksh8008:覺得A錯是覺得不是因為是unstable 而是因為以排序好了
→ cksh8008:用quick sort會O(n^2)
→ cksh8008:認為B對的原因：雖然是Double linked list
→ cksh8008:但不知道是刪除哪個 還是要線性搜尋到該點
→ cksh8008:所以是O(n)+O(1) => O(n)
推 houseuse616:c大的想法跟我一樣
→ houseuse616:問個笨問題，請問一下第六題的C 哪裡錯啊??
推 gn01262438:可以問一下第5題嗎 101的 有點搞不懂他的需求
推 c5onb:6c  foo(i*i)需要O(n^4)  所以總共要O(n^5)喔
推 gn01262438:101第9題似乎沒有E  我用之前有人講的那個程式去try的
→ gn01262438:delete 10之後 32 44 50 是紅的
→ pig456654:還是不知道怎做T__T
推 pippen6668:想請問最後一題(11)的 要怎麼解出來 想好久@@
→ pippen6668:是比他小的英文 都可以加進來嗎?