113 年 國立中山大學電機工程學系碩士班丙組《資料結構》

核心觀念

maxHeapify(A, i, n) 的前提是：

• 以左小孩為根的 subtree 已經是 max-heap。
• 以右小孩為根的 subtree 已經是 max-heap。
• 只有 $A[i]$ 可能違反 max-heap order property。

因此，buildMaxHeap 必須採用「後序」處理順序：

1. 先將左 subtree 建成 max-heap。
2. 再將右 subtree 建成 max-heap。
3. 最後呼叫 maxHeapify(B, i, n)，使以 $B[i]$ 為根的 subtree 成為 max-heap。

陣列採用 0-based indexing 時：

完全二元樹中，索引 $i \ge \lfloor n/2 \rfloor$ 的節點沒有小孩，因此是葉節點，本身已經是 max-heap。

解題方法

從節點 $i$ 開始遞迴處理：

• 若 $i \ge \lfloor n/2 \rfloor$，代表目前節點是葉節點，直接結束。
• 否則先遞迴處理左小孩。
• 再遞迴處理右小孩。
• 左右 subtree 都完成後，呼叫 maxHeapify(B, i, n)。

關鍵程式碼

void buildMaxHeap(unsigned int B[], int i, int n) {
    // i >= n / 2 表示 B[i] 是葉節點，已經是 max-heap
    if (i >= n / 2)
        return;

    int leftChild = 2 * i + 1;
    // leftChild 是 B[i] 的左小孩索引

    int rightChild = 2 * i + 2;
    // rightChild 是 B[i] 的右小孩索引

    // 先將左 subtree 建成 max-heap
    buildMaxHeap(B, leftChild, n);

    // 再將右 subtree 建成 max-heap
    buildMaxHeap(B, rightChild, n);

    // 左右 subtree 已經是 max-heap，
    // 將以 B[i] 為根的 subtree 調整成 max-heap
    maxHeapify(B, i, n);
}

呼叫方式為：

buildMaxHeap(B, 0, n);

① 調和級數的漸近時間

核心觀念： 使用調和級數的漸近界。依掃描圖，執行時間為

解題方法： 以積分估計調和級數：

因此 $T(n)=\Theta(\log n)$。對數底數只會造成常數倍差異，不影響漸近界；最簡型式可寫成 $f(n)=\log n$。

解題技巧： 遇到 $\sum_{i=1}^{n}1/i$，可直接辨認為調和級數，其漸近成長為對數級。

② 比較兩個演算法的時間

核心觀念： 比較漸近成長率；輸入規模夠大時，成長較慢的執行時間較佳。

解題方法： 依掃描圖中的公式，演算法 $A$ 的時間為 $n^{\log_2 n}$，演算法 $B$ 的時間為 $\log_2(n^n)$。先化簡 $B$：

比較兩者的比值：

所以 $T_A(n)$ 成長得比 $T_B(n)$ 快；輸入規模夠大時，應選擇演算法 $B$。

解題技巧： 先利用 $\log(a^b)=b\log a$ 化簡，再比較兩式的成長率。

核心觀念

後序式（postfix）把運算子放在運算元之後。由左至右讀取時，遇到數值就放入堆疊；遇到二元運算子，就取出堆疊頂端的兩個數值運算，再把結果放回堆疊。

依原卷圖中的式子，運算式為 $C\ D\ E\ -\ +\ A\ B\ C\ +\ *\ -$。

解題方法

代入 $A=3$、$B=2$、$C=5$、$D=4$、$E=6$，逐步處理：

核心觀念

陣列支援隨機存取，可在 $O(1)$ 時間直接取得中間位置的元素；雙向鏈結串列則只能沿著前後指標逐節點移動，沒有辦法在 $O(1)$ 時間跳到中間位置。二分搜尋要達到 $O(\log n)$，除了比較次數是 $O(\log n)$，每次也必須能有效取得搜尋區間的中間元素。

解題方法

答案：不能在 $O(\log n)$ 時間內判定。

若要在 $L$ 中照二分搜尋的方式找中間節點，必須先從串列的一端逐節點走到中間，這一步就需要 $O(n)$ 時間。接著每次縮小搜尋範圍時，仍須沿著指標移動到新的中間節點。

本題考查圖的兩種基本遍歷演算法：深度優先搜尋 (Depth-First Search, DFS) 和廣度優先搜尋 (Breadth-First Search, BFS)。題目提供了圖的鄰接串列 (adjacency list) 表示法，並指定了遍歷的起始點 (node 0) 和鄰居的拜訪順序規則。

圖的結構分析：
根據圖 3 的 adjacency-lists，我們可以得到節點的鄰居關係：

• Node 0: neighbors are 1, 5. (Visit order: 1 then 5)
• Node 1: neighbors are 0, 2, 3. (Visit order: 0 then 2 then 3)
• Node 2: neighbors are 1, 4. (Visit order: 1 then 4)
• Node 3: neighbors are 1, 4. (Visit order: 1 then 4)
• Node 4: neighbors are 2, 3, 6. (Visit order: 2 then 3 then 6)
• Node 5: neighbors are 0, 4. (Visit order: 0 then 4)
• Node 6: neighbors are 4, 5. (Visit order: 4 then 5)

遍歷規則：

• 起始點：Node 0。
• 拜訪順序：必須嚴格按照 adjacency-list 中列出的順序。
• DFS：使用堆疊 (stack) 或遞迴實現。當訪問一個節點時，標記為已訪問，然後遍歷其鄰居。如果鄰居未被訪問，則遞迴地訪問該鄰居。
• BFS：使用佇列 (queue) 實現。當訪問一個節點時，標記為已訪問，並將其加入佇列。然後從佇列中取出節點，遍歷其鄰居。如果鄰居未被訪問，則標記為已訪問並加入佇列。

① 深度優先搜尋 (DFS) 的拜訪順序：

我們從 node 0 開始。使用遞迴或堆疊來模擬 DFS。

1. Visit 0: Mark 0 as visited. Add 0 to the result list.
   Result: [0]
   Neighbors of 0: 1, 5. Visit 1 first.

2. Visit 1: Mark 1 as visited. Add 1 to the result list.
   Result: [0, 1]
   Neighbors of 1: 0, 2, 3. Node 0 is visited. Visit 2 next.

3. Visit 2: Mark 2 as visited. Add 2 to the result list.
   Result: [0, 1, 2]
   Neighbors of 2: 1, 4. Node 1 is visited. Visit 4 next.

4. Visit 4: Mark 4 as visited. Add 4 to the result list.
   Result: [0, 1, 2, 4]
   Neighbors of 4: 2, 3, 6. Node 2 is visited. Visit 3 next.

5. Visit 3: Mark 3 as visited. Add 3 to the result list.
   Result: [0, 1, 2, 4, 3]
   Neighbors of 3: 1, 4. Node 1 is visited. Node 4 is visited. No unvisited neighbors from 3. Backtrack to 4.

6. Backtrack from 3 to 4. All neighbors of 4 (2, 3) have been visited. Backtrack to 2.

7. Backtrack from 4 to 2. All neighbors of 2 (1, 4) have been visited. Backtrack to 1.

8. Backtrack from 2 to 1. Next neighbor of 1 is 3. Node 3 is already visited. No more unvisited neighbors from 1. Backtrack to 0.

9. Backtrack from 1 to 0. Next neighbor of 0 is 5. Visit 5.

10. Visit 5: Mark 5 as visited. Add 5 to the result list.
    Result: [0, 1, 2, 4, 3, 5]
    Neighbors of 5: 0, 4. Node 0 is visited. Node 4 is visited. No unvisited neighbors from 5. Backtrack to 0.