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

看板Grad-ProbAsk作者 (村)時間11年前 (2014/02/24 21:03), 編輯推噓2(204)
留言6則, 4人參與, 最新討論串10/18 (看更多)
想問一下第4題 這題我寫A balance binary tree 左右子樹最多只差一個node 搜尋某個元素 不就更剛好是O(logn)了嗎? : ※ 引述《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 要麻煩大家幫忙湊答案了... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.79.198.240

02/24 21:19, , 1F
Balance BT喔 並不一定是BST 既然沒有規則,最慘是O(n)
02/24 21:19, 1F

02/24 21:23, , 2F
如果是balance bst 那就O(lgn)
02/24 21:23, 2F

02/24 22:06, , 3F
BT每一個node都要找 所以是最差O(n)
02/24 22:06, 3F

02/25 19:38, , 4F
原來如此!!DS(B)考的滿心機的,題目要看很清楚XD
02/25 19:38, 4F

03/01 22:21, , 5F
這一題錯的點應該是左右子樹是高度差1而不是node數差1吧@@
03/01 22:21, 5F

03/01 22:21, , 6F
不知道我自己定義有沒有記錯@@
03/01 22:21, 6F
文章代碼(AID): #1J2qCl_T (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 10 之 18 篇):
文章代碼(AID): #1J2qCl_T (Grad-ProbAsk)