成大 111 年資管所 資料結構 參考答案

$f_3\prec f_1\approx f_2\approx f_4\prec f_5$

$f_3=\Theta ({\log }^{2}n)$；$f_1=\frac{1}{2}n\log n-\frac{1}{2}n$、$f_2=\log n!\approx n\log n-n\log e$（Stirling）、$f_4=n\log n$ 三者皆為 $\Theta (n\log n)$；$f_5=(4/3{)}^n$ 為指數。

Heap（Priority Queue）。持續插入新訊息並反覆取出優先權最高者，Insert 與 Extract 皆為 $O(\log n)$。

Queue。依收單先後出餐為 FIFO，新訂單從隊尾 enqueue、完成的從隊首 dequeue，皆為 $O(1)$。

AVL Tree。資料保持有序，inorder 走訪 $O(n)$ 即得排序名單；依名字查詢與插入新球員皆為 $O(\log n)$。

B-tree。節點大小對齊磁碟區塊、fanout 高使樹很矮，插入只需 $O({\log }_{m}n)$ 次磁碟存取，適合大量外部資料的頻繁插入。

Move-to-front List。資料不可比較，AVL Tree 無法依大小建樹；Move-to-front List 只需判斷相等，且每次 Find 後把該元素移到最前端，常被查的資料很快就能找到。

void rearrange(int b[], int n) {
    int start = 0, end = n - 1, i = 0, t;
    while (i <= end) {
        if (b[i] < 0) {                 /* 負數 → 換到左區 */
            t = b[i]; b[i] = b[start]; b[start] = t;
            start++; i++;
        } else if (b[i] > 0) {          /* 正數 → 換到右區，i 不前進 */
            t = b[i]; b[i] = b[end]; b[end] = t;
            end--;
        } else {                        /* 零 → 留在中區 */
            i++;
        }
    }
}

最終 heap（層序，A[0] 為根）：[1, 4, 2, 3, 6, 5, 9, 8, 7]

最終 heap（層序，A[0] 為根）：[2, 4, 7, 3, 6, 5, 9, 8]

left：$3i+1$；middle：$3i+2$；right：$3i+3$

最少 33、最多 127。

最少 0 次、最多 1 次。插入後只需對第一個失衡節點做一次單旋或雙旋，該子樹高度即恢復插入前的值，祖先不再失衡。

取首、中、尾三個元素的中位數為 pivot。本例首 11、中 7（index 6）、尾 35，中位數為 11，pivot $=11$。

第 1 層：pivot 11 → [6, 7, 1, 10]｜[19, 13, 20, 21, 15, 14, 17, 35]

第 2 層：pivot 7 → [6, 1]｜[10]；pivot 21 → [19, 13, 20, 15, 14, 17]｜[35]

第 3 層：pivot 6 → [1]｜（空）；pivot 19 → [13, 15, 14, 17]｜[20]

第 4 層：pivot 15 → [13, 14]｜[17]

第 5 層：pivot 13 → （空）｜[14]

排序結果：1, 6, 7, 10, 11, 13, 14, 15, 17, 19, 20, 21, 35

hasCycle(G):
    for each v in V: visited[v] = false
    for each v in V:
        if not visited[v] and dfs(v, -1): return true
    return false

dfs(u, parent):
    visited[u] = true
    for each w in adj[u]:
        if not visited[w]:
            if dfs(w, u): return true
        else if w != parent:      # 非沿路來源的邊繞回已走訪節點
            return true
    return false

Stack 存 (vertex, parent)，鄰居由大到小 push，使較小者先 pop；pop 出未訪問的頂點即加入 tree edge。

Stack 變化（左為頂）：[(1,–)] → [(2,1),(4,1)] → [(3,2),(5,2),(4,1)] → [(5,3),(5,2),(4,1)] → [(5,2),(4,1)] → [(4,1)] → []

Spanning Tree 邊集合：1-2、2-3、3-5、1-4

最大 degree 為 4（頂點 9），取分量 $\{6,\dots ,11\}$。

邊依權重排序後逐一檢查：加入 $9\text{-}7(1)$、$9\text{-}10(2)$、$7\text{-}6(2)$、$10\text{-}11(2)$；$9\text{-}6(3)$、$7\text{-}11(4)$ 成環捨棄；加入 $9\text{-}8(6)$。

MST 邊集合：$9\text{-}7(1)$、$9\text{-}10(2)$、$7\text{-}6(2)$、$10\text{-}11(2)$、$9\text{-}8(6)$，總權重 13。

Floyd(W, n):
    for i = 1 to n:
        for j = 1 to n:
            c[i][j] = W[i][j]          # 直接邊的權重，無邊為 INF，i=j 為 0
    for k = 1 to n:                    # k 必須在最外層
        for i = 1 to n:
            for j = 1 to n:
                if c[i][k] + c[k][j] < c[i][j]:
                    c[i][j] = c[i][k] + c[k][j]
    return c

$c(i,j,k)=min(c(i,j,k-1),c(i,k,k-1)+c(k,j,k-1))$，$k=n$ 時即為 all-pairs 最短距離。

$4\to 2\to 5\to 8\to 6\to 7$

選 11。除法雜湊的除數應取質數：8、9、27 分別為 $2^3$、$3^2$、$3^3$，取餘數時 key 的規律（低位元、3 的倍數）會保留下來，使餘數集中在少數 bucket；11 是質數，最能把 key 平均分散。

• Differential File：把新增與修改的資料先寫進獨立的小型差異檔，累積後再與主檔批次合併，避免每筆異動都重組主檔。
• 使用方式：用 $k$ 個 hash function 把差異檔中有異動的 key 對應到 bit array 並設為 1。查詢時先查 Bloom Filter：任一位元為 0 表示確定未異動，直接讀主檔；全為 1 表示可能有異動，才去查差異檔。