作者ko330 (ko330)
看板Grad-ProbAsk
標題[理工] 107台大電機丙 資結對答案
時間Tue Jan 29 16:50:48 2019
如題 有寫這份的希望可以一起檢討
1~5 AABAB
6~10 ABBBA
11~15 BBBAA
16 ABCDE
17 BCD 我知道偵測cycle可以O(n) 但O(V+E)應該是可以選？
18 E
19 D
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.51.188
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548751851.A.8FB.html
※ 編輯: ko330 (223.136.50.221), 01/29/2019 16:54:33
※ 編輯: ko330 (223.136.50.221), 01/29/2019 17:25:53
1F：推 magic83v: 7.8我選AA 有t(node) 找中間相當於二分搜尋的速度01/29 17:35
2F：→ magic83v: 旋轉可能會影響到整棵樹s.t 花O(n)調整應該合理01/29 17:36
3F：→ magic83v: 想問1. 至少修改4個link 是哪4個01/29 17:40
4F：→ magic83v: 17c也看不太懂意思 qq01/29 17:58
7我是想說他沒有說balance 所以worst case斜斜一條找中位數要O(n)
8是說整棵樹的s跟t都可能要改嗎，那可能是O(n)沒錯..
第1我記錯了 是插入才要改4個
17c是考union find吧 一個component當成一個集合
※ 編輯: ko330 (223.136.50.221), 01/29/2019 18:51:47
5F：→ magic83v: 哦對 7A忘記skew的情況01/29 19:08
6F：推 anonimo: 第7題 他說can be found 所以我覺得應該選最小O(logn)01/29 20:21
7F：→ anonimo: 第8題應該不用整顆樹改 只要改做ratation的部分就好01/29 20:23
8F：→ anonimo: *rotation01/29 20:24
第7我是覺得他想考的不是這個耶0.0
第8 rotation可能不只動三個點耶，下面subtree也全部會動到，你寫看看106的11題也是
這樣
※ 編輯: ko330 (114.137.158.87), 01/29/2019 21:55:19
9F：→ anonimo: 不太懂你的意思 只要把rotation node間的data換過去不就 01/29 23:19
10F：→ anonimo: 好了嗎 106那題不也是動abc 3點之間嗎？ 01/29 23:19
11F：→ anonimo: 這題其實就是是CLRS第14章 可以去看看課本 01/29 23:20
感謝 剛剛去翻了一下課本有寫到紀錄size可以用來查是第幾個小的，插入一樣O(logn)
題目的s(node)原本以為旋過去之後要調底下每一點的height
但好像根本不用記錄在node上 我傻了，搜尋過程中每經過一點就+1就好
※ 編輯: ko330 (114.137.158.87), 01/30/2019 00:39:04
12F：推 silenteve: 請問第19題怎麼算呢 01/30 15:18
13F：推 ekids1234: 16應該沒有E 因為splay 可skew 供之後人參考 02/16 21:52