作者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