作者taitin (小南)
看板Grad-ProbAsk
標題[理工] [資工] 98-台大DS&algo
時間Tue Jan 19 19:50:52 2010
這是我自己寫的答案，希望跟大家討論一下
附上題目
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
1F：推 applexgreen:推你一個 01/19 22:18
2F：推 killerjoe:為什麼doubly linked list 的insert與delete是O(1)? 01/19 23:13
dll 的插入需要移動四個指標，但因為是未排序的，插入任何位置都可以O(4)=O(1)
刪除也只需移動常數指標，仔細看題目delete a element point by p from L，這說明
指標已經只到要刪除的地方，而DLL的好處是可以找到前面一個節點，
如此一來刪除只要O(1)
3F：推 gensim:最後一題A,B寫反了.... 01/20 00:27
感謝樓上，因為是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)
4F：推 killerjoe:謝謝原來如此~ 01/20 23:37
5F：推 qwertz:第二題的第二小提del BST裡的 11跟21位置好像反了@@ 01/22 14:17
6F：→ taitin:沒有反喔，刪除只有一個子點的node，直接連起來就好了 01/25 07:56
8F：推 qwertz:阿 記錯了 抱歉XDD" 01/26 01:21
※ 編輯: taitin 來自: 61.230.227.76 (02/06 23:54)
※ 編輯: taitin 來自: 61.230.218.49 (02/20 21:49)
9F：推 RdMax:推一個 12/09 01:11