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

[mistel (Mistel)]

硬體直接崩潰，就不對答案了..


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