作者NOtWorThy (分子小於64)
看板Grad-ProbAsk
标题[理工] [资结]-tree and grap
时间Fri Jan 29 23:40:03 2010
a)If undirected grap is connected, there must exist more than one spanning tree.
// why true ?? 若原本图就是tree,那spanning tree不就不会超过一种吗??
b)If we use adjacency matrix to reprent the undirected grap, the time of DFS
and BFS are all O(n*n), n is number of vertex
// 这题不太懂
c)There has more than one topology sort in AOV network
// why false ?? 不是会超过一种吗??
Which time complexity is O(nlogn)
Delet min in binomial heap // 不是O(logn)嘛??
Merge two leftist heap as a leftist // why??
Search a n item in splay tree in amortimed analysis // why??
烦请高手不吝赐教
感激不尽!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.70.230.32
1F：推 assassin88:A.有weight才唯一 01/30 00:04
2F：推 assassin88:B.也不懂= = 01/30 00:10
3F：→ assassin88:最後一题题目出错 01/30 00:10
4F：→ trovadores:用相邻矩阵实做DFS或BFS时因为要知道与点v相邻的所有点 01/30 00:34
5F：推 Astroboy0803:第二题你要先简略划个相邻矩阵，然後从第一顶第一个 01/30 00:34
6F：→ Astroboy0803:边找，找到後再往下一个顶点找，依此类推...求完所有 01/30 00:35
7F：→ trovadores:所以读相邻矩阵的第v列(O(n)),总共做n次,所以O(n*n) 01/30 00:36
8F：→ Astroboy0803:点~求平均的话(1+2+3+..+N-1)*N/N所以就为O(N*N) 01/30 00:37
9F：→ NOtWorThy:THX 不过第一题好像是ST不是MST 所以我想一条 01/30 09:23
10F：→ NOtWorThy:simple path v1-v2-...-vn不竟是为一一个AT吗? 01/30 09:23
11F：→ NOtWorThy:还有可能超过一条吗?? 01/30 09:24
12F：推 hahaha86888:第一题FALSE吧...题目说must耶 01/31 14:57