[理工] 108 台大電機丙 複選題

[joywilliamjo (joywilliamjoy)]

複選14、15、16
板上討論很多但沒有個定案
那就再討論一次吧...
https://i.imgur.com/lh19E8H.jpg
14題我的理解是要找worst/best/average case的時間複雜度都是一樣的演算法
E的話我之前上網背的表格時間複雜度都是
O(n*(d+r))所以我覺得答案應該是BCE
15的話BC不知道怎麼解釋
D的話我認為overflow的狀況沒被考慮進去（整個hash table都滿了依然overflow
然後16題
這題我一開始是寫沒答案
CE一定錯
D沒認真算，但有一個for loop兩個while loop估計不會是nlogn
，B的話我覺得不是O(n)就是O(n^n)
怎麼樣也不會到n^2
A我自己覺得應該是nlogn但看板上的討論應該是錯了
不知道為什麼
還希望能大家多多討論
救救沒有讀書會的人QQ

補充一下
13的E應該是對的
上網有查到O(E+V),adjacency list存
我是選CDE
https://i.imgur.com/WSr1iMa.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.74.26.5 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607418006.A.F31.html
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 17:11:17
推 jimmylin1024: 15題 B還是可以用 只是結果好不好的問題 C不會變快
→ jimmylin1024: 因為刪掉資料後會在對應的slot做記號 才不會影響之
→ jimmylin1024: 後的search (才不會還沒probe到要找到資料就因為pro
→ jimmylin1024: be到空的slot 而回傳null ）
所以15比較像CE？
推 jimmylin1024: 13題E是對的 topological sort可以是O(E+V) 但是要
→ jimmylin1024: 對graph做預處理
→ mathtsai: topological sort本來就是O(E+V)啊
→ jimmylin1024: 14題E input 一開始的排列不會影響radix sort 的時
→ jimmylin1024: 間複雜度 因為每一個digit 都一樣會是O(n)
推 jimmylin1024: 16 A 如果你把式子寫成 T(n) = T(n/k) + O(1) k是正
→ jimmylin1024: 整數， 就是O(logn)
了解，用master theory想比較快
是說如果這題直接空白或是寫無解到底是扣兩分還是全錯啊
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 17:50:42
→ aa871220: 15（c) CLRS關於quadratic probing是這樣說的：
→ aa871220: Hash function :h(k,I)=(h’(k)+c1i +c2i^2)mod m
→ aa871220: 要使slot被full use 必須特別挑選c1 c2與m之值
→ aa871220: 換句話說你可以隨便找個反例的slot數量與hash finction
→ aa871220: 更正是D
→ aa871220: （C) 像一樓說的 會加入一個delete node 在原本的slot
→ aa871220: 所以你其他與被刪除的node之proving sequence一樣時 不
→ aa871220: 會改變要probing的數量 所以不會變快 答案應該只有E
總結一下
14.BCE
15.E
16.A
推 jimmylin1024: aa大 這樣的話D選項可以選吧（？）雖然可以找到反例
不行哦，照題目英文翻譯是linear和quadratic要所有情況都能應付，我的理解是有例外
反例這個選項就不能選
→ jimmylin1024:  但是只要特別挑選的話 是可以probe到全部slot 的（
→ jimmylin1024: ？）還是我哪裡有理解錯誤麻煩指正QQ
你這個就比較像
https://i.imgur.com/ALwv421.jpg
比較像英文理解問題而不是觀念理解
QQ
→ aa871220: 該怎麼說 我覺得電機丙的題目很雞掰 有時候要考慮極端情
→ aa871220: 況有時候不用
→ aa871220: 我其實是看題目的語氣決定答案的
→ aa871220: 反正觀念就是上面那些 要選啥就看個人造化了哈哈哈哈
真的覺得有夠麻煩
還有電機丙是非選擇的notation= =
比如說題目最逼近的是O(n)，但要是題目問O(n^n)對不對的話得選對
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 21:12:46