[理工] 107台大電機丙 資結對答案

看板Grad-ProbAsk作者 (ko330)時間5年前 (2019/01/29 16:50), 5年前編輯推噓4(4推 0噓 9→)
留言13則, 4人參與, 5年前最新討論串1/2 (看更多)
如題 有寫這份的希望可以一起檢討 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://www.ptt.cc/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
推
01/29 17:35, 5年前 , 1F
7.8我選AA 有t(node) 找中間相當於二分搜尋的速度
01/29 17:35, 1F
→
01/29 17:36, 5年前 , 2F
旋轉可能會影響到整棵樹s.t 花O(n)調整應該合理
01/29 17:36, 2F
→
01/29 17:40, 5年前 , 3F
想問1. 至少修改4個link 是哪4個
01/29 17:40, 3F
→
01/29 17:58, 5年前 , 4F
17c也看不太懂意思 qq
01/29 17:58, 4F
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
→
01/29 19:08, 5年前 , 5F
哦對 7A忘記skew的情況
01/29 19:08, 5F
推
01/29 20:21, 5年前 , 6F
第7題 他說can be found 所以我覺得應該選最小O(logn)
01/29 20:21, 6F
→
01/29 20:23, 5年前 , 7F
第8題應該不用整顆樹改 只要改做ratation的部分就好
01/29 20:23, 7F
→
01/29 20:24, 5年前 , 8F
*rotation
01/29 20:24, 8F
第7我是覺得他想考的不是這個耶0.0 第8 rotation可能不只動三個點耶，下面subtree也全部會動到，你寫看看106的11題也是 這樣 ※ 編輯: ko330 (114.137.158.87), 01/29/2019 21:55:19
→
01/29 23:19, 5年前 , 9F
不太懂你的意思 只要把rotation node間的data換過去不就
01/29 23:19, 9F
→
01/29 23:19, 5年前 , 10F
好了嗎 106那題不也是動abc 3點之間嗎？
01/29 23:19, 10F
→
01/29 23:20, 5年前 , 11F
這題其實就是是CLRS第14章 可以去看看課本
01/29 23:20, 11F
感謝 剛剛去翻了一下課本有寫到紀錄size可以用來查是第幾個小的，插入一樣O(logn) 題目的s(node)原本以為旋過去之後要調底下每一點的height 但好像根本不用記錄在node上 我傻了，搜尋過程中每經過一點就+1就好 ※ 編輯: ko330 (114.137.158.87), 01/30/2019 00:39:04
推
01/30 15:18, 5年前 , 12F
請問第19題怎麼算呢
01/30 15:18, 12F
推
02/16 21:52, 5年前 , 13F
16應該沒有E 因為splay 可skew 供之後人參考
02/16 21:52, 13F
‣ 更多 ko330 的文章
文章代碼(AID): #1SK1FhZx (Grad-ProbAsk)
‣ 更多 ko330 的文章
文章代碼(AID): #1SK1FhZx (Grad-ProbAsk)