Re: [理工] 102 台大電機丙 資結 對答案

看板Grad-ProbAsk作者 (鍵盤007)時間11年前 (2014/02/24 01:23), 編輯推噓2(2推 0噓 6→)
留言8則, 4人參與, 最新討論串8/18 (看更多)
請問第3題要怎麼算？ 還有第2題和第23題正確的複雜度應該是多少？ 謝謝~ ※ 引述《olderbrother (大蜘蛛)》之銘言： : 題目 : http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/102/102409.pdf : 我寫的答案 : (A:True, B:False, 考卷上是這樣標的...) : 1. B : 2. B : 3. A : 4. B : 5. A : 6. B (感謝 A4P8T6X9 大大) : 7. B : 8. B : 9. B : 10. A : 11. A : 12. A : 13. B : 14. A : 15. B : 16. A : 17. B : 18. B (感謝 a5120265 大大) : 19. A (感謝 A4T8T6X9 大大) : 20. B (感謝 A4T8T6X9 大大) : 21. B : 22. A : 23. B : 24. A : 25. B : 6 19 20 要麻煩大家幫忙湊答案了... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.136.107.253
→
02/24 08:17, , 1F
2.O(n) 23.對兩個點各做一次DFS即可吧。
02/24 08:17, 1F
→
02/24 08:17, , 2F
3.排列有n!種，每種要印出來需要n。
02/24 08:17, 2F
→
02/24 08:54, , 3F
感謝~~!!
02/24 08:54, 3F
→
02/25 22:39, , 4F
不是做DFS巴 是做short path of two vertexs 是O(n^3)
02/25 22:39, 4F
推
02/26 15:48, , 5F
做兩次DFS會快一點吧O(n^2)，當然用Floyid解就是O(n^3)
02/26 15:48, 5F
推
02/26 15:51, , 6F
用DFS做也可以避免graph without weight的狀況
02/26 15:51, 6F
→
02/26 15:53, , 7F
畢竟只是要判斷有沒有相連而已題目應該不要求short path
02/26 15:53, 7F
→
02/26 15:53, , 8F
一點想法　參考參考
02/26 15:53, 8F
‣ 更多 PTT007 的文章
文章代碼(AID): #1J2YwCXo (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 8 之 18 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共18篇)
‣ 更多 PTT007 的文章
文章代碼(AID): #1J2YwCXo (Grad-ProbAsk)