作者taitin (小南)
看板Grad-ProbAsk
標題[理工] [資結] 97交大資訊聯招-DS&algo核對
時間Mon Feb 1 20:13:17 2010
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)
1F：推 polomoss:請問一下第四大題:4578錯的地方在哪? 怕有些漏看的觀念 02/03 11:52
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。
2F：→ polomoss:謝謝 02/03 11:52
3F：→ polomoss:另外，7-(1)最右邊那項你打錯了 02/03 11:53
已修正，感謝
※ 編輯: taitin 來自: 140.113.37.176 (02/03 20:39)
4F：推 polomoss:謝謝回答~~很詳細^^ 02/03 23:25
※ 編輯: taitin 來自: 61.216.173.134 (02/18 01:16)
5F：推 rockmanray:6(3)min cut錯了 應該是SA CE EF 01/28 23:27
6F：→ rockmanray:應該是手誤 01/28 23:27