[理工] [資工] 98-台大DS&algo

[taitin (小南)]

這是我自己寫的答案，希望跟大家討論一下

附上題目

http://www.lib.ntu.edu.tw/exam/graduate/98/98404.pdf

1. (1) G
   (2) H
   (3) L
   (4) E
   (5) H

2.
(1)
     34
    /  \
   23  51
  /    / \
 11   39 89
  \      /
  21    77

(2)
     34                34
    /  \             /   \
   11  39           11   77
    \   \    OR      \   / \
    21  89          21 39  89
         /
        77


(3)
  當輸入數列為遞增數列，或為遞減數列的時候
  EX 1 3 5 7 9

(4)
假設N個數中，Xj為第j個插入的數字

則可將數列分成兩個數列，僅需討論已下數列
1.{G|for all Xi;Xk>Xi>Xj;1<=k<=i<j<=n}
2.{L|for all Xi;XK<Xi<Xj;1<=k<=i<j<=n}     (<= 小於或等於)

則 Xj的深度=|G|+|L|  其中|G|,|L|為符合敘述的個數

討論|G|在ith插入時的期望值

則每次增加高度的期望值為p(Xi)=1/i

依序插入N個值後，可得到總高度為

|G|=p(X1)+p(X2)+...+p(Xn)
   =1+1/2+1/3+1/4+...1/n 為一調和數列
   =O(logn)

同理可証得，|L|=O(logn)

因此random binary search tree 深度為
   |G|+|L|=O(logn)

3.
           unsorted  sorted  unsorted  sorted
           singly    singly  doubly    doubly
           linked    linked  linked    linked

search       B         B       B        B
INSERT       A         B       A        B
DELETE       B         B       A        A
SUCCESOR     A         A       A        A
PREDECESSOR  B         B       A        A
minimum      B         A       B        A
maximum      B         A       B        A


4. If the node's parent don't  have  parent
   then that means the node's parent is a root.
   Beacuse the root must be black.
   There is no "red-red conflict"
   So we don't have to handle the situation.

5.
 (1) B
 (2) B

6.
 (1) L(u,w)+d(v,u)-d(v,w)>= 0

  -> d(v,w)<=d(v,u)+l(u,w)
  由題目可知d(v,w)為一最短路徑from v to w
  若 此最短路徑經過u
  則d(v,w)=d(v,u)+l(u,w)
  若 最短路徑不經過u
  則表示 v~>u->w的路徑比較大
  d(v,w)<d(v,u)+L(u,w)
  因此可証得 d(v,w)<=d(v,u)+L(u,w)

 (2)
a.
   在G中 假設有條路徑 p(u,v),由u經過x1,x2,...,xn到v
   則p(w,x)=L(u,x1)+L(x2,x3)+...+L(xn,v)  ...(1)
   已知在G'中 L'(w,x)=L(w,x)+s(w)-s(x)
           L(w,x)=L'(w,x)-s(w)+s(x)
   代入(1)得
   p(u,v)=L'(w,x1)+L'(x2,x3)+...+L'(xn,v)-s(u)+s(v)
   若假設G'中沿相同路徑稱為p'(u,v)，則
   p'(u,v)=L'(u,x1)+L'(x2,x3)+...+L'(xn,v)
   則
   p(u,v)=p'(u,v)-s(u)+s(v)

b.
      已知在G中w,x有最短路徑d(w,x)屬於p(w,x)
      且p(w,x)>=d(w,x)   (註 大於或等於)
      由a知 G'中p(w,x)=p'(w,x)-s(w)+s(x)

      因此 p'(w,x)-s(w)+s(x) >= d'(w,x)-s(w)+s(x)  (註 大於或等於)
           p'(w,x)>= d'(w,x)
      由此知d'(w,x)為一最短路徑且與d(w,x)相同


 (3) A is suitable
     Because B is not suitable when there has  negative length.
     consider a graph

             4
          -------
         /       \
         a---c---b
           5   -1
     start from a
     algo B will choose the shortest edge AB
     and never look back.

     but algo A will check all the edges.so it is suitable


希望也有寫這分考卷的朋友可以一起討論

有錯請不吝指教

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.242.210
推 applexgreen:推你一個
推 killerjoe:為什麼doubly linked list 的insert與delete是O(1)?
  dll 的插入需要移動四個指標，但因為是未排序的，插入任何位置都可以O(4)=O(1)
  刪除也只需移動常數指標，仔細看題目delete a element point by p from L，這說明
  指標已經只到要刪除的地方，而DLL的好處是可以找到前面一個節點，
  如此一來刪除只要O(1)
推 gensim:最後一題A,B寫反了....
 感謝樓上，因為是BELLMEN algo 我就很自然的寫成B   XD
※ 編輯: taitin          來自: 140.113.37.153       (01/20 09:00)
ps 6-(2) 修改很多，這樣寫感覺比較洽當
※ 編輯: taitin          來自: 140.113.37.153       (01/20 11:15)
推 killerjoe:謝謝原來如此~
推 qwertz:第二題的第二小提del BST裡的 11跟21位置好像反了@@
→ taitin:沒有反喔，刪除只有一個子點的node，直接連起來就好了
→ taitin:http://0rz.tw/ZvSKr
推 qwertz:阿　記錯了　抱歉XDD"
※ 編輯: taitin          來自: 61.230.227.76        (02/06 23:54)
※ 編輯: taitin          來自: 61.230.218.49        (02/20 21:49)
推 RdMax:推一個