111 年 國立成功大學電機工程學系碩士班已組《資料結構》

核心觀念

Stack（堆疊）是一種遵循「後進先出」原則的線性資料結構，即 LIFO（Last In, First Out）。

堆疊的新增與刪除都在同一端進行，此端稱為 top：

• 新增節點：push
• 移除節點：pop

因此，最後放入堆疊的節點，會最先被移除。

解題方法

判斷堆疊的存取規則：

1. 節點依序加入：$A \rightarrow B \rightarrow C$
2. 移除時，最先取出的是最後加入的 $C$
3. 存取順序為：

$$C \rightarrow B \rightarrow A$$

這正是 Last In, First Out，也就是 LIFO。

選項分析

核心觀念

Linked list（鏈結串列）的 index 用來表示節點在串列中的位置，因此必須使用能表示整數位置的資料型態。

例如：

• 第 1 個節點的索引可表示為 $1$
• 第 2 個節點的索引可表示為 $2$
• 若採用從 $0$ 開始的索引，則位置可表示為 $0,1,2,\ldots$

索引表示的是「第幾個位置」，本質上是整數，因此答案為 Integer。

解題方法

判斷 index 的功能即可：

1. index 用來標示節點的位置。
2. 位置通常以連續的整數表示。
3. 因此鏈結串列的 index 應為整數型態。

題目中的空格應填入：

A linked list index is an Integer representing the position of a node in a linked list.

選項分析

• (A) an Integer：正確

核心觀念

本題考查陣列（array）與鏈結串列（linked list）的基本結構與儲存方式。

• 陣列：元素通常連續配置在記憶體中，屬於密集式（dense）資料結構；陣列大小通常在建立時決定，因此屬於靜態資料結構。
• 鏈結串列：由多個節點（node）組成，每個節點通常包含：
  1. 資料欄位（data 或 information）
  2. 指向下一個節點的指標（next pointer）

鏈結串列的節點不要求在記憶體中連續存放，而是透過指標串接各節點。

解題方法

判斷每個選項是否符合陣列與鏈結串列的正式定義。

其中要特別注意「指標儲存的是什麼」：

• 指標儲存的是下一個節點的記憶體位址。
• 指標不是用來直接儲存下一個資料元素本身。
• 因此，若選項把 pointer 說成直接儲存 next data element，便是不精確且錯誤的敘述。

選項分析

(A) Arrays are dense lists and static data structure

此敘述正確。

陣列的元素通常連續儲存在記憶體中，例如：

$$A[0], A[1], A[2], \ldots, A[n-1]$$

若每個元素大小為 $w$，則第 $i$ 個元素的位址可由下式直接計算：

$$\operatorname{Address}(A[i]) = \operatorname{Base}(A) + i \times w$$

這種連續配置使陣列具有密集式結構。傳統陣列的容量通常在建立時決定，無法任意動態增加，因此歸類為靜態資料結構。

(B) data elements in a linked list need not be stored in adjacent space in memory

此敘述正確。

鏈結串列的節點不需要連續配置在記憶體中。例如：

核心觀念

本題考查佇列（queue）的基本特性：先進先出（First In, First Out，FIFO）。

佇列的運作方式類似超市排隊：

• 最先加入佇列的資料，最先被取出。
• 加入資料通常稱為 enqueue。
• 移除資料通常稱為 dequeue。
• 新資料從佇列尾端加入，資料從佇列前端移除。

因此，題目所描述的「the first one in line is the first one out」正是 FIFO 的定義。

解題方法

辨識資料結構的核心規則即可：

$$\text{最先進入的元素} \longrightarrow \text{最先離開}$$

這種「先進先出」的資料結構是佇列（queue）。

鏈結串列（linked list）只是實作佇列的一種方式，並不會改變佇列的 FIFO 特性。例如：

$$A \rightarrow B \rightarrow C$$

若依序加入 $A$、$B$、$C$，則移除順序為：

$$A \rightarrow B \rightarrow C$$

選項分析

• (A) queue linked list：正確

  題目描述的是 queue，也就是佇列。佇列可使用鏈結串列實作，並且符合先進先出，因此此選項為正確答案。

核心觀念

線性資料結構（linear data structure）是指資料元素依序排列，除了第一個與最後一個元素外，每個元素通常都具有唯一的前驅與唯一的後繼。

常見線性資料結構包括：

• 字串（String）
• 串列（List）
• 堆疊（Stack）
• 佇列（Queue）
• 陣列（Array）

其共同特徵是資料呈現單一路徑的順序關係；相對地，樹（Tree）與圖（Graph）屬於非線性資料結構，因為一個節點可能連結多個後續節點。

解題方法

本題要求判斷各選項是否屬於線性資料結構。逐一檢查其資料元素是否以順序方式排列：

1. 字串由一連串字元依序組成。
2. 串列由多個元素依序連接而成。
3. 佇列中的元素依照先進先出（FIFO）順序排列。

三者都符合線性資料結構的定義，因此應選擇「以上皆是」。

選項分析

(A) Strings

字串是由字元按照特定順序排列所形成的序列，例如：

$$\text{DATA} = [D, A, T, A]$$

每個字元具有明確的位置與前後順序，因此字串屬於線性資料結構。

本選項正確。

(B) Lists

串列由一系列依序排列的資料元素組成。以單向鏈結串列為例，每個節點通常包含資料與指向下一個節點的連結：

核心觀念

資料結構可依資料元素之間的組織關係，分為：

• 線性資料結構（linear data structure）：資料元素依序排列，除第一個與最後一個元素外，每個元素通常只有一個前驅與一個後繼。例如陣列、鏈結串列、堆疊、佇列。
• 非線性資料結構（non-linear data structure）：資料元素不是單一路徑排列，而是呈現階層式或網狀關係，一個元素可連結至多個其他元素。例如樹與圖。

本題詢問哪一種資料結構屬於非線性資料結構。

解題方法

判斷資料結構的基本連結關係：

1. 若資料元素呈單一路徑排列，屬於線性資料結構。
2. 若資料元素具有階層、分支或多重連結關係，屬於非線性資料結構。

樹以根節點為起點，節點之間形成父子階層關係；一個節點可以擁有多個子節點，因此不是單一路徑排列，屬於非線性資料結構。

選項分析

• (A) Arrays

  陣列中的元素依索引順序排列，例如：

  $A[0], A[1], A[2], \ldots, A[n-1]$

  每個元素通常依序對應前後位置，屬於線性資料結構。因此本選項錯誤。

• (B) Linked lists

核心觀念

本題考查雙端佇列（deque, double-ended queue）的兩種限制型態。

一般雙端佇列允許：

• 從前端或後端插入
• 從前端或後端刪除

若限制其中一種操作，則有：

1. 輸入受限雙端佇列（input-restricted deque）
   只能在固定一端插入，但可從兩端刪除。

2. 輸出受限雙端佇列（output-restricted deque）
   可從兩端插入，但只能從固定一端刪除。

題目要求：

• 刪除：兩端皆可
• 插入：只能一端

因此符合輸入受限雙端佇列。

解題方法

直接比較題目描述與兩種受限雙端佇列的定義：

資料結構	插入限制	刪除限制
Input-restricted deque	只能一端插入	兩端皆可刪除
Output-restricted deque	兩端皆可插入	只能一端刪除

題目所述「deletions at both ends but insertion at only one end」完全符合第一列，因此正確答案為 Input-restricted deque。

選項分析

(A) Input-restricted dequeuer

核心觀念

在鏈結串列（linked list）中，START 通常指向串列的第一個節點。

當：

$$\text{START} = \text{NULL}$$

表示目前沒有任何節點，亦即鏈結串列為空（empty linked list）。

若此時要從串列中刪除或取出資料，便會因為串列中沒有元素而發生 underflow（下溢）。

---

解題方法

判斷 START=NULL 所代表的狀態：

1. START 不指向任何節點。
2. 鏈結串列中沒有資料元素。
3. 對空串列進行刪除、取出等操作時，會發生 underflow。

因此，本題所描述的是鏈結串列的空串列狀態，對其進行取出或刪除操作即屬於 underflow。

---

選項分析

• (A) underflow：正確

核心觀念

本題考查資料結構能否儲存「異質資料元素（heterogeneous data elements）」。

• 同質資料結構：所有元素必須具有相同資料型別，例如整數陣列。
• 異質資料結構：不同欄位或元素可以具有不同資料型別，例如一筆記錄同時包含姓名、年齡與成績。

解題方法

逐一判斷各資料結構對資料型別的限制：

1. 若結構要求所有元素型別相同，便不能儲存異質資料。
2. 若結構允許不同欄位使用不同型別，便能儲存異質資料。

選項分析

(A) Arrays

陣列的基本定義是：由固定數量、相同資料型別的元素所組成，且元素通常連續儲存於記憶體中。

例如：

$$\texttt{int A[3] = \{10,20,30\}}$$

陣列中的每個元素都必須是 int 型別，不能直接在同一陣列中放入整數、浮點數與字串。因此陣列不能儲存異質資料元素。

此選項正確。

(B) Records

Record（記錄）由多個欄位組成，不同欄位可以具有不同型別。例如：

核心觀念

本題考查：

• Stack（堆疊）：後進先出（LIFO, Last In First Out）。
• Queue（佇列）：先進先出（FIFO, First In First Out）。
• 將元素從佇列取出後，再依取出順序逐一推回堆疊。

解題方法

五個元素依序推入堆疊：

$$A \rightarrow B \rightarrow C \rightarrow D \rightarrow E$$

此時堆疊頂端為 $E$：

$$\text{Stack：} [A,B,C,D,E]$$

連續彈出四次，彈出順序依堆疊的後進先出原則為：

$$E,\ D,\ C,\ B$$

每個彈出的元素依序插入佇列，因此佇列內容由前端到後端為：

$$\text{Queue：} [E,D,C,B]$$

堆疊中尚未彈出的元素只剩：

$$\text{Stack：} [A]$$

接著從佇列移除兩個元素。佇列遵循先進先出，因此移除順序為：

$$E,\ D$$

將這兩個元素依序推回堆疊：

1. 推入 $E$：$\text{Stack}=[A,E]$
2. 推入 $D$：$\text{Stack}=[A,E,D]$

此時堆疊頂端為 $D$，所以最後彈出的元素是：

$$D$$

核心觀念

在圖論中，若邊 $e$ 連接頂點 $u$ 與 $v$，可表示為：

$$e=[u,v]$$

則 $u$ 與 $v$ 分別是邊 $e$ 的兩個端點。對無向圖而言，兩個頂點之間存在一條邊相連時，稱它們彼此相鄰；其中一個頂點也可稱為另一個頂點的鄰點。

因此：

• $u$、$v$ 是邊 $e$ 的 endpoints。
• $u$、$v$ 是彼此相鄰的節點，即 adjacent nodes。
• $u$、$v$ 互為 neighbors。

解題方法

直接依據圖論的基本定義判斷：

1. $e=[u,v]$ 表示邊 $e$ 的兩端連接頂點 $u$ 與 $v$。
2. 與同一條邊相連的兩個頂點，稱為該邊的端點。
3. 兩個由邊直接連接的頂點，稱為相鄰節點，也互稱鄰點。
4. 因此選項 $(A)$、$(B)$、$(C)$ 均正確。

選項分析

核心觀念

指標（pointer）是一種變數，其內容儲存另一個資料物件在記憶體中的位址。若 P 儲存陣列 DATA 某個元素的記憶體位址，便可透過 P 存取該元素。

指標不限定只能指向陣列第一個元素，也不會同時儲存資料內容本身。

解題方法

判斷各選項是否符合指標的基本定義：

1. 是否儲存資料元素的位址？
2. 是否錯誤地限制只能指向第一個元素？
3. 是否忽略指標必須與資料物件建立關聯？
4. 是否誤以為指標同時儲存資料內容與位址？

符合「儲存資料元素位址」的選項即為正確答案。

選項分析

• (A) P contains the address of an element in DATA

  正確。指標 P 可以儲存 DATA 中某個元素的記憶體位址，例如：

  $P = \&DATA[i]$

  其中 $\&DATA[i]$ 表示取得 DATA[i] 的位址。這符合指標的基本定義。

• (B) P points to the address of the first element in DATA

解題步驟

1. 後序走訪的最後一個節點必為根節點。
   $\text{post-order}=C\,D\,B\,F\,G\,E\,\underline{A}\;\Rightarrow\;A\text{ 為根}$

2. 從根節點開始，前序走訪的第一個節點必為根節點。
   故正確的前序走訪必以 A 為首字母。

核心觀念

陣列（array）是一種將相同型別元素依照索引排列的線性資料結構。其元素通常配置在一段連續的記憶體空間中，因此各元素會按照索引順序依序儲存。

若陣列第一個元素的位址為 $\text{base}$，每個元素大小為 $w$ bytes，則一維陣列 $A[i]$ 的位址為：

$$\text{LOC}(A[i])=\text{base}+i\times w$$

這種利用固定公式直接計算元素位址的特性，使陣列能夠以 $O(1)$ 時間存取指定索引。

解題方法

題目問陣列元素在記憶體中的儲存方式。陣列的標準定義是：元素依照邏輯順序配置於連續記憶體位置。

例如陣列：

$$A=[10,20,30,40]$$

若每個元素占用 $4$ bytes，則記憶體位址可能如下：

元素	位址
$A[0]$	1000
$A[1]$	1004
$A[2]$	1008
$A[3]$	1012

核心觀念

本題考查演算法時間複雜度的分析情況（case analysis）。對於輸入規模為 $n$ 的問題，常見的複雜度分析包括：

• 最佳情況（Best case）：所有規模為 $n$ 的輸入中，執行時間最少的情況。
• 最壞情況（Worst case）：所有規模為 $n$ 的輸入中，執行時間最多的情況。
• 平均情況（Average case）：考慮各種輸入出現機率後，計算期望執行時間。
• Null case 並非複雜度理論中的標準分析分類。

若以 $T(I)$ 表示輸入 $I$ 所需的執行時間，輸入規模為 $n$ 的集合記為 $\mathcal{I}_n$，則：

$$T_{\text{best}}(n)=\min_{I\in\mathcal{I}_n}T(I)$$ $$T_{\text{worst}}(n)=\max_{I\in\mathcal{I}_n}T(I)$$

平均情況則通常表示為：

$$T_{\text{average}}(n)=\sum_{I\in\mathcal{I}_n}P(I)\,T(I)$$

其中 $P(I)$ 是輸入 $I$ 出現的機率分布。

解題方法

判斷各選項是否屬於標準的演算法複雜度分析情況即可。資料結構與演算法中，最基本的三種分析方式是最佳情況、最壞情況與平均情況；「Null case」不屬於正式的複雜度分類。

因此選擇 (D) Null case。

選項分析

(A) Best case

正確存在。

最佳情況是指輸入規模固定為 $n$ 時，演算法執行時間最短的輸入情況。

例如，線性搜尋在第一個位置就找到目標值時，執行時間為常數：

$$T_{\text{best}}(n)=\Theta(1)$$

因此 Best case 是複雜度分析中的標準概念。

核心觀念

題目考的是串列（list）的基本操作定義。

依序處理串列中的每一個元素，例如讀取、檢查、列印或計算每個元素，這種操作稱為「走訪」（Traversal）。

走訪的重點是：

• 從串列的起點開始；
• 按照串列的順序逐一處理元素；
• 直到所有元素都被處理完畢。

若串列共有 $n$ 個元素，每個元素處理一次，時間複雜度通常為：

$$O(n)$$

解題方法

題幹中的關鍵描述是：

processing each element in the list

意思是「處理串列中的每一個元素」。這正是 Traversal 的定義。

以陣列為例：

for i = 0 to n - 1
    process(list[i])

此程式會依序存取並處理 $list[0]$ 到 $list[n-1]$，因此稱為串列走訪。

選項分析

(A) Sorting

Sorting 是「排序」，指依照特定規則重新排列元素，例如由小到大排列。

核心觀念

題目考查「資料結構與資料之間關係」的對應。

階層關係是指元素之間具有上下層級，例如：

• 檔案系統中的資料夾與檔案
• 公司組織圖中的主管與部屬
• 家族樹中的祖先與子孫
• 運算式的語法結構

能直接表示此種「父節點—子節點」關係的資料結構是樹（Tree）。在樹中，除了根節點外，每個節點都可以有零個或多個子節點，適合表達一對多的階層結構。

解題方法

判斷資料結構是否適合表示階層關係，可觀察其核心用途：

• 若資料結構主要處理元素的先後順序、兩端插入刪除或優先權，通常不是階層式結構。
• 若資料結構以節點及其父子關係組織資料，則適合表示階層關係。

本題選項中，只有 Tree 具有明確的父子節點結構，因此正確答案為 (C)。

選項分析

(A) Dequeue

Dequeue 通常指 Deque（double-ended queue，雙端佇列），允許在佇列的前端與後端進行插入或刪除。其資料排列主要呈現線性關係，不具備父節點與子節點的階層結構，因此不適合表示階層關係。

(B) Priority

核心觀念

若一個演算法在執行過程中呼叫自己，稱為遞迴（recursion）。

遞迴分為兩種：

• 直接遞迴（direct recursion）：函式直接呼叫自身。
• 間接遞迴（indirect recursion）：函式 $A$ 呼叫函式 $B$，而函式 $B$ 再呼叫函式 $A$，形成循環呼叫。

題幹中的：

An algorithm that calls itself directly or indirectly

意思是「一個直接或間接呼叫自己的演算法」，其定義正是 Recursion。

遞迴通常包含兩個必要部分：

1. 基本情況（base case）：滿足條件時直接得到結果，停止遞迴。
2. 遞迴情況（recursive case）：將問題縮小後再次呼叫自身。

例如計算階乘：

$$n! = \begin{cases} 1, & n=0\\ n(n-1)!, & n>0 \end{cases}$$

其中 $n=0$ 是基本情況，$n(n-1)!$ 是遞迴情況。

解題方法

直接比對題幹中的定義：

「演算法直接或間接呼叫自己」即表示該演算法具有自我呼叫的結構，這就是遞迴。

因此正確選項為：

$$\boxed{\text{(B) Recursion}}$$

選項分析

(A) Sub algorithm

核心觀念

Linked list（鏈結串列）以節點（node）儲存資料，每個節點除了資料欄位外，還包含指向下一個節點的指標。其結構大小不必在建立時固定，能依需求動態配置與釋放記憶體。

典型單向鏈結串列節點可表示為：

$$\text{Node} = (\text{data}, \text{next})$$

鏈結串列的主要特性如下：

• 插入與刪除不需要搬移大量資料，只要調整指標即可。
• 結構大小可動態增加或縮減。
• 不支援如陣列般的直接索引，存取第 $i$ 個元素通常需要從頭節點逐一走訪，時間複雜度為 $O(n)$。
• 每個節點需要額外儲存指標，因此具有額外的記憶體成本。

因此，鏈結串列特別適合資料筆數與結構內容經常變動的情況。

解題方法

判斷資料結構的適用情境，可比較兩種需求：

1. 資料集合是否大致固定？
2. 是否需要頻繁插入、刪除或改變集合大小？

若資料集合相對固定，陣列具有連續記憶體配置與 $O(1)$ 的索引存取優勢，通常更適合。

若資料筆數經常改變，鏈結串列可透過動態配置節點調整大小；在已知插入或刪除位置的節點指標時，操作本身可達到 $O(1)$，不必搬移後續元素，因此較適合此類情境。

本題描述「結構大小與其中資料不斷改變」，符合鏈結串列的主要使用場合，故選擇 (B)。

選項分析

(A) for relatively permanent collections of data

錯誤。

「相對固定的資料集合」通常適合使用陣列。陣列的元素連續儲存，能以索引直接存取：

$$A[i] \text{ 的存取時間} = O(1)$$

鏈結串列若要存取第 $i$ 個節點，必須由頭節點開始逐一走訪，時間複雜度為：

$$O(i) \subseteq O(n)$$

核心觀念

本題考查指標（pointer）的主要用途。指標是一種儲存「記憶體位址」的變數，可透過位址間接存取資料。

在資料結構與 C/C++ 程式設計中，指標常用於：

• 以位址存取陣列或字串元素
• 執行動態記憶體配置
• 建立鏈結串列、樹、圖等動態資料結構

題目要求選出「錯誤」的敘述。

解題方法

逐一判斷選項 A～C 是否為指標的合理用途：

1. 若 A～C 都是正確用途，則選項 D「全部皆錯誤」便為錯誤敘述。
2. 若其中任一項錯誤，D 的敘述仍不一定成立，因為不可能「全部皆錯誤」。

因此，關鍵在於確認 A～C 是否皆為指標的用途。

選項分析

(A) Accessing arrays or string elements

正確。

在 C 語言中，陣列名稱通常會退化（decay）為指向第一個元素的指標。例如：

$$a[i] \equiv *(a+i)$$

因此可以透過指標運算存取陣列元素：

int a[3] = {10, 20, 30};
int *p = a;

printf("%d", *(p + 1));  // 20

字串本質上也是以字元陣列儲存，常使用 char * 指標處理：

char *s = "data";
printf("%c", *(s + 2));  // t

所以，指標確實可用來存取陣列或字串元素。

(B) Dynamic memory allocation

正確。

動態記憶體配置會在執行期間取得記憶體空間，配置函式會回傳該空間的起始位址，因此必須使用指標保存：

核心觀念

本題考查陣列走訪、巢狀迴圈，以及 Two Sum 問題。

函式 twoSum 的用途是：在整數陣列 nums 中，尋找兩個不同位置的元素，使其總和等於 target，並回傳這兩個元素的索引值。

函式回傳型別為 vector<int>：

• 找到符合條件的兩個元素時，回傳 {i, j}。
• 找不到時，回傳空陣列 {}。
• 索引採用 C++ 常見的 0-based indexing，第一個元素的索引為 0。

---

解題方法

程式使用兩層迴圈列舉所有可能的元素配對：

for(int i = 0; i < nums.size(); i++)
{
    for(int j = i + 1; j < nums.size(); j++)
    {
        if(nums[i] + nums[j] == target)
        {
            return {i, j};
        }
    }
}

其中：

• 外層迴圈固定第一個元素 nums[i]。
• 內層迴圈從 i+1 開始尋找第二個元素 nums[j]。
• j 不從 0 開始，是為了避免：
  • 使用同一個元素兩次，例如 i == j；
  • 重複檢查相同配對，例如先檢查 (0,1)，再檢查 (1,0)。

只要找到第一組符合條件的配對，便立即執行：

return {i, j};

因此函式回傳的是第一組被找到的索引，而不是所有符合條件的配對。

---

範例分析

給定：

nums = [2, 7, 8, 13]
target = 10

各元素索引如下：

索引	元素
0	2
1	7
2	8
3	13

程式依序檢查：

1. $nums[0] + nums[1] = 2 + 7 = 9$
2. $nums[0] + nums[2] = 2 + 8 = 10$

第二次檢查符合目標值，因此立即回傳：

{0, 2}

代表：

nums[0] + nums[2] = 2 + 8 = 10

函式回傳的不是元素值 {2, 8}，而是元素的索引 {0, 2}。

---

函式執行流程

vector<int> twoSum(vector<int>& nums, int target) {

接收：

核心觀念

本題考查「最長共同前綴」（Longest Common Prefix, LCP）。

• 前綴：字串從第 $0$ 個字元開始，連續取出的部分。
• 共同前綴：所有字串都擁有、且內容完全相同的前綴。
• 最長共同前綴：在所有共同前綴中，長度最大的部分。

例如：

strs = {"flower", "flow", "flight"}

三個字串的共同前綴為：

"f"、"fl"

其中最長的是 "fl"，因此答案為 "fl"。

---

解題方法

函式先將 strs[0] 當作基準字串，逐一與其他字串比較：

for(int i=1;i<strs.size();i++)

對於每個 strs[i]，最多只能比較到兩字串中較短的長度：

int current_min_len = min(strs[0].length(), strs[i].length());

接著從第 $0$ 個字元開始逐字比較：

for(int j=0;j<current_min_len;j++){
    if(strs[0][j]==strs[i][j]){
        ans_number++;
    }
    else {
        break;
    }
}

ans_number 表示 strs[0] 與目前 strs[i] 的共同前綴長度。

例如：

strs[0] = "flower"
strs[i] = "flow"

逐字比較結果為：

位置	strs[0]	strs[i]	結果
0	f	f	相同
1	l	l	相同
2	o	o	相同
3	w	w	相同

因此：

$$ans\_number=4$$

目前共同前綴為 "flow"。

若某個字串在更早位置發生不相同的字元，函式立即停止比較。例如：

strs[0] = "flower"
strs[i] = "flight"

比較到位置 $2$ 時：

strs[0][2] = 'o'
strs[i][2] = 'i'

因此共同前綴長度為 $2$，即 "fl"。

函式以 first 儲存所有比較結果中的最小共同前綴長度：

if(ans_number < first){
    first = ans_number;
}

原因是：要成為「所有字串」的共同前綴，長度必須受最短的那一組共同前綴限制。因此：

$$LCP(strs)=\min_{1\leq i<n} LCP(strs[0],strs[i])$$

最後：

strs[0].resize(first);
return strs[0];

將基準字串縮短為 first 個字元，並回傳該字串。

---

範例說明

令：

strs = {"flower", "flow", "flight"};

與 strs[0] 比較：

核心觀念

本題考查「使用堆疊判斷括號是否正確配對」，也就是判斷字串是否為合法的括號序列。

合法括號序列必須同時符合：

1. 每個左括號 (、{、[ 都有對應的右括號。
2. 右括號的種類必須與最近尚未配對的左括號相同。
3. 任一處從左至右掃描時，右括號都不能多於左括號。
4. 掃描結束後，不能留下未配對的左括號。

堆疊具有「後進先出」（LIFO）的特性，最上方元素正好代表目前最接近、尚未配對的左括號，因此適合處理巢狀括號。

---

解題方法

函式 isValid(string s) 的用途是：

判斷字串 s 是否只由括號組成，且所有括號皆正確配對、巢狀順序正確。

演算法逐一掃描字串中的每個字元。

1. 長度為奇數時直接判定無效

if (s.size()%2==1) return false;

每一個左括號都必須搭配一個右括號，因此合法字串的長度必定是偶數。

例如：

([)]

長度為 $4$，仍須進一步檢查；但：

(()

長度為 $3$，不可能完全配對。

---

2. 最後一個字元不能是左括號

if(s[s.size()-1]=='('||s[s.size()-1]=='{'||s[s.size()-1]==']')
    return false;

若字串最後是左括號，代表至少有一個左括號沒有右括號配對。

不過此處程式有一個明顯的判斷錯誤：

s[s.size()-1]==']'

應該檢查的是右括號 ']' 對應的左括號 '['，因此若要判斷最後一字元是否為左括號，正確條件應為：

s[s.size()-1]=='(' ||
s[s.size()-1]=='{' ||
s[s.size()-1]=='['

此錯誤不會破壞主要演算法，因為後續掃描仍會正確判斷 ]；只是這個前置判斷沒有完整涵蓋最後為 [ 的情況。

---

3. 遇到左括號便推入堆疊

case '(':
case '{':
case '[':
    save.push(current);
    break;

左括號代表尚待配對，因此推入堆疊。

例如掃描：

{[(

堆疊內容由底至頂為：

{ [ (

最上方的 ( 是最先需要被配對的左括號。

---

4. 遇到右括號時檢查堆疊頂端

以右小括號為例：

case ')':
    if(save.size()==0||save.top()!='(') return false;
    save.pop();
    break;

判斷分成兩部分：

• save.size()==0：沒有左括號可配對，表示右括號過多。
• save.top()!='('：最近的左括號種類不符，表示括號巢狀順序錯誤。

確認配對成功後，將堆疊頂端的左括號移除。

右中括號與右大括號的處理完全相同：

case '}':
    if(save.size()==0||save.top()!='{') return false;
    save.pop();
    break;

case ']':
    if(save.size()==0||save.top()!='[') return false;
    save.pop();
    break;

---

5. 非括號字元直接判定無效

default:
    return false;

此函式只接受六種括號：

( ) { } [ ]

因此輸入英文字母、數字、空白或其他符號，都會回傳 false。

---

6. 掃描結束後檢查堆疊

if(save.size()!=0) {
    if(save.top()=='('||save.top()=='{'||save.top()=='[')
        return false;
}
return true;

若掃描完成後堆疊仍不為空，代表尚有左括號未配對，因此應回傳 false。

由於堆疊中只會推入三種左括號，所以只要 save.size()!=0，save.top() 必定是 (、{ 或 [ 其中之一。此條件實際上等價於：

return save.empty();

因此尾端更清楚的寫法是：

核心觀念

此函式 MM 用來合併兩個已依遞增順序排列的單向鏈結串列，產生一個仍然遞增排列的鏈結串列。

其核心觀念是：

• 單向鏈結串列的節點透過 next 指標連接。
• 若兩串列皆已排序，只需比較兩個串列目前節點的 val。
• 每次取出值較小的節點，接到合併結果後方。
• 重複此程序，直到其中一串列為空。
• 另一串列剩餘部分本身已排序，可直接接到結果尾端。

這是典型的合併排序（merge sort）中的 merge 操作，也常用於合併兩個已排序鏈結串列。

---

解題方法

函式接收兩個指標：

ListNode* MM(ListNode* L1, ListNode* L2)

其中 L1 與 L2 分別指向兩個已排序串列的開頭。

1. 處理空串列

if(L1 == NULL)
    return L2;
else if(L2 == NULL)
    return L1;

若 L1 為空，表示第一個串列沒有節點可合併，因此直接回傳 L2。

若 L2 為空，則直接回傳 L1。

這兩個條件也是遞迴的終止條件。

---

2. 比較兩個目前節點

if(L1->val <= L2->val){
    L1->next = MM(L1->next, L2);
    return L1;
}

當

$$L1\text{->val} \leq L2\text{->val}$$

時，L1 的節點應該排在合併結果的最前面。

接著：

L1->next = MM(L1->next, L2);

代表：

1. 保留目前的 L1 作為結果頭節點。
2. 將 L1 從原串列中往後移一格。
3. 遞迴合併剩餘的 L1 與原本的 L2。
4. 將遞迴結果接到目前 L1 的 next。

最後回傳目前的 L1：

return L1;

---

3. 處理 L2 節點較小的情況

若前面的條件不成立，代表：

$$L1\text{->val} > L2\text{->val}$$

因此應選擇 L2：

L2->next = MM(L1, L2->next);
return L2;

這段程式的意義是：

1. 保留目前的 L2 作為結果頭節點。
2. 將 L2 往後移一格。
3. 遞迴合併原本的 L1 與剩餘的 L2。
4. 將遞迴結果接到目前 L2 的 next。
5. 回傳目前的 L2。

---

運作範例

假設：

L1: 1 → 4 → 7
L2: 2 → 3 → 8

執行過程如下：

比較結果	選出的節點	剩餘待合併串列
$1 \leq 2$	1	4 → 7 與 2 → 3 → 8
$4 > 2$	2	4 → 7 與 3 → 8
$4 > 3$	3	4 → 7 與 8
$4 \leq 8$	4	7 與 8
$7 \leq 8$	7	空串列與 8
第一串列為空	8	合併完成

因此結果為：

1 → 2 → 3 → 4 → 7 → 8

函式不會建立新的節點，而是直接重新調整原有節點的 next 指標。

---