剛考完資料結構 ,來解一下 , 不過下面的今年都沒出~
※ 引述《mt1127 (饅頭)》之銘言：
: 我都被搞混了..能不能請大大解釋一下...
: 1.下列哪個是有|V|個的頂點和|E|的邊的topological sort problem 的執行時間?
: (A)O(V^2) (B)O(V+E) (C)O(ElogV) (D)O(V^3)
(B) O(V+E) ,每次刪去In-dgree為0的點,並刪去它的邊,(共有V個點+E個邊)的operations
: 2.下列哪個是有n個的頂點的All-pairs shortest paths algorithm 的執行時間?
: (A)O(n^2) (B)O(n^2logn) (C)O(n^3) (D)O(n^4)
(C) O(n^3)
: 3.有一個unicycle圖有n個頂點,它有幾個邊?
: (A)n-1 (B)n (C)n+1 (D)n(n-1)/2
(B) n (不過這題我不太確定)
: 4.下列哪個是有|V|個的頂點和|E|的邊的Bellman-Ford algorithm 的執行時間?
: (A)O(V^2) (B)O(V+E) (C)O(ElogV) (D)O(V^3)
O(VE) 這題有個選項應該是這個才對,這題的algo就要麻煩上網找了
: 5.下列哪個是有n個的矩陣的matrix-chain multiplication problem 的執行時間?
: (A)O(nlogn) (B)O(n^2) (C)O(n^2logn) (D)O(n^3)
(D) O(n^3) ,很明顯低當p=q=r=n時(A matrix:pxq ,B matrix qxr) ,T(n)=O(n^3)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.67.210.63