[理工] 105交大资演 AAQ8 PTT批踢踢实业坊

[理工] 105交大资演

楼主: AAQ8 (不要就是要) 2019-02-10 16:39:48

https://i.imgur.com/pwob9ds.jpg
https://i.imgur.com/a4sbWMr.jpg
https://i.imgur.com/uM7pTnM.jpg
21的(C)选项
我知道heap的插入和删除都是logn
但merging two min-heap是什么意思
22的(C)选项
Qsort不是还有花O(1)的时间merge吗
为什么可以说不用花时间作merge
25想问(B)(C)错在哪里
麻烦各位
感谢

作者: CorkiN (柯基) 2019-02-10 16:45:00

21那个是说leftist heap，merge就是log(n)

作者: Leaving 2019-02-10 17:58:00

21可以想成2n的array做build heap 所以是O(n)哦看错题目没事

作者: yabi125 (春卷) 2019-02-10 18:58:00

22题有一样的疑问

作者: Leaving 2019-02-10 19:04:00

22不用merge 所有动作都在同一条array中完成的

作者: Kanaheipapa (趴趴) 2019-02-10 20:49:00

25b 应该是都差不多O(V+E)

作者: alen0303 (艾伦零参智商负三) 2019-02-10 20:52:00

25C large资料反而更不适合DFS 需要担心stack overflow

作者: leviliang (levi) 2019-02-10 22:01:00

BFS与DFS另外需要queue与stack排顺序，只有union免

楼主: AAQ8 (不要就是要) 2019-02-10 23:31:00

想请问queue的话没有overflow的问题吗

作者: leviliang (levi) 2019-02-10 23:53:00

一般来说实作上都会做到最大，也就是大小为|V|的阵列，不会给他有机会overflow的。

楼主: AAQ8 (不要就是要) 2019-02-11 10:23:00

我懂了感谢

继续阅读

[理工] 105 电机丙数haniwang [离散] 命题lionccc [理工] 离散 pseudo graph表示ncdonalds123 [理工] 104台大资工计系TonyXIAO [理工] 计系问题求救beatssola 107清大计组kaidi620 [理工] 107交大数学kaidi620 [理工] 107台科数学Marcolod [理工] 台联大106 电子Rexasto [理工] 中兴程式题rustw2010