112 年 國立成功大學工程科學系碩士班乙組《資料結構》

核心觀念

本題考二元樹的三種深度優先走訪方式：

• 中序走訪：左子樹 → 根節點 → 右子樹。
• 前序走訪：根節點 → 左子樹 → 右子樹。
• 後序走訪：左子樹 → 右子樹 → 根節點。

依原圖，根節點為 1；1 的左、右子節點分別為 7、9；7 的子節點為 3、4，3 的子節點為 2、5；9 的子節點為 6、8。

解題方法

依各種走訪的固定順序，從根節點開始，分別走訪左、右子樹。每個子樹也套用相同規則：

核心觀念

本題考有向加權圖的最短路徑。路徑只能沿箭頭方向前進，路徑成本是沿途邊權重的總和。各邊權重皆非負，因此可用戴克斯特拉演算法：每次選取目前暫定距離最小的頂點，確定其距離，再用 $d(v)\leftarrow\min\{d(v),d(u)+w(u,v)\}$ 更新相鄰頂點。

解題方法

依原圖，$G$ 在右上、$C$ 在左下；重要方向與權重如下，參數 $m$、$b$、$a$ 分別標在 $A\to H$、$E\to I$、$F\to E$：

以下「確定距離順序」列出戴克斯特拉演算法依序確定的頂點與距離；其他候選距離若大於已知標籤，就不會取代它。

(a) $m=18,\ b=11,\ a=5$，由 $A$ 到 $J$

從 $A$ 出發，先得到 $d(H)=18$、$d(B)=21$。接著 $H$ 更新出 $d(I)=48$、$d(G)=64$；$B$ 經 $C$ 得 $d(C)=39$；$I$ 更新出 $d(J)=89$；$C$ 再得到 $d(D)=69$。

確定距離順序為：

$J$ 的最短距離由 $I\to J$ 得到，因此最短路徑為 $A\to H\to I\to J$，成本為 $18+30+41=89$。例如，經 $G,F$ 到 $J$ 的成本為 $18+46+41+33=138$，較大。

(b) $m=34,\ b=33,\ a=31$，由 $E$ 到 $C$

從 $E$ 出發，$d(D)=30$、$d(I)=33$。先確定 $D$ 時，經 $D\to I$ 得到的候選距離為 $63$，不優於 $I$ 的 $33$。確定 $I$ 後，$d(B)=51$、$d(C)=74$、$d(A)=54$、$d(J)=74$；再由 $B\to C$ 將 $d(C)$ 更新為 $51+18=69$。

確定距離順序為：

解題方法

由原卷提示可讀出：陣列第 1 格存非零項數 $K$；之後每兩格依序存一組「係數、指數」。第 (b) 小題的原卷式子為 $P(x)=7x^5+9x^3+6$。

核心觀念

若多項式有 $K$ 個非零項，表示法為

其中 $A_1=K$，而第 $i$ 項由係數與指數組成一對，依序寫入陣列。指數為 $0$ 的項代表常數項。

逐題推導

(a) 給定陣列共有 $11$ 個元素，因此 $K=(11-1)/2=5$。從第 2 格起依序配對：

每一對分別表示一項係數與指數，因此

(a)
前綴：- - + - + A B C D E F
後綴：A B + C - D + E - F -

(b)
前綴：+ * / G - + H I J K * L - M N

核心觀念

本題涵蓋《資料結構》與《演算法分析》四大核心主題：

1. 時間與空間複雜度分析（Asymptotic Notation & Complexity）：漸進符號之成長階次（Order of Growth）、多項式 Big-$O$ 漸進上界表示法、空間複雜度計算。
2. 基本資料結構特性（Data Structures & Memory Allocation）：多項式之順序陣列表示法（Array Representation of Polynomials）、陣列與鏈結串列（Array vs. Linked List）在存取模式（Random Access vs. Sequential Access）與記憶體空間開銷（Memory Overhead）之比較。
3. 排序演算法機制與性質（Sorting Algorithms & Properties）：
   • 快速排序法（Quicksort）：最佳與最差情況之遞迴關係式與分割分析。
   • 穩定排序（Stable Sort）之精確定義與典型排序演算法（Heap Sort, Merge Sort）之穩定性與時間複雜度比較。
   • 插入排序法（Insertion Sort）及其變體之漸進時間複雜度界限。
   • 堆積排序法（Heap Sort）之原位排序（In-place Sorting）空間複雜度特性。

解題方法

本題為 10 題是非題，解題切入點如下：

1. 依據時間複雜度定義，比較漸進階次 $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n)$，釐清執行時間隨資料量 $n$ 成長之快慢關係。
2. 多項式若採用「按指數儲存係數」之順序陣列（Dense Array Representation），陣列長度需由最高次數（Degree $d$）決定，長度為 $d + 1$。
3. 比較連續記憶體（Array，支援 $O(1)$ 隨機存取）與指標連結（Linked List，僅支援 $O(n)$ 順序存取且需額外指標空間）之結構差異。
4. 針對 Quicksort，檢驗 Pivot 選擇對分割品質與遞迴關係式（Recurrence Relation）之影響；對雙向優化 Insertion Sort 進行搬移次數之最差情況界限估算。
5. 嚴格區分「穩定排序（Stable Sort）」與「時間複雜度在不同 Case 下保持恆定」之概念差異。

選項分析

(1) False

• 題目原文：If we sort time complexity by execution time, O(n²)<O(nlogn).
• 詳解：當輸入規模 $n \to \infty$ 時，時間複雜度之漸進階次關係為 $O(n \log n) < O(n^2)$。階次越小代表演算法的執行時間成長越慢、執行效率越高。因此，就執行時間而言，$O(n \log n)$ 的執行時間少於 $O(n^2)$，敘述寫成 $O(n^2) < O(n \log n)$ 為錯誤。

(2) False

• 題目原文：The Big-O of the polynomial 8n+5n+51 is O(n²).
• 詳解：多項式 $f(n) = 8n + 5n + 51 = 13n + 51$，其最高次項為 $n^1$。在演算法複雜度分析中，漸進緊密上界（Tight Upper Bound）應表示為 $O(n)$。雖然數學定義上 $13n + 51 \in O(n^2)$，但在資料結構與演算法之標準規範中，多項式之 Big-$O$ 階次必由其最高次方決定，故該敘述將其標註為 $O(n^2)$ 屬錯誤表示。

(3) True

• 題目原文：If the polynomial f(x)=16x+8x+63x+85x stored by coefficients, you need an array of length 7.
• 詳解：原題多項式最高次方項為 $x^6$（即 $f(x) = 16x^6 + 8x^4 + 63x^2 + 85x^0$）。若採用係數陣列表示法（Dense Coefficient Array），必須為指數 $0$ 到最高次數 $d$ 的每一個次方分配一個陣列元素位置。當最高次數 $d = 6$ 時，需要的陣列長度為 $d + 1 = 6 + 1 = 7$（對應索引 $0, 1, 2, 3, 4, 5, 6$）。故敘述正確。

(4) False

• 題目原文：The linked-list allows random access, but arrays only allow sequence access.
• 詳解：陣列（Array）佔用連續記憶體空間，可透過基底位址與索引直接計算記憶體位址，支援 $O(1)$ 時間的隨機存取（Random Access）；而鏈結串列（Linked List）的節點散佈於記憶體中，必須自頭節點（Head）順著指標逐一走訪，僅支援 $O(n)$ 時間的順序存取（Sequential Access）。題目將兩者的存取特性顛倒敘述，故為錯誤。

(5) True

• 題目原文：When the type and number of elements are the same, the memory space used by linked-list will be more than array.
• 詳解：若儲存相同的資料型別與元素個數，陣列僅需儲存資料本身；鏈結串列的每個節點除了儲存資料欄位（Data Field）之外，還必須額外配置指標欄位（Pointer Field，如 next 或 prev）以維護節點間的連結關係。因此鏈結串列的記憶體空間開銷必定大於陣列。故敘述正確。