[理工] 105交大資演

[AirWall (空氣牆)]

17題b為什麼錯呢? (Solved)
http://i.imgur.com/pGhTV8L.jpg

26題a為什麼錯呢?
是錯在 m Unions嗎?
http://i.imgur.com/7RT1lC7.jpg

29題的c 大家怎麼看?
我想說如果是ALOG版本merging time是logn
DS的才是O(1)
加上洪說DS版本定義不好考試基本都考ALGO版本
http://i.imgur.com/f5WcTCb.jpg


47 C不行嗎?~  (Solved)
http://i.imgur.com/WshEOag.jpg
http://i.imgur.com/VbWooqF.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.20.179
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455521021.A.78E.html
→ a016258: 你的題目在哪.........
sorry, 題目已補上
→ odanaga: 還在公海上
※ 編輯: AirWall (36.224.9.139), 02/15/2016 15:51:02
→ odanaga: C就不是shortest path阿QQ
好吧~想說先問看有沒人一樣還沒重算QQ
※ 編輯: AirWall (36.224.20.179), 02/15/2016 16:03:09
推 WES2163818: 17(b)應該是時間Θ(n)空間Θ(n)...
...我懂了Q_Q感謝
※ 編輯: AirWall (36.224.20.179), 02/15/2016 16:12:08
※ 編輯: AirWall (36.224.20.179), 02/15/2016 16:12:50
→ f111222003: 26)只有n個點
推 goldflower: 47 CLRS也是O(1)
→ yaxauw: 你29題記到的那段是binomial heap,Fibonacci是O(1)
推 j22491050: 借問資演1.(3) 為何答案不是(A)呢，"Here we assume th
→ j22491050: e lowest leaf node has height 1." 最低的葉子高度是1
→ j22491050: ，那整顆的高度不就是3嗎@@
→ yaxauw: 給題目@@
推 JFaker: 1.(3)我也有同樣的問題
推 odanaga: 1.當樹根高度=1 2. 你有地方畫錯 qq
推 xogo: 1（3）大家一起傳真吧
推 silent0108: 1.(3) 是5阿 你畫錯吧
推 odanaga: http://i.imgur.com/QWyhySB.png
→ odanaga: QQ
推 goldflower: 我覺得他的意思是F的高度是1
→ goldflower: 不過我也是寫5  當下沒想那麼多
→ goldflower: 這題硬要也能說是定義在所有2元樹裡面最低的樹高度為1
→ yaxauw: 畫得跟o大一樣 (話說大家怎麼都在線上@@
推 odanaga: 吃晚餐吧
推 JFaker: 因為他題目假設最低的leaf的height為1，所以...qq
→ yaxauw: 這就是root從1開始數的另一個講法
推 xogo: 大家對low的看法不同
推 xogo: 若越靠近root越low因為level小，應該也沒錯
推 j22491050: 若root的高度為最低,則the lowest leaf node我認為是F,
→ j22491050: 但是若root的高度為最高,則最低的葉子是H高度也確實是5
→ j22491050: ,但是一般定義高度的方式不是root最低嗎
推 silent0108: 我覺得要這樣解釋也是通，但交大出題感覺不會改答案
→ goldflower: 通常"定義"方面的問題他不太會理你的樣子...
→ goldflower: 因為實際上應該找不到資料(課本)真的對這個名詞定義
→ odanaga: 題目真的有錯應該會改 這題我是覺得不會 當你沒看懂題意
推 silent0108: 嗯嗯，會改的幾乎都是題目有錯，題意不清是不會改的（
→ silent0108: 除非你能在書上找到一樣的題目）
推 JFaker: 拚個3 or 5都對也好吧，不然一題五分好傷qq
推 Bassy: 1.(3)可以參考這個 http://goo.gl/2Rd8is
→ Bassy: Height的求法是以leaf作base line,看點跟leaf之間的最長邊
推 Bassy: 數是多少,其中height of tree=height of root
推 xogo: 聖經本的height是用所有node中最大的level，和樓上定義不同
推 hunyi: 推
→ Bassy: DS中的定義跟x大說的一樣 而AL中的定義則同我貼的網址
→ Bassy: 而交大似乎是以AL的定義來教(有找到2012年的pdf)
→ Bassy: 所以1.(3)答案恐怕不會更動吧@@
推 odanaga: 結果我當場冥燈                           其實我也錯3.