作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 108電機丙 資結對答案
時間Mon Dec 23 17:02:48 2019
硬體直接崩潰，就不對答案了..
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://webptt.com/m.aspx?n=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
1F：推 jeremyyuan: 12 E AVL tree delete rotation 是O(n)12/23 18:42
感謝，發現E應該是錯的，不過他應該是考single rotation跟double rotation？
所以正確應該改成 one single rotation or double rotation....
2F：→ jeremyyuan: 14 ABD 都會因為一開始是小到大或大到小而sensitive12/23 18:44
3F：→ jeremyyuan: 所以是CE吧12/23 18:44
selection sort無論input data是什麼都是O(n^2)吧？
Radix sort我是覺得不知道input data range 算不算sensitive所以沒選
4F：→ jeremyyuan: 其他的我13選BE 15選CE 16選ABD 然後是非都跟你一樣12/23 18:47
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
5F：→ jeremyyuan: 13 14你應該沒錯 我看錯了12/23 19:22
6F：→ jeremyyuan: 16 AB沒錯12/23 19:41
7F：→ jeremyyuan: 目前不一樣的就是 15 D quadratic 會有probe不到的問12/23 19:48
8F：→ jeremyyuan: 題 E 我也不確定12/23 19:48
9F：→ jeremyyuan: 拍謝剛剛邊吃飯邊看 現在才回到家找之前寫的答案 所以12/23 19:53
10F：→ jeremyyuan: 錯有點多XD 你可以修掉沒關係12/23 19:53
感謝j大幫忙對答案！
目前修改成這樣，不確定的我先標起來了
https://i.imgur.com/RQi994W.jpg
15我覺得j大是對的，E選項我再查查有沒有課文是有講過
※ 編輯: mistel (223.137.243.184 臺灣), 12/23/2019 21:57:05
11F：推 ekids1234: AVL 2 rotation 有例子嗎 ?12/23 22:27
是指double rotation (RL,LR), single rotation (RR,LL)
one single rotation意思是一個RR,LL的rotation，這樣就錯了
12F：→ b10007034: 16 的B是false，楓葉本有 12/23 22:28
請問b大連CLRS都寫完了嗎QQ? 太強了...
13F：→ ekids1234: 我覺得 4 是 F (平均約n) ,6 T12/23 22:32
https://i.imgur.com/7Nz233Y.jpg
4.參考洪逸第四章
6.我認為錯是錯在rehashing跟chain都是碰撞的解決方法，而如果chain會使一個鏈結過長
，那代表hashing function本身就有問題了，所以應該改善hashing function才對
14F：→ ekids1234: 16 這樣的話好像只剩 A，但又覺得好像不包含合併時間 12/23 22:33
15F：→ ekids1234: 又或是 cut the problem 的時間已經包含合併的時間了?12/23 22:34
不一定吧？合併成本可能低於切割時間，所以在notation下我們就看不出來了~
※ 編輯: mistel (223.137.243.184 臺灣), 12/24/2019 12:02:05
16F：→ mistel: 答案晚上一併更新~ 12/24 12:02
17F：→ ekids1234: 4. 的確，之前說n有點太隨便了，不過題目是說 1/4 of n 12/24 12:33
18F：→ ekids1234: (n+1)/2 的話接近 n*(1/2)，不知道這有沒有差 12/24 12:33
19F：→ ekids1234: 6 的話改善 hash function 應該同 rehashing ? 12/24 12:34
20F：→ b10007034: 沒人寫得完CLRS吧，沒意義 12/24 12:35
21F：→ b10007034: 4.題意看起來是說n/4？還是我搞錯了 12/24 12:35
22F：→ mistel: 我是想說單純只論insert和delete，link list跟array比較 12/24 12:51
23F：→ mistel: 的話，前者只要O(1)後者要O(n)，但仔細看看題目說到n/4好 12/24 12:51
24F：→ mistel: 像主要錯在這邊？ 12/24 12:51
25F：→ Fanchien: 可是我在網路上看Horner’s method是n^2耶QQ 12/24 13:56
26F：→ Fanchien: 16的A 網路上也有PPT是寫logn 12/24 13:56
27F：→ jeremyyuan: 恩恩 4應該是錯在n/4了 Horner best 是O(logn) worst 12/24 14:02
28F：→ jeremyyuan: 才是n^2 12/24 14:02
29F：→ jeremyyuan: *O(nlogn) 12/24 14:04
30F：推 misaka0120: 16. C如果是python的話那個迴圈會跑7次 01/17 18:53
31F：推 Fanchien: 3.是true 只要找到存在即可 01/18 20:10
32F：→ mistel: 3是true沒錯 感謝 01/27 18:00