[理工] 106 成大电通资结 magic83v PTT批踢踢实业坊

楼主: magic83v (R7) 2019-02-21 19:57:08

想讨论一下选择题答案
https://i.imgur.com/t1zNRkG.jpg
1.
2. D
3. BC
4. D
第一题剩C能选但是没看过bfs的back edge(?
二的a 最差是O(n) 吗？
感谢各位

作者: tataTangQQ (TaTa) 2019-02-21 21:01:00

Rule by weight应该就是O(lgn)吧

作者: CorkiN (柯基) 2019-02-21 21:46:00

同意楼上第一题，依tree的定义，就是acyclic了，应该不会有back edge，我不会选它

楼主: magic83v (R7) 2019-02-21 22:22:00

有没有n个点都不同set 的情况第一次find要找n个set?

作者: sooge (老衲) 2019-02-21 22:44:00

第一题A不对吗？

作者: alily86 (lily) 2019-02-22 00:07:00

A对吧

楼主: magic83v (R7) 2019-02-22 00:41:00

最快的怪怪的(? 那换成dfs 也对吗

作者: sooge (老衲) 2019-02-22 01:20:00

BFS和DFS最快都是V+E 想说怎么没人要选

楼主: magic83v (R7) 2019-02-22 13:30:00

所以1.A可以 2.A也对吗q

作者: alily86 (lily) 2019-02-22 14:08:00

第四题错了吧 max heapify最快是nlogn

楼主: magic83v (R7) 2019-02-22 15:10:00

4你觉得哪个对

作者: sooge (老衲) 2019-02-22 18:43:00

2我不知道不过4是D没错选项说最快最快就是不用调把node检查一遍而已所以才会是n问一般的时间复杂度才会是nlgn

楼主: magic83v (R7) 2019-02-22 19:39:00

ok 感谢各位

继续阅读