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

看板Grad-ProbAsk作者 (揪立)時間7年前 (2017/01/24 16:50), 編輯推噓5(5021)
留言26則, 4人參與, 最新討論串17/18 (看更多)
※ 引述《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

01/24 16:51, , 1F
噢對了,中間還有一題234top down插入,我的結果root是7
01/24 16:51, 1F

01/24 17:03, , 2F
Binomial heap是好幾個binomial tree組成 最多點的tree
01/24 17:03, 2F

01/24 17:03, , 3F
的root對應的key不一定是所有樹中最小的
01/24 17:03, 3F

01/24 17:04, , 4F
21題我直接舉一個binary tree就剛好否決題目敘述了...
01/24 17:04, 4F

01/24 17:06, , 5F
咦我的課本怎麼有寫root是最小值QQ,還是定義有不一樣
01/24 17:06, 5F

01/24 17:06, , 6F
不過依你的例子來說,我追蹤的結果跟你一樣
01/24 17:06, 6F

01/24 17:07, , 7F
我也是按照postorder 左右中下去追蹤QQ感覺不太實際?
01/24 17:07, 7F

01/24 17:08, , 8F
每棵樹的root一定是該棵樹最小 但不一定是整個heap的最小
01/24 17:08, 8F

01/24 17:08, , 9F
1 2
01/24 17:08, 9F

01/24 17:09, , 10F
|
01/24 17:09, 10F

01/24 17:09, , 11F
3
01/24 17:09, 11F

01/24 17:09, , 12F
這樣應該也是一種binomial heap?
01/24 17:09, 12F

01/24 17:09, , 13F
如果是的話可以用來否決題目的敘述
01/24 17:09, 13F

01/24 17:12, , 14F
又看了一遍題目,一個B heap的最小值是一個binomial tree
01/24 17:12, 14F

01/24 17:12, , 15F
中的root
01/24 17:12, 15F

01/24 17:13, , 16F

01/24 17:13, , 17F
這個好像就是反例?
01/24 17:13, 17F

01/24 17:14, , 18F
所以不一定是最多點的b heap有最小值,我是這麼覺得
01/24 17:14, 18F

01/24 17:15, , 19F
我覺得你的敘述沒錯,看其他人覺得有沒有瑕疵
01/24 17:15, 19F

01/24 17:28, , 20F
修正一下圖,應該是binomial heap不是tree,tree是裡面每
01/24 17:28, 20F

01/24 17:28, , 21F
一個components
01/24 17:28, 21F

01/24 18:33, , 22F
20錯吧,最多點的root不一定會是最小ㄚ
01/24 18:33, 22F

01/24 18:34, , 23F
應該是binary tree的root是(該tree)最小,不是binary
01/24 18:34, 23F

01/24 18:34, , 24F
heap
01/24 18:34, 24F

01/24 18:36, , 25F
樓上想說的是binomial?
01/24 18:36, 25F

01/24 18:44, , 26F
噢對binomial .. 打錯字QQ
01/24 18:44, 26F
文章代碼(AID): #1OXnLaPW (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 17 之 18 篇):
文章代碼(AID): #1OXnLaPW (Grad-ProbAsk)