Re: [問題] 資料結構
※ 引述《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
推
05/23 11:11, , 1F
05/23 11:11, 1F
討論串 (同標題文章)