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

[carlossp (weyuruiwysfjgnjf)]

※ 引述《galapous (墨)》之銘言：
: ※ 引述《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 大大)
: : 19. A  (感謝 A4T8T6X9 大大)
: : 20. B  (感謝 A4T8T6X9 大大)
: : 21. B
: : 22. A
: : 23. B
: : 24. A
: : 25. B
: : 6 19 20 要麻煩大家幫忙湊答案了...
: 想問一下第18題怎麼會是B
2-3-4 tree的key number n, 4^(h-1)<=n<=2^(h-1)
2-3 tree , 3^(h-1)<=n<-2^(h-1)
很明顯不管怎麼看, 2-3-4 tree的高度一定小於或是等於2-3 tree

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.185.204
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422697112.A.5ED.html
推 a95641126: 誰說的...如果2-3-4的樹每個節點只存一個key,2-3樹每
→ a95641126: 個節點都存2個key
→ carlossp: 不會有上述情況發生吧，2-3樹跟2-3數的建立不都是
→ carlossp: to[ down的方式，資料是一筆一筆插入, 可以請您舉個例子
→ carlossp: 謝謝您 :)
推 galapous: 2-3-4 tree insert 1 to 10 後刪10 9 8
→ galapous: 2-3 tree 1 2 3 5 4 6 7
→ galapous: 前面文章就討論過囉
→ galapous: 1 2 3 5 6 4 7才對XD
→ carlossp: gala大大，請問2-3樹要用B-tree的建法,還是3node先分解
推 galapous: 3node先分解是?B-tree應該都同一種建法吧@@
→ carlossp: gala大大,可以請你畫一下這兩顆樹的結果給我看嗎？混了
→ carlossp: 我建立2-3-4樹後。10不知道怎麼刪除~~
推 hbkhhhdx2006: c大上面說的指的是2-3-4 tree的forward insertion嗎
推 GuardmanMart: http://ppt.cc/~R6~
→ GuardmanMart: 2-3-4 tree insert完1~10長這樣
→ GuardmanMart: 刪10 9 8後剛好每個node只有一個key
推 galapous: 起床才看到,thx G大
→ carlossp: 2-3-4樹再刪除時遇到2-node不是要先合併,Guar大大
→ carlossp: 可以請您畫一下刪除的結果嗎？
推 GuardmanMart: 所以9、10都刪了之後，上面的那個節點underflow了，
→ GuardmanMart: 8要下移跟7合併，然後再刪8