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

[hyc1227 ()]

※ 引述《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 要麻煩大家幫忙湊答案了...

請問一下

第8題怎麼找反例

Given a k-nary tree with n node, the height of the tree is at least log n-1
                                                                       k
這裡是說 at least 所以應該要找到一個 n 個 node 的 k-nary tree 高度更小

想不到要怎麼畫?


第11題

T1 T2 T3 T4 都說是同樣高度，這樣他給的圖本來就不是AVL tree了吧

所以要先rotation幫他平衡再insert a new node嗎?

感謝


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.123.57.203
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1422776145.A.CAD.html
推 victor801120: 第11題先幫他平衡+1
推 victor801120: 第八題應該是因為，在完滿樹時節點數n= (k^h) -1 ，
→ victor801120: 推得的高度公式與題目給的不同吧？（ log n-1 <-> l
→ victor801120: og n+1 )
原來是這樣啊
※ 編輯: hyc1227 (140.123.57.203), 02/02/2015 16:16:17