[理工] 105台大電機丙 資結 對答案
是非
1. B
max height of AVL tree: 1.44xlogn
max height of RB tree: 2 logn
2. B
3. A
4. B
5. B (我覺得是O(n)...)
6. A
7. A
8. A
9. A
10.B (O(1) time)
單選
1. C
2. B
3. E (12354)
4. E (0 double rotation, 2 left rotations)
非選
三 google一下應該有很多
array 可以randome access; linked list 只能sequential access
之類的等等等
四 自己有寫一個 可是不知道對不對 請大神補充
五 題目問的怪怪的 strongly connected component只有directed graph 才有
如果是undirected graph 求 connected component
int component=0;
for i=0 to n-1 // iterate throught all vertices in the graph
{ if vertex[i]==FALSE // if the vertex is not visited
dfs(G, i);
int j;
printf("%d", i);
visitied[i]=1;
for(j=0; j<n; j++){
if(visited[j]==0&&G[i][j]==1)
dfs(G, j);
}
component+=1;
}
不太確定 請大神幫忙debug!
如果是directed graph 求strongly connected component
---->google Kosaraju's algorithm
看不懂QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.125.97.119
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483441872.A.0C8.html
※ 編輯: tzutengweng (59.125.97.119), 01/03/2017 19:11:53
推
01/03 19:43, , 1F
01/03 19:43, 1F
→
01/03 19:47, , 2F
01/03 19:47, 2F
→
01/03 19:48, , 3F
01/03 19:48, 3F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 2 篇)：