Re: [理工] 102 台大電機丙 資結 對答案

[joeboy (揪立)]

※ 引述《olderbrother (大蜘蛛)》之銘言：
: 題目
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/102/102409.pdf
: 我寫的答案
: (A:True, B:False, 考卷上是這樣標的...)
:  1. B
:  2. B
:  3. A
:  4. B
:  5. A
:  6. B  (感謝 A4P8T6X9 大大)
:  7. B
:  8. B
:  9. B
: 10. A
: 11. A
: 12. A
: 13. B
: 14. A
: 15. B
: 16. A
: 17. B
: 18. B  (感謝 a5120265 大大)
: 18. B  (感謝 a5120265 大大)
: 19. A  (感謝 A4T8T6X9 大大)
: 20. B  (感謝 A4T8T6X9 大大)
: 21. B
: 22. A
: 23. B
: 24. A
: 25. B
: 6 19 20 要麻煩大家幫忙湊答案了...

不好意思想請問一下20跟21
Binomial最小的點是root這個ok
那麼root不是應該有最多的點跟他相連嗎？
這句話錯在哪裡呢QQ

21他說DAG用postorder trversal
這個要怎麼追蹤呢？
http://i.imgur.com/fqPurQu.jpg
這是我自己假設的例子
以起點s開始追蹤

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.182.68
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485247844.A.660.html
→ joeboy: 噢對了，中間還有一題234top down插入，我的結果root是7
推 w181496: Binomial heap是好幾個binomial tree組成 最多點的tree
→ w181496: 的root對應的key不一定是所有樹中最小的
推 yupog2003: 21題我直接舉一個binary tree就剛好否決題目敘述了...
→ joeboy: 咦我的課本怎麼有寫root是最小值QQ，還是定義有不一樣
→ yupog2003: 不過依你的例子來說，我追蹤的結果跟你一樣
→ joeboy: 我也是按照postorder 左右中下去追蹤QQ感覺不太實際？
→ w181496: 每棵樹的root一定是該棵樹最小 但不一定是整個heap的最小
→ yupog2003: 1   2
→ yupog2003:     |
→ yupog2003:     3
→ yupog2003: 這樣應該也是一種binomial heap?
→ yupog2003: 如果是的話可以用來否決題目的敘述
→ joeboy: 又看了一遍題目，一個B heap的最小值是一個binomial tree
→ joeboy: 中的root
→ joeboy: http://i.imgur.com/lgBBsRm.jpg
→ joeboy: 這個好像就是反例？
→ joeboy: 所以不一定是最多點的b heap有最小值，我是這麼覺得
推 yupog2003: 我覺得你的敘述沒錯，看其他人覺得有沒有瑕疵
→ joeboy: 修正一下圖，應該是binomial heap不是tree，tree是裡面每
→ joeboy: 一個components
推 Transfat: 20錯吧，最多點的root不一定會是最小ㄚ
→ Transfat: 應該是binary tree的root是（該tree)最小，不是binary
→ Transfat: heap
→ yupog2003: 樓上想說的是binomial?
推 Transfat: 噢對binomial .. 打錯字QQ