[問題] 資料結構

[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 ?

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)
推 flamemmx2:第一題：第一個插入的一定是4(一種方法)，然後再考慮第
→ flamemmx2:二層的2和6，有可能是2先或是6先插入(2*1種方法)，再來
→ flamemmx2:考慮第三層的1、3、5、7(有4*3*2*1種方法)，故全部的方
→ flamemmx2:法數為1*1*2*4*3*2*1=48種。不知道這樣解對不對XD
推 steter:第一題我也有疑問?
推 steter:我記得答案不是48 雖然我算48 XD
推 cutedoll7411:缺少了像2163 57這一類的
→ cutedoll7411:所以除了原本的48再加上將213為一堆，657為一堆
→ cutedoll7411:一開始先選擇要哪一堆，若選擇213，則為2*2！，
→ cutedoll7411:再將6插入213中的4個位置其中一個，為 C4取1
→ cutedoll7411:最後在排57，則為(C4取1)*2！
→ cutedoll7411:所以為48+2*2！*4*2！
推 steter:我也記得答案是80
> -------------------------------------------------------------------------- <

作者: 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
推 cutedoll7411:應該是用深度追蹤(DFS)去想
→ cutedoll7411:先追蹤4，將26放入queue中，因為下一次要追蹤第2層
→ cutedoll7411:將queue中2 pop出來，再將13放入queue
→ cutedoll7411:將queue中6 pop出來，再將57放入queue
→ cutedoll7411:這樣就能保證1層1層追蹤，所以使用queue
推 galdar:別想太多..level order就是queue...
推 jojoh:C大 這應該是廣度追蹤 用Queue去做
→ jojoh:總結來說 ..level order就是queue...
→ canatmis:嗯，了解，謝謝各位大大的校正，還有第一題是80種
→ canatmis:為原來的48+(2*2!)*(2*2!*2!)