作者galapous (墨)
看板Grad-ProbAsk
標題Re: [理工] 102 台大電機丙 資結 對答案
時間Sat Jan 24 10:45:03 2015
※ 引述《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 要麻煩大家幫忙湊答案了...
想問兩題，
11、這題題目給的不是AVLtree，如果插入T3的leaf會使之+1高度那做完兩次rotation後
是不是c就不為root了？
16、這題出現過兩次不過還是沒搞懂orz，b tree of order 2照定義想不是應該是至少1
child至多2個嗎？為什麼是full bt？
感謝看完。
--
Sent from my Android
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.150
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422067505.A.27D.html
→ guo1111: 11題 如果是先rotate再插入的話 c就是root 01/24 11:04
→ galapous: 題目開頭就說那棵樹是AVL tree讓我不知道要不要先轉他@@ 01/24 19:27
→ galapous: 記得電機10x年好像也有一題題目原本就不是AVLtree的= = 01/24 19:27
→ guo1111: 先插入再轉的話 我轉不出balanced tree耶 01/24 22:53
推 yulinya: 16題，之前也有這個疑問，查維基它的說明裡有說到"The B- 01/25 01:40
→ yulinya: tree is a generalization of a binary search tree in t 01/25 01:40
→ yulinya: hat a node can have more than two children (Comer 197 01/25 01:40
→ yulinya: 9, p. 123). "所以猜想是原本定義中的b-tree最少就一定要 01/25 01:40
→ yulinya: 含兩個子點 01/25 01:40
推 yulinya: 外加如果只有一個子點,failure node 不會在同一層 01/25 01:46
→ galapous: 感謝y大! 01/25 13:09
→ galapous: 用Failure node要在同一層來想感覺蠻直觀的thxxx 01/25 13:10