作者magic83v (R7)
看板Grad-ProbAsk
標題[理工] 106 成大電通 資結
時間Thu Feb 21 19:57:08 2019
想討論一下選擇題答案
https://i.imgur.com/t1zNRkG.jpg
1.
2. D
3. BC
4. D
第一題剩C能選 但是沒看過bfs的back edge(?
二的a 最差是O(n) 嗎？
感謝各位
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.246.97.245
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1550750231.A.D50.html
1F：推 tataTangQQ: Rule by weight應該就是O(lgn)吧 02/21 21:01
2F：推 CorkiN: 同意樓上 02/21 21:46
3F：→ CorkiN: 第一題，依tree的定義，就是acyclic了，應該不會有back ed 02/21 21:47
4F：→ CorkiN: ge，我不會選它 02/21 21:47
5F：→ magic83v: 有沒有n個點都不同set 的情況 第一次find要找n個set? 02/21 22:22
6F：推 sooge: 第一題A不對嗎？ 02/21 22:44
7F：推 alily86: A對吧 02/22 00:07
8F：→ magic83v: 最快的怪怪的(? 那換成dfs 也對嗎 02/22 00:41
9F：推 sooge: BFS和DFS最快都是V+E 想說怎麼沒人要選 02/22 01:20
10F：→ magic83v: 所以1.A可以 2.A也對嗎q 02/22 13:30
11F：推 alily86: 第四題錯了吧 max heapify最快是nlogn 02/22 14:08
12F：→ magic83v: 4你覺得哪個對 02/22 15:10
13F：推 sooge: 2我不知道 不過4是D沒錯 選項說最快 最快就是不用調把node 02/22 18:43
14F：→ sooge: 檢查一遍而已所以才會是n 02/22 18:43
15F：→ sooge: 問一般的時間複雜度才會是nlgn 02/22 18:43
16F：→ magic83v: ok 感謝各位 02/22 19:39