108 年 國立成功大學會計學研究所乙組《資料結構》

核心觀念

本題考查鏈結串列的搜尋時間複雜度。

在循環雙向鏈結串列中：

• 每個節點包含資料、next 指標與 prev 指標。
• 最後一個節點的 next 指向第一個節點。
• 第一個節點的 prev 指向最後一個節點。
• 雖然可以向前或向後走訪，但節點通常沒有依照資料值排序，因此搜尋特定資料仍須逐一比對。

雙向性只能讓「已知某節點後往前或往後移動」更方便，不能直接將搜尋範圍縮小為一半，也不會自動形成二分搜尋。

解題方法

假設從某個起始節點開始搜尋：

1. 先檢查目前節點的資料。
2. 若不是目標節點，沿著 next 或 prev 指標移動。
3. 最差情況下，目標節點位於最後才檢查到，或目標不存在。
4. 此時最多需要檢查 $N$ 個節點。

因此，搜尋所需時間為

循環結構只影響走訪方式，不改變最差情況下必須檢查 $N$ 個節點的事實。

選項分析

A. $O(1)$

錯誤。

$O(1)$ 表示不論節點數量 $N$ 多大，都只需固定時間完成搜尋。若只知道起始節點與目標資料，仍須逐一走訪節點，無法保證固定步數完成。

核心觀念

本題考查 虛擬碼（pseudo code） 的定義。

虛擬碼是一種以接近自然語言、結合程式設計結構所寫成的演算法描述方式，用來表達程式或演算法的操作流程。它不受特定程式語言語法限制，重點在於清楚呈現：

• 執行順序
• 條件判斷
• 迴圈結構
• 資料處理流程

題目中的關鍵敘述是：

an informal high-level description of the operation principle of a computer program or other algorithm

意思是「以非正式、高階的方式描述電腦程式或演算法的運作原理」，正是虛擬碼的定義。

解題方法

判斷此題可採用「定義對應法」：

1. 找出題幹中的核心描述：
   「非正式」、「高階描述」、「程式或演算法的運作原理」。
2. 對照各選項的用途。
3. 能描述演算法流程的選項即為正確答案。

虛擬碼範例如下：

Algorithm FindMax(A)
    max ← A[1]
    for each element x in A
        if x > max
            max ← x
    return max

這段內容描述尋找陣列最大值的步驟，但不完全遵循 C、Java 或 Python 等特定語言的語法，因此屬於虛擬碼。

選項分析

A. pseudo code

正確。

Pseudo code 即「虛擬碼」，以接近人類語言及一般程式結構的方式描述演算法，不要求符合特定程式語言的完整語法。

題幹對虛擬碼的描述包括：

核心觀念

本題考查堆疊（stack）的後進先出（Last In, First Out, LIFO）特性：

• 插入資料稱為 push，資料從堆疊頂端加入。
• 移除資料稱為 pop，只能從堆疊頂端移除。
• 先插入的資料，通常會較晚被移除。

初始堆疊由頂端至底端為：

解題方法

依序將 $a$、$b$ 插入堆疊：

1. 插入 $a$：

2. 插入 $b$：

接著移除三個項目：

• 第一次移除：$b$

• 第二次移除：$a$

• 第三次移除：$x$

因此最後堆疊內容由頂端至底端為：

選項分析

核心觀念

本題考查 Quick Sort 的時間複雜度。Quick Sort 透過以下步驟排序：

1. 選擇一個樞紐元素（pivot）。
2. 將資料分割成小於與大於 pivot 的兩部分。
3. 對左右子序列遞迴排序。

若每次分割大致平均，遞迴關係為：

其中，$O(n)$ 是一次分割所需的時間。由主定理可得：

因此，Quick Sort 的平均時間複雜度為 $O(n\log n)$。

題目未註明最佳、平均或最壞情況；依選擇題通常採用的平均情況判斷，答案為 C。

解題方法

將排序過程視為遞迴樹：

• 每一層所有分割操作合計約需 $O(n)$。
• 若每次分割均衡，遞迴深度約為 $\log n$。
• 總時間為：

Quick Sort 的複雜度整理如下：

最壞情況的遞迴關係為：

因此：

核心觀念

**Memory leak（記憶體洩漏）**是指程式在執行期間配置了動態記憶體，但使用完畢後沒有正確釋放，導致這些記憶體雖然已無法再被程式使用，卻仍被系統占用。

記憶體洩漏通常具有以下特徵：

• 發生在程式執行期間。
• 需要追蹤記憶體的配置與釋放情形。
• 可藉由檢查「已配置但尚未釋放」的記憶體區塊加以偵測。

因此，這類問題適合使用**執行時期檢查（runtime checking）**或動態分析工具處理。

解題方法

判斷各選項是否能偵測 memory leak 的關鍵，在於確認該技術是否會在程式執行時追蹤：

1. 哪些記憶體區塊被配置；
2. 哪些記憶體區塊已被釋放；
3. 程式結束或特定檢查點時，是否仍有配置後未釋放的記憶體。

若某區塊符合：

便可能構成 memory leak。這正是 runtime checking 的用途。

選項分析

A. runtime interpretation

Runtime interpretation（執行時期解譯）是指程式在執行時由解譯器逐步解讀並執行指令，例如某些直譯式語言的執行方式。

它描述的是程式如何被執行，並不等同於追蹤記憶體配置與釋放。因此，單靠 runtime interpretation 無法直接偵測 memory leak。

錯誤。

B. runtime execution

Runtime execution（執行時期執行）只是泛指程式實際執行的階段。

在 C/C++ 中，& 產生變數的記憶體位址，稱為 取址（address‑of）運算子，其語意為「取得變數的參考（r

核心觀念

本題考查「自我平衡搜尋樹」的種類與用途。

自我平衡搜尋樹會在插入、刪除資料後，透過旋轉、分裂、合併等操作維持樹高，使搜尋、插入、刪除維持良好效率。典型的二元搜尋樹結構包括：

• AVL tree
• Red-black tree

B-tree 雖然不是二元樹，而是多路搜尋樹，但也是常見的自我平衡搜尋樹，主要用於磁碟、資料庫與檔案系統。

R+ tree 則屬於空間索引結構，主要用來處理多維幾何資料，不是二元搜尋樹，也不是一般意義下的自我平衡搜尋樹。

解題方法

判斷每個選項是否屬於自我平衡搜尋樹，主要檢查兩點：

1. 是否維持搜尋樹的有序性？
2. 是否透過結構調整維持樹高平衡？

其中，AVL tree 與 red-black tree 是二元搜尋樹；B-tree 是多路平衡搜尋樹。R+ tree 的設計目標是空間資料索引，不是依照單一鍵值進行二元搜尋。

因此，不符合題意的選項是 R+ tree。

選項分析

A. AVL tree

AVL tree 是典型的自我平衡二元搜尋樹。

對任一節點，左右子樹高度差的絕對值至多為 $1$：

插入或刪除造成失衡時，AVL tree 會透過單旋轉或雙旋轉恢復平衡。因此搜尋、插入、刪除的時間複雜度通常為：

所以 A 正確屬於自我平衡二元搜尋樹。

B. red-black tree

Red-black tree 是另一種常見的自我平衡二元搜尋樹。每個節點具有紅色或黑色標記，並遵守紅黑樹的平衡規則，例如：

核心觀念

Dictionary（字典）是一種抽象資料型態，用來維護一組資料，並支援以下基本操作：

• Search：依照鍵值（key）尋找資料。
• Insert：加入新的鍵值與資料。
• Delete：刪除指定鍵值的資料。

字典的重點在於：資料通常透過唯一的鍵值識別，目標是讓搜尋、插入與刪除都能有效率地完成。

Hash table（雜湊表）利用雜湊函數將鍵值轉換為陣列索引：

在雜湊函數設計良好、碰撞（collision）受到控制時，搜尋、插入與刪除的平均時間複雜度皆可達到：

因此，Hash table 是實作 Dictionary 最典型的資料結構之一。

解題方法

題目問的是「哪一種資料結構用來解決 Dictionary 的實作問題」。

判斷重點是比較各選項是否適合支援：

1. 依鍵值快速搜尋；
2. 動態插入資料；
3. 依鍵值刪除資料。

Hash table 會先透過雜湊函數計算資料應存放的位置，再進行搜尋、插入或刪除。若發生不同鍵值對應到同一位置的碰撞，可使用 chaining（鏈結串列法）或 open addressing（開放定址法）處理。

因此，Hash table 能直接針對 Dictionary 的核心需求提供高效率操作。

選項分析

A. hash table

正確。

Hash table 以 key 作為輸入，透過雜湊函數決定資料位置，適合支援 Dictionary 的搜尋、插入與刪除操作。

平均時間複雜度如下：

在雜湊碰撞嚴重或雜湊函數設計不佳時，最差情況可能退化為 $O(n)$，但整體而言仍是實作 Dictionary 的標準選擇。

B. stack

錯誤。

核心觀念

排序依資料是否能全部放入主記憶體，分為：

• 內部排序（internal sorting）：待排序資料可全部放在主記憶體中，主要考量 CPU 運算時間。
• 外部排序（external sorting）：資料量大於主記憶體容量，資料主要存放於磁碟等外部儲存裝置，主要考量磁碟讀寫次數。

外部排序通常將資料分批讀入主記憶體處理，再將中間結果寫回磁碟，最後合併各批排序結果。典型方法是外部合併排序。

本題要從四個選項中，找出適合處理外部資料的排序技術。

解題方法

判斷重點在於：該排序法是否能將資料分割成若干部分，分別處理並儲存於外部裝置，降低主記憶體需求。

Bucket sort（桶排序）會依照資料的鍵值範圍，將資料分配至不同的桶中：

當資料量過大時，各個 bucket 可存放在磁碟中，主記憶體只需一次處理一個桶，因此適合延伸為外部排序方法。

選項分析

A. heap sort（堆積排序）錯誤

Heap sort 必須在主記憶體中維護一個 heap 結構，透過反覆取出最大值或最小值完成排序。其典型時間複雜度為：

但 heap sort 的資料存取通常是隨機存取。若資料位於磁碟中，頻繁的隨機讀寫會造成大量 I/O 成本，因此不適合作為外部排序的主要方法。

B. bubble sort（泡沫排序）錯誤

核心觀念

Queue（佇列）是一種「先進先出」的線性資料結構，英文為 First In, First Out，FIFO。

其基本操作為：

• Enqueue：從佇列尾端加入元素。
• Dequeue：從佇列前端移除元素。

因此，最早進入 Queue 的元素，會最早被移除。若依序加入 $A、B、C$，移除順序必為：

這就是 FIFO 規則。

解題方法

直接根據 Queue 的定義判斷其資料進出順序：

1. Queue 的元素從尾端進入。
2. 元素從前端離開。
3. 先加入的元素會先離開。

所以 Queue 遵循：

即 FIFO。

選項分析

A. FIFO

FIFO 是 First In, First Out 的縮寫，意思是「先進先出」，完全符合 Queue 的定義。

因此此選項正確。

B. FILO

FILO 是 First In, Last Out 的縮寫，意思是「先進後出」。

核心觀念

本題考查 Huffman 編碼。Huffman 編碼是一種以字元出現頻率為權重，建立「加權路徑長度最小」之最佳前綴碼的方法。

基本原則如下：

1. 統計每個字元的出現次數。
2. 每次選取頻率最小的兩個節點合併。
3. 將合併後的權重放回集合中，持續合併至只剩根節點。
4. 從根節點往左、右分別標記 $0$、$1$。
5. 每個字元的 Huffman code，就是從根到該字元的路徑標記。

空白不視為字母，因此不列入統計。

字母頻率統計

題目訊息為：

CAST CAST SAT AT A TASA

各字母出現次數如下：

總字母數為：

Huffman 樹建立過程

依照頻率由小到大排列：

第一次合併

選取最小的兩個節點 $C(2)$ 與 $S(4)$：

目前節點為：

第二次合併

選取最小的兩個節點 $T(5)$ 與合併節點 $6$：

目前節點為：

第三次合併

將 $A(7)$ 與 $11$ 合併為根節點：

因此 Huffman 樹結構如下。令左分支標記 $0$，右分支標記 $1$：

核心觀念

此函式的設計目的是在二元搜尋樹中搜尋 key：

• 找到相同資料時，令 n 指向該節點，回傳 true。
• 搜尋走到空指標時，令 n 指向最後檢查的父節點，回傳 false。這可用來指出搜尋終點。

二元搜尋樹的搜尋依比較結果往左或往右走，時間複雜度為 $O(h)$，其中 $h$ 是樹高；遞迴空間複雜度也是 $O(h)$。

解題方法與程式問題

程式在遞迴呼叫時沒有把遞迴結果傳回：

if (key < T->data)
    Mystery(T->lchild, key, T, n);
else
    Mystery(T->rchild, key, T, n);

因此，只要搜尋進入遞迴分支，該層函式最後就沒有回傳 bool。在 C++ 中，非 void 函式走到結尾卻未回傳值，行為未定義；即使遞迴層找到節點並回傳 true，上層仍會丟棄這個結果。

若要符合設計目的，遞迴呼叫需改成：

if (key < T->data)
    return Mystery(T->lchild, key, T, n);
else
    return Mystery(T->rchild, key, T, n);

對照 Fig. 2

核心觀念

本題考查各種常見函數與程式片段的漸近時間複雜度。判斷時使用以下原則：

• Big-O 描述輸入規模 $n$ 增大時，執行時間的上界成長率。
• 只保留成長最快的項，忽略常數係數與低階項。
• 與 $n$ 無關的固定運算量，時間複雜度為 $O(1)$。
• 常見成長率由慢至快為：

A. $3n^2+3n+1$

解題方法

比較各項隨 $n$ 增大的速度：

• $3n^2$ 為二次項；
• $3n$ 為一次項；
• $1$ 為常數項。

當 $n$ 很大時，$n^2$ 的成長速度遠高於 $n$ 與常數，因此只保留最高階項：

更精確地說：

選項分析

A 的最佳 Big-O 表示為：

B. $1+2+3+\dots+100$

解題方法

此和式最後一項固定為 $100$，與輸入大小 $n$ 無關。其實際數值為：

$5050$ 是固定常數，因此執行時間不會隨 $n$ 增加而增加：

選項分析

B 的最佳 Big-O 表示為：

常見陷阱

不能因為有許多加法符號，就判斷成 $O(n)$。題目中的上限是固定的 $100$，不是 $n$。若題目是

才會有：

C.

解題方法

將遞迴式逐層展開：

展開至 $T(1)$：

因為 $T(1)=1$，且幾何級數和為：

所以：

因此：

選項分析

C 的最佳 Big-O 表示為：

解題技巧

遞迴式中每次將前一層乘以 $2$，且只減少 $1$ 個問題規模：

這類型通常呈現指數成長。若係數改成 $T(n-1)+1$，才會是線性成長。

D. $100^4+2^9$

解題方法

$100^4$ 與 $2^9$ 都是固定數值：

因此整體為固定常數：

選項分析

D 的最佳 Big-O 表示為：

常見陷阱

核心觀念

本題考查二元樹的定義，以及三種樹走訪方式中的：

• In-order Traversal（中序走訪）：左子樹 → 根節點 → 右子樹
• Post-order Traversal（後序走訪）：左子樹 → 右子樹 → 根節點

二元樹的定義是：每個節點最多只能有兩個子節點，分別稱為左子節點與右子節點。

解題方法

判斷 Fig. 3 時，應逐一檢查每個節點：

1. 是否最多擁有兩個子節點，以判斷是否為二元樹。
2. 從根節點開始，依照圖中的左、右子樹遞迴走訪。
3. 中序走訪記錄順序為「左、根、右」。
4. 後序走訪記錄順序為「左、右、根」。

圖形資訊不足