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