為什麼這篇二元樹建立鄉民發文收入到精華區:因為在二元樹建立這個討論話題中,有許多相關的文章在討論,這篇最有參考價值!作者forris (喬巴)看板Examination標題[問題] 資料結構時間Sat May 17 ...
二元樹建立 在 革命開始的時候躺下來 Instagram 的精選貼文
2021-08-19 00:32:23
▸ 最後是寂寞 ◂ 朋友們爭論過好幾次村上改編電影最棒的到底是《東尼瀧谷》還是《燃燒烈愛》,你覺得呢? 洋子,這個問題真不好回答,就像你問我喜歡草莓蛋糕還是檸檬塔一樣。 高中一年級和一個女孩看了《挪威的森林》,至此更喜歡低溫感、纖細而真空的電影。我從電影看回原著小說,真愛的一...
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 ?
3. 在二元樹上,依照節點所在的層次,由最上層至最下層一層層走動 (traverse) 時,
需要用到哪一種資料結構?
(a) stack (b) queue (c) hash table (d) heap
為何要選 b 而不是 d ?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.240.43
※ 編輯: forris 來自: 218.173.240.43 (05/17 00:56)
> -------------------------------------------------------------------------- <
作者: canatmis (Guest~) 看板: Examination
標題: Re: [請益] 資料結構
時間: Sat May 17 11:31:45 2008
※ 引述《forris (喬巴)》之銘言:
: 1. 將 1234567 七個數目依某順序插入一個空的二元搜尋樹 (Binary Search Tree) 後,
: 所得的二元搜尋數如下圖所示:
: 4
: / \
: 2 6
: / \ / \
: 1 3 5 7
: 總共有幾種可能的插入順序?
: (a) 40 種 (b) 48 種 (c) 80 種 (d) 96 種
這題我也是跟原po那篇推文的幾個大大一樣的算法
如果是以上圖所示的二元搜尋樹來插入的話
第一層的4<-- root 只有一種插入順序
第二層的2和6誰都可以先插入,而不影響另一個,所以可有2!種插入順序
第三層的1、3、5、7,如因為2和6已完成插入
,所以第三層誰先插入也都可以所以有4!種插入順序
因此,1!*2!*4! = 48 種插入順序
: 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 ?
二元搜尋樹的定義:如果不是空集合,左子樹的所有節點值必小於root值
右子樹的所有節點值必大於root值
因此用此觀念來run
選項 c: root = 24,再看後面一個48 > 24,故48(含)以後的值都必大於24
(因為,在搜尋過程不會再突然變到root的左子樹去,會一直比下去
故,後面的所有值都大於root值)
因此,後面的搜尋過程比較,也依此類推
24
\
(48、44、25、40、33、26、34、30)
24
\
48
/
(44、25、40、33、26、34、30)
24
\
48
/
44
/
25
\
40
/
33
/
26
\
「34」<---錯,因為34並不小於33
: 3. 在二元樹上,依照節點所在的層次,由最上層至最下層一層層走動 (traverse) 時,
: 需要用到哪一種資料結構?
: (a) stack (b) queue (c) hash table (d) heap
: 為何要選 b 而不是 d ?
我們舉個例子好了,以下圖所示,印出走訪過的節點值
4
/ \
2 6
/ \ / \
1 3 5 7
如果我的走訪順序是4、6、5的話,要印出走訪過的節點值
也會像走訪過的順序一樣印出
這樣一來,像不像Queue的定義呢?
Queue的定義:FIFO,先進先出
以上,有錯的請各位大大校正
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.127.66.114