[理工] [資結] 97交大資訊聯招-DS&algo核對

[taitin (小南)]

1-(1) F
1-(2) T
1-(3) T
1-(4) F
1-(5) F

2-(1)
  若G唯一connected guderited graph，且邊上有成本OR權重。
  可產生大於等於一個以上的spanning tree。
  而其中權重和最小的即為spanning tree

2-(2)
  (圖略)
  {3}
  {3}{4}
  {3}{4,4}
  {3}{4,4}{5}
  {3}{4,4,6}{5}
  {3}{4,4,6}{5,7}
  {3}{4,4,6,5,7,8}
  {3,4,4,6,5,7,8,14}

2-(3)
   (圖略)
  {5}
  {5,7}
  {5,7,8}
  {5,7,8,4}
  {5,7,8,4,4}
  {5,7,8,4,4,6}
  {5,7,8,4,4,6,14}
  {5,7,8,4,4,6,14,3}

2-(4)

 k's algo O(ElogE) 其中E為邊數
 p's algo O(V^2)   其中V為點數


3-(1)
  為一complete Binnary tree，若非空則滿足
  1.所有父點<=子點
  2.root的key值最小

3-(2)
  比較各子點KEY值是否小於父點，若是則return false
  否則向下比較，到leaf return true

  node *p //a point point to root
  bool check(node *p)
  {
     if(p->left)
      {
        if((p->left)<p(value)) return false;
        if(!check(p->left)) return false;
      }
     if(p->right)
      {
        if((p->right)<p(value)) return false;
        if(!check(p->right)) return false;
      }

     return true;
}



4-(1) F
4-(2) F
4-(3) T
4-(4) F
4-(5) F
4-(6) T
4-(7) T
4-(8) F

5-(1) Θ(n(lgn)^2)
5-(2) Θ(nlglgn)
5-(3) Θ(lgnlglgn)
5-(4) Θ(lgn)
5-(5) Θ(lgn)


6-(1) x=1 y=2 z=1
6-(2) if change CD to 4， the maxflow is 5
6-(3) maxflow is 5
      minmun cut SE CE EF

7-(1) (1-8)^2+(8-2)^2+(2-7)^2+(7-3)^2+(3-6)^2+(6-4)^2+(4-5)^2
      =49+36+25+16+9+4+1=140

7-(2)
    1.use heap sort sort A in array
    2.for(i=1;i<n+1;i+=2)
      {
        B[i]=A[i]
        B[i+1]=A[n-i+1]
      }

    1. sort Θ(nlogn)
    2. O(n)
             = >>>  Θ(nlogn)


8-(1)  若給予一組數據，含有乘+1或-1的資訊
       則可在O(n)時間內被驗證，因此此題目為一npcomplete

       (接下來不會了XD，請高手指導)

希望有寫這份的可以一起討論~

歡迎寄信或回(推)文

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.236.51
※ 編輯: taitin          來自: 114.44.236.51        (02/01 20:42)
推 polomoss:請問一下第四大題:4578錯的地方在哪? 怕有些漏看的觀念
4. 他問的是any，所以我認為有包含RADIX sort
5.如果radix sort 的每個key都用比較sort法，那就失去了linear time的意義
  而rasix sort 個 key值應該用的是bucket sort。
7.應該是我當初想錯了...感覺在玩文字遊戲..我之前已為他說兩個一樣，已修正
8.因為B-heap的reduce需要logV time，因此結果會是O(Vlgv+ElgV)
  但F-heap只需O(1)，所以O(Vlgv+E)可完成
  有關這個部分 資結課本有，但是沒有講個很詳細，而且他B-heap講得很複雜
  他Bheap定義不能reduce key。
  我們老師建議直接看Corman的演算法。可以參考530。
→ polomoss:謝謝
→ polomoss:另外，7-(1)最右邊那項你打錯了
已修正，感謝
※ 編輯: taitin          來自: 140.113.37.176       (02/03 20:39)
推 polomoss:謝謝回答~~很詳細^^
※ 編輯: taitin          來自: 61.216.173.134       (02/18 01:16)
推 rockmanray:6(3)min cut錯了 應該是SA CE EF
→ rockmanray:應該是手誤