※ 引述《forris (喬巴)》之銘言： : 1. 將 1234567 七個數目依某順序插入一個空的二元搜尋樹 (Binary Search Tree) 後， : 所得的二元搜尋數如下圖所示： : 4 : ／ ＼ : 2 6 : ／ ＼ ／ ＼ : 1 3 5 7 : 總共有幾種可能的插入順序？ : (a) 40 種 (b) 48 種 (c) 80 種 (d) 96 種 不會，留給高手吧 : 2. 某二元搜尋樹內存有 10 到 50 之間的數目。自此二元搜尋樹搜尋數目 30 時， : 其搜尋過程中比對過的數目，不可能是下列哪一個順序？ : (a) 15,43,18,39,20,36,27,30 : (b) 38,10,19,37,21,33,31,30 : (c) 24,48,44,25,40,33,26,34,30 : (d) 42,39,12,13,23,35,28,32,30 : 為什麼是選 c ? 因為是二元搜尋樹，所以樹中的各節點，必定排序過了 a / \ a左半邊子樹的值必定全小於a, 右半邊子樹的值必定全大於a b c 可以用最簡單的方式判斷 以選項(c)為例 24為根節點，30為搜尋值，向右子樹拜訪，因此，接下來所有的值都必須大於24 (此部份都還吻合) 下一個拜訪的節點為48，30<48，故往48的左子樹拜訪 接下來經過的所有節點都必須小於48 下一個節點為44，30<44，再往44的左子樹拜訪 接下來經過的所有節點都須小於44 . . . (以上類推) 問題會出現在 33這個節點，30<33，所以要往33的左子樹拜訪 理論上，後續要拜訪的三個節點(26.34.30)都必須要小於33 但題目中出現了34這個不符合的節點，所以c是錯的 : 3. 在二元樹上，依照節點所在的層次，由最上層至最下層一層層走動 (traverse) 時， : 需要用到哪一種資料結構？ : (a) stack (b) queue (c) hash table (d) heap : 為何要選 b 而不是 d ? 依照題意由上層至下層一層層走動，為廣度優先搜尋，使用queue應無誤 若為深度優先搜尋需要使用stack 不知為何會想選擇heap (如解題有誤，煩請賜教) --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.163.226.50