[理工] 105交大資演

看板Grad-ProbAsk作者 (空氣牆)時間9年前 (2016/02/15 15:23), 9年前編輯推噓22(22推 0噓 23→)
留言45則, 12人參與, 最新討論串2/10 (看更多)
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
→
02/15 15:32, , 1F
你的題目在哪.........
02/15 15:32, 1F
sorry, 題目已補上
→
02/15 15:37, , 2F
還在公海上
02/15 15:37, 2F
※ 編輯: AirWall (36.224.9.139), 02/15/2016 15:51:02
→
02/15 15:57, , 3F
C就不是shortest path阿QQ
02/15 15:57, 3F
好吧~想說先問看有沒人一樣還沒重算QQ ※ 編輯: AirWall (36.224.20.179), 02/15/2016 16:03:09
推
02/15 16:09, , 4F
17(b)應該是時間Θ(n)空間Θ(n)...
02/15 16:09, 4F
...我懂了Q_Q感謝 ※ 編輯: AirWall (36.224.20.179), 02/15/2016 16:12:08 ※ 編輯: AirWall (36.224.20.179), 02/15/2016 16:12:50
→
02/15 16:40, , 5F
26)只有n個點
02/15 16:40, 5F
推
02/15 16:45, , 6F
47 CLRS也是O(1)
02/15 16:45, 6F
→
02/15 16:54, , 7F
你29題記到的那段是binomial heap,Fibonacci是O(1)
02/15 16:54, 7F
推
02/15 17:01, , 8F
借問資演1.(3) 為何答案不是(A)呢，"Here we assume th
02/15 17:01, 8F
→
02/15 17:01, , 9F
e lowest leaf node has height 1." 最低的葉子高度是1
02/15 17:01, 9F
→
02/15 17:01, , 10F
，那整顆的高度不就是3嗎@@
02/15 17:01, 10F
→
02/15 17:02, , 11F
給題目@@
02/15 17:02, 11F
推
02/15 17:23, , 12F
1.(3)我也有同樣的問題
02/15 17:23, 12F
推
02/15 17:25, , 13F
1.當樹根高度=1 2. 你有地方畫錯 qq
02/15 17:25, 13F
推
02/15 17:41, , 14F
1（3）大家一起傳真吧
02/15 17:41, 14F
推
02/15 17:45, , 15F
1.(3) 是5阿 你畫錯吧
02/15 17:45, 15F
推
02/15 17:46, , 16F
02/15 17:46, 16F
→
02/15 17:47, , 17F
QQ
02/15 17:47, 17F
推
02/15 17:47, , 18F
我覺得他的意思是F的高度是1
02/15 17:47, 18F
→
02/15 17:48, , 19F
不過我也是寫5 當下沒想那麼多
02/15 17:48, 19F
→
02/15 17:49, , 20F
這題硬要也能說是定義在所有2元樹裡面最低的樹高度為1
02/15 17:49, 20F
→
02/15 17:49, , 21F
畫得跟o大一樣 (話說大家怎麼都在線上@@
02/15 17:49, 21F
推
02/15 17:51, , 22F
吃晚餐吧
02/15 17:51, 22F
推
02/15 17:52, , 23F
因為他題目假設最低的leaf的height為1，所以...qq
02/15 17:52, 23F
→
02/15 17:57, , 24F
這就是root從1開始數的另一個講法
02/15 17:57, 24F
推
02/15 18:08, , 25F
大家對low的看法不同
02/15 18:08, 25F
推
02/15 18:09, , 26F
若越靠近root越low因為level小，應該也沒錯
02/15 18:09, 26F
推
02/15 18:11, , 27F
若root的高度為最低,則the lowest leaf node我認為是F,
02/15 18:11, 27F
→
02/15 18:11, , 28F
但是若root的高度為最高,則最低的葉子是H高度也確實是5
02/15 18:11, 28F
→
02/15 18:11, , 29F
,但是一般定義高度的方式不是root最低嗎
02/15 18:11, 29F
推
02/15 18:29, , 30F
我覺得要這樣解釋也是通，但交大出題感覺不會改答案
02/15 18:29, 30F
→
02/15 18:30, , 31F
通常"定義"方面的問題他不太會理你的樣子...
02/15 18:30, 31F
→
02/15 18:31, , 32F
因為實際上應該找不到資料(課本)真的對這個名詞定義
02/15 18:31, 32F
→
02/15 18:32, , 33F
題目真的有錯應該會改 這題我是覺得不會 當你沒看懂題意
02/15 18:32, 33F
推
02/15 18:43, , 34F
嗯嗯，會改的幾乎都是題目有錯，題意不清是不會改的（
02/15 18:43, 34F
→
02/15 18:43, , 35F
除非你能在書上找到一樣的題目）
02/15 18:43, 35F
推
02/15 18:57, , 36F
拚個3 or 5都對也好吧，不然一題五分好傷qq
02/15 18:57, 36F
推
02/15 19:05, , 37F
1.(3)可以參考這個 http://goo.gl/2Rd8is
02/15 19:05, 37F
→
02/15 19:09, , 38F
Height的求法是以leaf作base line,看點跟leaf之間的最長邊
02/15 19:09, 38F
推
02/15 19:09, , 39F
數是多少,其中height of tree=height of root
02/15 19:09, 39F
推
02/15 19:21, , 40F
聖經本的height是用所有node中最大的level，和樓上定義不同
02/15 19:21, 40F
推
02/15 20:40, , 41F
推
02/15 20:40, 41F
→
02/15 21:11, , 42F
DS中的定義跟x大說的一樣 而AL中的定義則同我貼的網址
02/15 21:11, 42F
→
02/15 21:11, , 43F
而交大似乎是以AL的定義來教(有找到2012年的pdf)
02/15 21:11, 43F
→
02/15 21:12, , 44F
所以1.(3)答案恐怕不會更動吧@@
02/15 21:12, 44F
推
02/18 22:40, , 45F
結果我當場冥燈 其實我也錯3.
02/18 22:40, 45F
‣ 更多 AirWall 的文章
文章代碼(AID): #1MmNpzUE (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 2 之 10 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共10篇)
‣ 更多 AirWall 的文章
文章代碼(AID): #1MmNpzUE (Grad-ProbAsk)