[理工] 108電機丙 資結對答案

看板Grad-ProbAsk作者 (Mistel)時間6年前 (2019/12/23 17:02), 6年前編輯推噓4(4推 0噓 28→)
留言32則, 6人參與, 6年前最新討論串1/1
硬體直接崩潰，就不對答案了.. 1.F 2.T 3.F 4.T 5.T 6.F 7.T 8.F 9.F 10.F 11.ABCDE 12.BCDE 13.BCD 14.BC 15.CD 16.AB 最後一題B選項完全不知道是什麼 另外也不清楚是非題第7題這樣敘述該是對還是錯 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.243.184 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1577091770.A.A30.html ※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 17:07:57 ※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 17:08:28 ※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 17:09:32 ※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 17:09:56
推
12/23 18:42, 6年前 , 1F
12 E AVL tree delete rotation 是O(n)
12/23 18:42, 1F
感謝，發現E應該是錯的，不過他應該是考single rotation跟double rotation？ 所以正確應該改成 one single rotation or double rotation....
→
12/23 18:44, 6年前 , 2F
14 ABD 都會因為一開始是小到大或大到小而sensitive
12/23 18:44, 2F
→
12/23 18:44, 6年前 , 3F
所以是CE吧
12/23 18:44, 3F
selection sort無論input data是什麼都是O(n^2)吧？ Radix sort我是覺得不知道input data range 算不算sensitive所以沒選
→
12/23 18:47, 6年前 , 4F
其他的我13選BE 15選CE 16選ABD 然後是非都跟你一樣
12/23 18:47, 4F
13.E只講directed沒講到acylic不知道能不能選？ C我選是因為DFS要用到遞迴，D是因為BFS可以在無權圖上找到最短邊，而且楓葉本有提到Di jkstra's是從BFS延伸的（page.594） 16.D請問大大複雜度算出來是多少呢？ ※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 19:06:30 ※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 19:06:53
→
12/23 19:22, 6年前 , 5F
13 14你應該沒錯 我看錯了
12/23 19:22, 5F
→
12/23 19:41, 6年前 , 6F
16 AB沒錯
12/23 19:41, 6F
→
12/23 19:48, 6年前 , 7F
目前不一樣的就是 15 D quadratic 會有probe不到的問
12/23 19:48, 7F
→
12/23 19:48, 6年前 , 8F
題 E 我也不確定
12/23 19:48, 8F
→
12/23 19:53, 6年前 , 9F
拍謝剛剛邊吃飯邊看 現在才回到家找之前寫的答案 所以
12/23 19:53, 9F
→
12/23 19:53, 6年前 , 10F
錯有點多XD 你可以修掉沒關係
12/23 19:53, 10F
感謝j大幫忙對答案！ 目前修改成這樣，不確定的我先標起來了 https://i.imgur.com/RQi994W.jpg
15我覺得j大是對的，E選項我再查查有沒有課文是有講過 ※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 21:57:05
推
12/23 22:27, 6年前 , 11F
AVL 2 rotation 有例子嗎 ?
12/23 22:27, 11F
是指double rotation (RL,LR), single rotation (RR,LL) one single rotation意思是一個RR,LL的rotation，這樣就錯了
→
12/23 22:28, 6年前 , 12F
16 的B是false，楓葉本有
12/23 22:28, 12F
請問b大連CLRS都寫完了嗎QQ? 太強了...
→
12/23 22:32, 6年前 , 13F
我覺得 4 是 F (平均約n) ,6 T
12/23 22:32, 13F
https://i.imgur.com/7Nz233Y.jpg
4.參考洪逸第四章 6.我認為錯是錯在rehashing跟chain都是碰撞的解決方法，而如果chain會使一個鏈結過長 ，那代表hashing function本身就有問題了，所以應該改善hashing function才對
→
12/23 22:33, 6年前 , 14F
16 這樣的話好像只剩 A，但又覺得好像不包含合併時間
12/23 22:33, 14F
→
12/23 22:34, 6年前 , 15F
又或是 cut the problem 的時間已經包含合併的時間了?
12/23 22:34, 15F
不一定吧？合併成本可能低於切割時間，所以在notation下我們就看不出來了~ ※ 編輯: mistel (223.137.243.184 臺灣), 12/24/2019 12:02:05
→
12/24 12:02, 6年前 , 16F
答案晚上一併更新~
12/24 12:02, 16F
→
12/24 12:33, 6年前 , 17F
4. 的確，之前說n有點太隨便了，不過題目是說 1/4 of n
12/24 12:33, 17F
→
12/24 12:33, 6年前 , 18F
(n+1)/2 的話接近 n*(1/2)，不知道這有沒有差
12/24 12:33, 18F
→
12/24 12:34, 6年前 , 19F
6 的話改善 hash function 應該同 rehashing ?
12/24 12:34, 19F
→
12/24 12:35, 6年前 , 20F
沒人寫得完CLRS吧，沒意義
12/24 12:35, 20F
→
12/24 12:35, 6年前 , 21F
4.題意看起來是說n/4？還是我搞錯了
12/24 12:35, 21F
→
12/24 12:51, 6年前 , 22F
我是想說單純只論insert和delete，link list跟array比較
12/24 12:51, 22F
→
12/24 12:51, 6年前 , 23F
的話，前者只要O(1)後者要O(n)，但仔細看看題目說到n/4好
12/24 12:51, 23F
→
12/24 12:51, 6年前 , 24F
像主要錯在這邊？
12/24 12:51, 24F
→
12/24 13:56, 6年前 , 25F
可是我在網路上看Horner’s method是n^2耶QQ
12/24 13:56, 25F
→
12/24 13:56, 6年前 , 26F
16的A 網路上也有PPT是寫logn
12/24 13:56, 26F
→
12/24 14:02, 6年前 , 27F
恩恩 4應該是錯在n/4了 Horner best 是O(logn) worst
12/24 14:02, 27F
→
12/24 14:02, 6年前 , 28F
才是n^2
12/24 14:02, 28F
→
12/24 14:04, 6年前 , 29F
*O(nlogn)
12/24 14:04, 29F
推
01/17 18:53, 7年前 , 30F
16. C如果是python的話那個迴圈會跑7次
01/17 18:53, 30F
推
01/18 20:10, 6年前 , 31F
3.是true 只要找到存在即可
01/18 20:10, 31F
→
01/27 18:00, 6年前 , 32F
3是true沒錯 感謝
01/27 18:00, 32F
‣ 更多 mistel 的文章
文章代碼(AID): #1U08Awem (Grad-ProbAsk)