假設一個無向圖(undirected graph)的邊(edges)如下:
S, T S, Z T, Y T, Z V, Y V, Z Y, Z
(一)使用堆疊(stack),從 S 開始,進行深度優先走訪(depth-first traversal),請寫出走訪結果。(10 分)
(二)使用佇列(queue),從 S 開始,進行廣度優先走訪(breadth-first traversal),請寫出走訪結果。(10 分)
對下列程式片段,請用 Big-O 符號(Big-O notation),分別估計最長執行時間(worsttime)。注意:S 中沒有與 n 相關的迴圈(n-dependent loops)。(每小題5 分,共20 分)
(一)for (int i = 0; i * i < n; i++) S
(二) for (int i = 1; i < n+1; i*=2) S
(三) for (int i = 1; i < n+1; i*=2)
for (int j = 0; j < n; j++) S
(四) k=1; for (int i=0; i {k*=3; for (int j=0; j