資料結構 申論題歷屆試題與參考架構
高考三級，民國 102～115 年共 14 份試卷、64 題，其中 48 題附參考答題架構。考這一科的類科：資訊處理。本頁列出歷年全部題目，參考架構只列開頭的「破題」，完整的答題架構、關鍵字與作答提醒請到站內查看。
115 年（考試時間 120 分鐘） 原卷 PDF
- 1
某系統 A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重複鍵值，雜湊表有 11 個儲存格，索引從 0 開始，雜湊函數（hash function）為 h A (k ) k mod 11，其用平方探查法（quadratic probing）處理碰撞（collision）問題，探查序列為 hiA ( k ) ( h A (k ) i 2 ) mod 11 (i 0,1, 2,...) ，刪除資料時，被刪除資料的位置標記為特殊符號 DELETED。請回答下列問題：
（一）給定一個空的雜湊表，依序插入下列鍵值 22、1、13、24、35、46、7、18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值 46 時的完整探查過程。（10 分）
（二）承上題，依序刪除鍵值 24、13，畫出刪除後的雜湊表狀態。並說明為什麼刪除鍵值時需用 DELETED 標記，而不能將該鍵值所在的儲存格恢復成「從未存放過鍵值」的空狀態。（5 分）
（三）承上題，執行插入鍵值 12，請列出插入時的探查過程、操作停止的理由，並寫出 12 最後插入那一個儲存格。插入時，DELETED 標記視為可放入新鍵值的儲存格。請注意鍵值不能重覆。（5 分）
（四）相較於系統 A，考慮另一個採用平方探查法之系統，系統 B 的表格大小為 8，索引亦從 0 開始，雜湊函數 h B ( k ) 及探查序列 hiB ( k ) 分別定義為h B ( k ) k mod 8 、 hiB (k ) (h B (k ) i 2 i 2 ) mod 8 (i 0,1, 2,...) 。在非均勻雜湊（non-uniform hashing）的情況下，也就是許多鍵值可能被分配到相同或少數幾個初始雜湊位置時，那一個系統的雜湊表儲存格利用率可能較高？並說明理由。（5 分）
（25 分）
參考架構・破題
本題考開放定址法的平方探查：先逐步算出插入結果，再說明「懶惰刪除」（DELETED 標記）為何必要，最後比較兩種平方探查能涵蓋的儲存格數量。關鍵是每一步都寫出 h(k)、i 與算出的位置。
完整答題架構與關鍵字：到站內看全文
- 2
給定一個無向圖 G (V, E) ，每個頂點代表一個地點，每條邊 e (e E) 代表一條道路，邊的正整數權重 (e) 表示該道路的塞車程度，數值越大越壅塞。對於一條從起點 s 到終點 t ( s, t V) 的路徑 P，其最大塞車程度 C(P)定義為路徑上所有邊權重的最大值：C(P) max (e) eP本題透過修改 Dijkstra 最短路徑演算法中陣列 d 的定義與更新方式，求出從 s 到 t 可行路徑所能達到的「最大塞車程度的最小值」 。修改後的演算法流程與 Dijkstra 最短路徑演算法相同，差異僅在於 d [v](v V) 的定義與更新規則，其中，新的 d [v] 表示目前已知從 s 到 v 的路徑中，最大邊權重的最小值。初始時令 d [ s ] 0 ，其他頂點 v 的 d [v] (v s ) 。之後依照 Dijkstra演算法，每一輪選出尚未被選定且 d 值最小的頂點 u，並將原本的更新方式 d [v] min(d [v], d [u ] (u, v)) 改為 d [v] min(d [v], max(d [u ], (u, v))) ，其中 (u, v) 為邊 (u, v) (u, v V) 的權重。重複進行，直到終點 t 被選定為止。
（一）以下列無向圖為例，令起點 s 為 A，終點 t 為 F，依照修改後的演算法，逐步列出每次選定一個頂點後陣列 d 的變化過程。陣列中的頂點順序請依字母順序排列。（15 分）
（二）說明修改後演算法之正確性，是基於 d [v] 更新規則具有何種性質。 （5 分）
（三）假設圖以相鄰串列（adjacency list）表示。若要在尚未選定的頂點中找出 d 值最小者，可使用以下兩種方法：方法一：每次以線性方式掃描所有尚未選定的頂點找出最小 d 值。方法二：使用最小堆積（min-heap）維護目前 d 值最小的頂點。分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。 （5 分）
（25 分）
參考架構・破題
本題為瓶頸最短路徑（minimax path）：把 Dijkstra 的「加總」改成「取最大值」，求 A 到 F 所有路徑中最大邊權重的最小值。重點是逐輪列出 d 陣列，並指出 max 運算的單調性保證貪婪選擇正確。
完整答題架構與關鍵字：到站內看全文
- 3
給定一棵二元搜尋樹（binary search tree） ，且該樹同時也是一棵 AVL 樹。樹的節點在 C 語言中宣告如下：typedef struct Node { int key; // 節點的鍵值，所有節點的鍵值皆互不相同int size; // 以該節點為根的子樹節點總數 (包含自己) struct Node *left; // 指向左子節點struct Node *right; // 指向右子節點} Node;並定義以下函式：int size (Node *node)：若傳入的 node 為 NULL，則回傳 0；否則回傳 node -> size。int count_less_equal (Node *node, int val)：回傳以 node 為根的子樹中，所有鍵值小於等於 val 的節點總數。Node* select (Node *node, int r)：回傳以 node 為根的子樹中，第 r 小的節點指標，r 從 1 開始算。Node* greater_k_smallest (Node *root, int val, int k)：找出以 root 為根的整棵樹中，所有鍵值大於 val 的節點裡，第 k 小的節點，k 從 1 開始算。若第 k 小的節點不存在，則回傳 NULL。
（一）完成下列程式碼的空格。 （20 分）int count_less_equal(Node *node, int val) { if (node == NULL) return 0; if (node->key > val) return count_less_equal(node->left, val); else return size(node->left)+ (1) ; } Node* select(Node *node, int r) { int left_size = size(node->left); if (r == (2) ) return node; else if (r <= left_size) return select(node->left, r); else return (3) ; } Node* greater_k_smallest(Node *root, int val, int k){ int x = count_less_equal(root, val); int y = (4) ; if (y > size(root)) return NULL; return select(root, y); }
（二）下圖為一棵包含 5 個節點且滿足 AVL 平衡特性的二元搜尋樹，圖中顯示每個節點的鍵值。若將鍵值為 70 的新節點插入此樹，為保持 AVL樹的平衡，會觸發旋轉。請畫出旋轉後的樹狀結構圖。除新插入的節點 70 外，若原有節點的 size 欄位值在旋轉後發生改變，請在旋轉後的圖中，於該節點旁標示其新的 size 欄位值。（5 分）
（25 分）
參考架構・破題
本題考「順序統計樹」（order statistic tree）：利用每個節點記錄的子樹大小 size，在 O(log n) 內算排名與選出第 r 小；第二小題考 AVL 樹的雙旋轉與旋轉後 size 的維護。
完整答題架構與關鍵字：到站內看全文
- 4
考慮以下兩個互相呼叫（mutually recursive）的 C 語言函式：int foo(int n) { if (n <= 1) return 1; return foo(n - 1) + bar(n - 1) + 2; } int bar(int n) { if (n <= 1) return 1; return foo(n - 1) + bar(n - 1); }請回答下列問題： （每一小題請寫出推導過程，無推導過程不予計分。）
（一）當執行 foo(10)時，一共會呼叫 foo()函式幾次（包含最外層 foo(10)的這一次呼叫）？（10 分）
（二）執行 foo(10)的最終回傳結果為何？（10 分）
（三）以 Big-O 表示 foo(n)的時間複雜度（time complexity）。本題若同一個「函式與參數」組合被呼叫多次，每次都重新計算，不會儲存先前的計算結果供之後使用。（5 分）
（25 分）
參考架構・破題
本題考查相互遞迴（Mutual Recursion）函式的追蹤、遞迴關係式求解以及時間複雜度分析。作答核心在於將相互遞迴系統解耦，列出遞迴次數與回傳值的封閉形式（Closed-form expression），進而推導特定參數之精確值與漸近複雜度。
完整答題架構與關鍵字：到站內看全文
114 年（考試時間 120 分鐘） 原卷 PDF
- 1
一棵空的階數為 3 的 B-Tree（B-Tree of order 3） 。由左而右依序插入下列鍵值（key value）：10, 80, 2, 9, 45, 62。請問插入完畢後，根節點中的鍵值有那些？請依序由小到大列出，用逗號分隔，並請說明樹節點的變化。（10 分）有一棵階數為 5 的 B-Tree（B-Tree of order 5），其高度（height）為 3，請問這棵樹中最多可以儲存多少個鍵值？(10 分)
（20 分）
參考架構・破題
本題考查 B-Tree（B 樹）之核心定義、鍵值插入時的節點分裂（Split）向上提昇機制，以及基於階數（Order）與高度推導最大容量之理論計算。作答時需精確掌握階數與容量限制，詳述插入與分裂過程，並清楚界定高度之定義層級。
完整答題架構與關鍵字：到站內看全文
- 2
有一個三維整數陣列 A[3][6][8]，每個元素占用 4 個記憶體空間，每個記憶體空間均有位址。該陣列在儲存至記憶體時，會先被轉換為一維陣列的形式儲存。下列位址皆為十進位，已知 A[0][1][2]的記憶體位址為2040，A[1][4][5]的位址為 2340。請問陣列 A 在記憶體中的儲存方式為何？是以列為主（row-major）還是以行為主（column-major）？（10 分）請計算 A[1][5][3]在記憶體中的位址為何？（10 分）
（20 分）
參考架構・破題
本題考查多維陣列在實體記憶體定址中之對應轉換。作答關鍵在於建立「以列為主（Row-Major）」與「以行為主（Column-Major）」之三維位址公式，利用題目給定兩元素之記憶體位址差建立方程式，驗證並判定儲存順序，進而計算基底位址與目標元素的位址。
完整答題架構與關鍵字：到站內看全文
- 3
假設 G 為一個無方向連通加權圖（Undirected connected weighted graph），包含五個節點：A、B、C、D、E。各節點間相連情形如下，邊權（邊的權重）為正整數，代表邊的成本。A 與 B 相連，邊權為 16；A 與 C 相連，邊權為 18；A 與 D 相連，邊權為 14；B 與 C 相連，邊權為 15；C 與 D 相連，邊權為 13；D 與 E 相連，邊權為 12；C 與 E 相連，邊權為 17；請使用 Sollin’s 演算法，寫出最終形成的最小成本擴展樹的邊集合與總成本，請寫出每一步的演算法與該步驟形成的擴展樹。每一合併過程，列出選中的邊與合併的組成（component）。（20 分）
（20 分）
參考架構・破題
本題考查圖形理論中最小成本擴展樹（Minimum Spanning Tree, MST）的 Sollin’s 演算法（又稱 Borůvka’s 演算法）。該演算法的核心為各個連通分量（Component）平行各自挑選權重最小的外連邊以進行合併。作答需詳列初始分量狀態、每一輪各分量所選取的邊、合併過程以及最終成本計算。
完整答題架構與關鍵字：到站內看全文
- 4
根據下列的虛擬碼，若 n = 21 則傳回的答案為何？請說明。其中 floor()為數學上的地板函數（floor function）。（20 分）function splitSum(n: integer) returns integer if n <= 1 then return 1 a ← floor(n / 2) b ← floor(n / 3) return splitSum(a) + splitSum(b)
（20 分）
- 5
下列虛擬碼是利用某演算法對陣列 A 的元素進行處理，請說明該法是進行何種處理並請寫出其名稱和在最壞情況下時間複雜度為何？（10 分）若陣列 A = [29, 10, 14, 37, 13]，請寫出該虛擬碼的處理過程：請列出陣列在每一輪（每次外層迴圈執行完後）的內容變化情形。請特別標示出最終結果為何？（10 分）doingSomething(A) begin n ←陣列 A 的元素個數for i ← 0 to n − 2 do theIndex ← i for j ← i + 1 to n − 1 do if A[j] < A[theIndex] then theIndex ← j end for if theIndex <> i then temp = A[i] A[i] = A[theIndex] A[theIndex] = temp end if end for end
（20 分）
參考架構・破題
本題考查基礎內部排序演算法之虛擬碼判讀、時間複雜度推導及執行過程追蹤。透過虛擬碼中「外層固定基準位置、內層搜尋未排序區間之最小值索引，最後進行一次交換」之特徵，判定該演算法為選擇排序法（Selection Sort），並按輪次展示陣列變化。
完整答題架構與關鍵字：到站內看全文
113 年（考試時間 120 分鐘） 原卷 PDF
- 1
（一）若有 200 人，其中一個人開始打電話給兩個人。隨後，每個接到電話的人都會打電話給另外兩個尚沒有接到電話的人。請問總共會撥打多少通電話？有多少人不會打電話？（無推導過程不給分） （10 分）
（二）若一個二元樹其前序追蹤順序（Preorder Traversal）及後序追蹤順序（Postorder Traversal）分別如下，請問此樹是否唯一？並請列出此二元樹的中序追蹤順序（Inorder Traversal） 。 （無推導過程不給分） （15 分）前序追蹤順序：T, S, R, F, D, I, H, E, Z, G, M, L, J, N, Q後序追蹤順序：F, I, H, D, R, Z, G, E, S, J, N, L, Q, M, T
（25 分）
參考架構・破題
本題考查樹狀結構的基本圖論性質（邊數與節點關係）以及二元樹的前序與後序追蹤重建唯一性定理。第一題將通知流程建構為樹狀模型推導通話總數與葉節點人數；第二題則依全二元樹無單親節點之特徵確立唯一性，並導出中序追蹤序列。
完整答題架構與關鍵字：到站內看全文
- 2
（一）快速排序法（Quick Sort）最壞的情況下所需的時間複雜度（Time Complexity）為 O(n2)，請說明是在何種情況下造成？（10 分）
（二）請列出其最壞的時間複雜度為 O(n2)的推導過程。（15 分）
（25 分）
參考架構・破題
本題考查快速排序法（Quick Sort）之分割機制（Partitioning）與極端情況下的時間複雜度漸近推導。解題核心在於說明樞紐元素（Pivot）的不當選取如何導致問題規模無法有效對半折半，並透過遞迴代換法或級數展開嚴格導出二次方時間複雜度。
完整答題架構與關鍵字：到站內看全文
- 3
請使用虛擬碼（Pseudo Code）或任何程式語言，完成下列問題：
（一）撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分）
（二）推導二元搜尋的時間複雜度（Time Complexity）。（5 分）
（25 分）
參考架構・破題
本題考查經典搜尋演算法「二元搜尋法」（Binary Search）之程式實作與效能理論分析。作答關鍵在於正確寫出遞迴與迴圈迭代（非遞迴）兩種虛擬碼，確保邊界條件精確無誤，並以遞迴關係式嚴謹推導其時間複雜度。
完整答題架構與關鍵字：到站內看全文
- 4
堆疊（Stack）與佇列（Queue）是常見的資料結構，請回答下列問題：
（一）利用雙向佇列（Deque）循序輸入 1, 2, 3, 4, 5, 6, 7，請問能否得到5174236 的輸出排列？並說明其過程或理由。（10 分）
（二）若有 1, 2, 3, 4 四個數字要依序 Push 進堆疊，再於任意時間點 Pop 出堆疊，請列出可能的輸出組合。（15 分）
（25 分）
參考架構・破題
本題考查線性資料結構雙向佇列（Deque）之進出受限特性與堆疊（Stack）之排列生成問題。作答核心在於透過狀態推演證明目標 Deque 序列是否具備可行性，並運用卡特蘭數（Catalan Number）系統化列舉堆疊所有合法排列。
完整答題架構與關鍵字：到站內看全文
112 年（考試時間 120 分鐘） 原卷 PDF
- 1
某一公司有下圖所示的8個優先順序分別為高或低的待執行工作，且將依順序自A至H每間隔一天的時間放入對應的高優先執行佇列（Queue）或低優先執行佇列（Queue），例如A（低）表示A工作將於第一天放入低優先執行佇列，而C（高）表示C工作將於第三天放入高優先執行佇列。此外，執行每個工作所需完成的時間均於工作名稱下顯示，例如執行A工作需要2天時間完成，而執行B工作需要1天時間完成。最後，各個工作的執行規則為，當高優先執行佇列內有工作待完成時，須優先執行該佇列內的工作（由第一個開始執行），直到高優先執行佇列內沒有任何待完成工作時，方可執行低優先執行佇列內的工作（由第一個開始執行） 。自A至H每間隔一天的時間放入對應的高優先佇列或低優先佇列H（低） G（高） F（高） E（低） D（高） C（高） B（低） A（低）1 2 1 1 2 2 1 2
（一）試計算執行此8個工作需要多少天方可完成。（10分）
（二）試計算此8個工作自放入佇列至開始執行的平均等待時間。（15分）
（25 分）
參考架構・破題
本題是雙佇列的優先權排程模擬（不可搶先）：依到達時間把工作放進高、低優先佇列，每次空閒時先取高優先佇列的第一個。關鍵是畫出時間軸（甘特圖），由此算完成天數與等待時間。
完整答題架構與關鍵字：到站內看全文
- 2
某一物流公司有下圖所示的8個地點要運送，每條方向性連線及其數字代表兩個地點的運送順序及運送成本。
（一）試使用拓樸排序法，找出此8個地點的運送順序以及總共運送成本。（15分）
（二）若將上圖的地點2與地點4之間以及地點6與地點7之間的連線方向顛倒，則運用拓樸排序法後，此8個地點的運送順序以及總共運送成本為何？（10分）
（25 分）
參考架構・破題
本題考有向無環圖（DAG）的拓樸排序：用入分支度（in-degree）法逐步取出入度為 0 的頂點；第二小題改變邊的方向後產生環路，拓樸排序無法完成，這是本題陷阱。
完整答題架構與關鍵字：到站內看全文
- 3
在電腦網路中，透過IP位址以查詢對應的裝置是常見的動作。今某電腦網路有以下表格所示的IP位址以及對應裝置（假設每個IP位址有8個位元），當輸入某一IP位址以查詢對應的裝置時，最壞情況為此表格中的每個IP位址的每個位元皆需要搜尋一次，以確認此輸入的IP位址是否有對應的裝置。由於這樣的IP位址儲存方式，將造成查詢時的高複雜度（例如，若表內有m個IP時，查詢的複雜度為m*8），因此運用適當的資料結構以減低查詢複雜度，已成為電腦網路的重要課題。IP位元0 IP位元1 IP位元2 IP位元3 IP位元4 IP位元5 IP位元6 IP位元7 裝置0 0 1 1 1 1 0 0 A 0 0 1 1 0 0 1 1 B 1 1 0 0 0 0 1 1 C 1 1 0 0 1 1 0 0 D 1 1 0 1 1 1 0 0 E … … … … … … … … …試建立並驗證一個樹狀資料結構，不僅可以儲存以上表格方式的IP位址以及對應裝置資訊，並可使得查詢IP位址所對應的裝置的最壞情況複雜度維持在常數8（也就是IP位址位元數）。（25分）
（25 分）
參考架構・破題
本題要設計二元字典樹（binary trie）：以 IP 的每個位元當作分支，從根往下走 8 層即可到達對應裝置，查詢成本只與位元數有關、與表格筆數 m 無關。答題要「建立」（畫樹與定義節點）並「驗證」（查詢範例與複雜度證明）。
完整答題架構與關鍵字：到站內看全文
- 4
某一系統有下表所示的使用者帳號與密碼資料，今為了保密需要欲將使用者密碼透過雜湊函數加以加密，並將雜湊後的密碼連同使用者帳號儲存於一個2-3樹（2-3 tree）（依使用者帳號英文字母順序儲存），而雜湊函數h(x) =密碼之英文及數字加總，其中英文a-z相當於1-26。使用者帳號 使用者密碼AA 234abc BB 123bcd CD aa012 AC 555be BD 45fdd CA 712ccc
（一）試計算出雜湊後的密碼資料。（10分）
（二）試建立此2-3樹，以儲存系統的使用者帳號與（雜湊後）密碼資料。（15分）
（25 分）
111 年（考試時間 120 分鐘） 原卷 PDF
- 1
以下是一中序運算式（Infix expression）轉換（Convert）成後序運算式（Postfix expression）的演算法operstk = the empty stack; while(not end of input){ symb = next input character; if(symb is an operand) add symb to the postfix string; else{ while(!empty(operstk) && precedence(stacktop(operstk),symb)){ topsymb = pop(operstk); add topsymb to the postfix string; } /*end while*/ if (empty(operstk) || symb != ‘)’) push(operstk, symb); else topsymb = pop(operstk); } /*end else*/ } /*end while*/ｗhile(!empty(operstk)){ topsymb = pop(operstk); add topsymb to the postfix string; } /*end while*/其中資料結構：“operstk”：用來儲存運算子的堆疊（Stack） ；“stacktop(operstk)”：表示 top 指標所指堆疊 operstk 的運算子；程序（Procedures）或函數（Functions） ：“empty(operstk)”：檢查堆疊 operstk 是否為空的布林函數；“pop(operstk)”：從堆疊 operstk 中取出一運算子；“push(operstk, symb)”：將運算子 symb 存入堆疊 operstk；“precedence(op1,op2)”：布林函數，定義在一沒有左右括弧的中序運算式中，op1 運算子出現在 op2 運算子的左邊時，當 op1 運算子優先順序不低於 op2 運算子，則設定成 TRUE，否則為 FALSE。例如，我們給定precedence(‘*’, ‘+’)=TRUE ， precedence(‘+’, ‘+’)=TRUE ，precedence(‘+’, ‘*’)=FALSE，為了處理運算式左右括弧，設定下列的 precedence: precedence(‘(’, op) = FALSE /*op 為任一運算子*/ precedence(op, ‘(’) = FALSE /*op 為除’)’外的任一運算子*/ precedence(op, ‘)’) = TRUE /*op 為除’(’外的任一運算子*/ precedence(‘)’, op) = undefined /*op 為任一運算子*/以中序運算式(2+3)*4 為例，執行上述演算法，依處理每一個運算子或運算元時，輸出 postfix string 及 operstk 內容為何（“eos”表示 end of string）？（25 分）symbol postfix string operstk ( + ) * eos
（25 分）
- 2
利用鏈結串列（Linked list）實做佇列（Queues），給予如下鏈結串列節點及佇列定義，front 指標指在串列第一個節點，rear 指標指在串列最後一個節點，請使用 C 語言完成 insert(pq, x)程序，將整數值 x 加入（Insert）到佇列，程式需檢查佇列加入前是否為空的鏈結串列，可使用函數 getnode() 配置（Allocate）一新節點。（25 分）struct node{ int info; struct node *next; }; typedef struct node *NODEPTR; struct queue{ NODEPTR front, rear; }; struct queue q; NODEPTR getnode() { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct node)); return(p); } insert(pq, x) struct queue *pq; int x; { NODEPTR p; }
（25 分）
參考架構・破題
本題考查使用單向鏈結串列（Singly Linked List）實作佇列（Queue）之佇列置入（Enqueue）操作。核心在於動態記憶體配置、新節點指標初始化，以及精確區分「佇列原本為空」與「佇列已有節點」兩種指標鏈結更新情況。
完整答題架構與關鍵字：到站內看全文
- 3
一個二元搜尋樹（Binary search tree）的前序追蹤（Preorder traversal）結果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用C 語言寫一遞迴程式 sortTree（NODEPTR tree） ，輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25 分）struct node{ int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void sortTree(NODEPTR tree){ }
（25 分）
參考架構・破題
本題考查二元搜尋樹（Binary Search Tree, BST）的結構特性重構與中序追蹤程式撰寫。BST 的關鍵特性為「左子樹所有鍵值小於根節點，右子樹所有鍵值大於根節點」，利用此特性可唯一逆推樹狀結構，而依序（由小至大）輸出節點資料即為中序追蹤（Inorder Traversal）的具體實踐。
完整答題架構與關鍵字：到站內看全文
- 4
用 G = (V, E)表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點（Vertices）形成邊及對應權重（Weights）所組成的集合。今有一圖形G = (V, E)，V = {0, 1, 2, 3, 4, 5}，圖形的邊與權重值以如下的定義儲存對應連接矩陣(Adjacency matrix)表示中的值#define MAX_EDGES 100 typedef struct { int col; int row; int weight; } edge; edge a[MAX_EDGES];已知陣列 a 儲存對應連接矩陣相連接邊的內容如下：a = {(3, 0, 2), (4, 0, 1), (5, 0, 20), (2, 1, 7), (5, 1, 24), (3, 2, 15), (4, 2, 10), (5, 2, 25), (4, 3, 3)}。請畫出陣列 a 所儲存的圖形，然後，利用 Prim 演算法從節點 0 開始依加入其它節點的順序，畫出此圖之最小擴張樹（Minimum spanning tree），並計算其最低權重或成本值。（25 分）
（25 分）
110 年（考試時間 120 分鐘） 原卷 PDF
- 1
A 為（8×4）矩陣、B 為（4×10）矩陣、C 為（10×3）矩陣、D 為（3×20）矩陣、E 為（20×4）矩陣，（一）請列出此 5 個矩陣相乘 ABCDE 所有可能的乘法順序（請用括號表示乘法順序） 。（5 分）（二）請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 ABCDE 的最佳乘法順序（請用括號表示乘法順序） ，使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）（三）請列出此五個矩陣相乘所需要花費的最少乘法數量。 （5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）
（25 分）
參考架構・破題
本題為矩陣鏈乘積（matrix-chain multiplication）問題：先列出 5 個矩陣的全部括號方式（Catalan 數 14 種），再用動態規劃表 m[i][j] 求最少純量乘法數與最佳括號。題目明言未列計算過程不計分，表格與遞迴式必寫。
完整答題架構與關鍵字：到站內看全文
- 2
假設收銀機內銅板的集合 S={$50, $20, $20, $15, $10, $2, $1, $1, $1}，而預計找錢給顧客的金額 W=$75。（一）請設計一個 Greedy（貪婪）的演算法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量最少，並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。 （15 分）
（二）此 Greedy 演算法適合使用何種資料結構來完成。（5 分）（三）此 Greedy演算法的解法是否能保證為最佳解？請舉例說明。（5 分）
（25 分）
- 3
二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法技巧，對一個已排序的（sorted）且長度為 n 的陣列 A[0:n1]，以二元化方 式 進 行 資 料 值 x 的 搜 尋 ， 其 最 差 時 間 複 雜 度 （ worst case time complexity）可降到(log n)。（一）請使用 C++或 Python 語言，修改此二元搜尋法，使其能對未排序的（unsorted）且長度為 n 的陣列 A[0:n1]，進行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列，並在可能包含資料值 x 的子陣列繼續進行 divide-and-conquer 技巧的搜尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分） （注意：請寫一個 searching 類別，內含一個 search 功能）（二）請分析修改後的三元化搜尋法其最差時間複雜度（worst case time complexity）以 order 的方式表示。（8 分） （注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）
（25 分）
參考架構・破題
本題要把二元搜尋改寫成「三分」的分治搜尋，但陣列未排序且不得排序，因此無法藉比較排除任何子陣列，三段都可能含 x，必須三段都遞迴搜尋。關鍵是看出這個差異並導出 T(n)=3T(n/3)+O(1)=Θ(n)。
完整答題架構與關鍵字：到站內看全文
- 4
（一）請使用 C 語言寫一副程式 void FindMeanAverage(int A [], int n, int * mean, int * average)，對一個未排序的（unsorted）且長度為 n 的陣列A[0:n1]，尋找陣列中的中位數與平均數，並分別存入 mean 及 average運算複雜度。（17 分）（二）請舉例說明此副程式最差情況（worst case）所花費的運算複雜度。 （8 分）（注意：請加註解說明程式碼作法。）
（25 分）
參考架構・破題
本題要對未排序陣列求中位數（題目變數名稱為 mean，實指中位數）與平均數。平均數一次掃描 O(n) 即可；中位數是選擇問題（selection），可排序後取中間或用 quickselect，重點在說明所用方法的最差情況並舉出具體例子。
完整答題架構與關鍵字：到站內看全文
109 年（考試時間 120 分鐘） 原卷 PDF
- 1
考慮數字1到n，若將其順序重新排置，每個排列順序都稱作一個排列或置換（Permutation），例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1到n的排列視為一個順序的映射P，則前述例子可表示為P(5) = 1、P(1) = 2、P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在一個數字1到n的排列P中，若一對數字 i 和 j ，1 i < j n，P( j) < P(i)，也就是在排列P中較大的數字 j 出現在較小的數字 i 左邊（前面），我們稱此對數字為反向（Inversion） ，而排列P的反向數（Inversion number）則定義為排列P中反向的總數量。請回答下列問題：
（一）數字1到n的何種排列會有最大的反向數？最大反向數是多少？（5分）
（二）若給定一個數字1到n的排列P，請提出一個線性遞迴（Linear Recursive）的方式來算出排列P的反向數，並提供虛擬碼（Pseudo-code）與時間複雜度分析。 （10分）
（15 分）
- 2
優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。
（一）請說明如何利用優先佇列對n個鍵值進行排序。（6分）
（二）我們使用一個未排序的陣列（Unsorted Array）來管理鍵值以實現一個優先佇列，請回答下列問題：（10分）
⑴若有n個鍵值，請說明兩個主要操作（加入（Insert）與擷取最小者（Delete_Min））的時間複雜度。
⑵請判斷下面的敘述是否為真，並請說明原因：若以此優先佇列進行排序（Sorting） ，其所對應的排序原理為插入排序（Insertion Sort）。
（三）二元堆積（Binary Heap）是一個優先佇列的資料結構，因為我們考慮鍵值小的物件有高的優先權，所以又可稱為最小堆積（Minimum Heap） 。（14分）
⑴在結構上最小堆積為一個完全二元樹（Complete Binary Tree），若使用一個陣列來實作最小堆積，陣列中物件的鍵值放置如下，請描述此陣列對應的完全二元樹（以樹狀結構表示） 。Index 1 2 3 4 5 6 7 8 9 10 Key 35 18 42 24 7 14 25 12 38 21
⑵請說明二元堆積中何謂堆積特性（Heap Property）？
⑶前揭⑴中的完全二元樹並未有堆積特性，請將其進行堆積化（Heapify），並以陣列表示出堆積化後的最小堆積所對應之完全二元樹。
（30 分）
參考架構・破題
本題從抽象資料型別「優先佇列」切入，依序考它的排序用途、未排序陣列實作的複雜度與對應排序法，最後考二元堆積的陣列表示與 bottom-up 堆積化，計算題要把每一步寫出來。
完整答題架構與關鍵字：到站內看全文
- 3
請回答下列關於AVL樹（AVL Tree）的問題：
（一）我們欲將所管理的鍵值（Key）依序列出，請問是否可以利用一個AVL樹對鍵值來進行排序（Sorting）？若不行，請說明原因；如果可以，請描述方法及時間複雜度。（5分）
（二）請提供一個線性時間的演算法來判斷一個二元搜尋樹是否為AVL樹。（10分）
（三）在AVL樹上進行一個加入（Insert）操作後，是否最多只需要一次的重構（Restructuring）即可恢復其平衡的特性？請說明原因。（10分）
（25 分）
- 4
若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)，請考慮下面的問題：圖一、無向圖G = (V, E)
（一）對於無向圖G = (V, E)：（12分）
⑴請給出對應的相鄰矩陣M。
⑵以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請由節點a開始，描述此深度優先搜尋所產生的深度優先樹（DF-tree） 。
（二）請說明在用相鄰矩陣（Adjacency Matrix）表示的無向圖上，進行深度優先搜尋的時間複雜度，其中節點與邊的數量分別為|V | = n與|E| = m。 （8分）
（三）若將圖一無向圖G = (V, E)中的邊給予方向成為如圖二中的有向圖（Directed Graph）G’：（10分）圖二、有向圖G’
⑴有向圖G’沒有迴圈（Cycle），是一個無迴圈有向圖（Directed Acyclic，所以存在節點的拓樸排序（Topological Sort）Graph, DAG） ，請對G’給出一個拓樸排序（Topological Sort）。
⑵請給一個方法來判斷一個有向圖是否沒有迴圈。
（30 分）
本題含圖表或公式，請對照原卷 PDF。
108 年（考試時間 120 分鐘） 原卷 PDF
- 1
給予如下二元樹節點的宣告，分別寫出 C 的遞迴程式計算二元樹節點個數及計算二元樹葉節點（leaves）個數（Count the number of nodes in a binary tree and count the number of leaf nodes in a binary tree, respectively）。（25 分）struct node{ int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void countTree(NODEPTR tree){ } void countLeaves(NODEPTR tree){ }
（25 分）
- 2
給予如下二元樹節點的宣告，寫一 C 的遞迴程式 swapTree（NODEPTR tree）將每一節點的左、右節點互換（Swap the left and right children of every node of a binary tree）。（25 分）struct node{ int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void swapTree(NODEPTR tree){ }
（25 分）
- 3
給予如下程式，假設 x[] = [30, 75, 53, 47, 21, 94, 88, 39]，lb = 0，ub = 7，請問執行完下列程式後，x[]的內容為何？（25 分）void divide&conquer(int x[], int lb, int ub, int *pj) { int a, down, temp, up; a = x[lb]; up = ub; down = lb; while(down < up){ while(x[down] <= a && down < ub) down++; while(x[up] > a) up--; if(down < up){ temp = x[down]; x[down] = x[up]; x[up] = temp; } } x[lb] = x[up]; x[up] = a; *pj = up; }
（25 分）
參考架構・破題
題目程式是快速排序（Quick Sort）的分割（partition）程序：以 x[lb] 為 pivot，把不大於 pivot 的元素放左邊、大於的放右邊，最後把 pivot 放到正確位置。本題要逐步追蹤指標 down、up 的變化。
完整答題架構與關鍵字：到站內看全文
- 4
用 G = (V, E)表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點（Vertices）形成一個邊及對應權重（Weights）所組成的集合，例如：(0, 1, 28)表示節點 0 至節點 1 有一個邊，而且權重為 28。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5, 6}，E = {(0, 1, 27), (1, 2, 15), (2, 3, 11), (0, 5, 9), (1, 6, 13), (4, 5, 24), (4, 6, 23), (3, 4, 21), (3, 6, 17)}。請利用 Kruskal 演算法計算最小擴張樹（Minimum spanning tree）之最低權重或成本值。 （25 分）
（25 分）
107 年（考試時間 120 分鐘） 原卷 PDF
- 1
（一）請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的差異（13 分）。
（二）若有 n 個鍵值，以下列甲和乙兩種資料結構策略儲存：策略甲：由小到大依序儲存在一陣列中策略乙：以 AVL tree 架構儲存請以 Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或兩者效能相近：尋找特定鍵值 k；尋找排序為 j 的鍵值；刪除特定鍵值 k；刪除排序為 j 的鍵值；插入新鍵值；依序輸出所有鍵值。 （12 分）
（25 分）
- 2
一非空的二元樹（binary tree） ，如果有 n0 個葉節點（leaf node）且 n2 個節點之分支度（degree）為 2，請證明 n0 = n2+1。（25 分）
（25 分）
- 3
一無向圖 G 之節點集合為 G(V)={0,1,2,3,4,5,6,7,8,9}，邊集合為 G(E)={(0,1), (1,2), (1,3), (2,4), (3,4), (3,5), (5,6), (5,7), (6,7), (7,8), (7,9)}；請列出 G 之接合點（articulation point）和畫出 G 的所有雙連通元件（biconnected component），雙連通元件須以節點和邊構成之子圖方式表示。 （20 分）
（20 分）
參考架構・破題
接合點（articulation point）是移除後會讓連通圖分裂的節點；雙連通元件（biconnected component）是沒有接合點的極大連通子圖。可用 DFS 搭配 dfn 與 low 值求解，再以邊集合列出各元件。
完整答題架構與關鍵字：到站內看全文
- 4
對稱式最小-最大堆積（Symmetric Min-Max Heap，簡稱 SMMH）是一種優先佇列（priority queue），請回答下列與 SMMH 相關的問題。
（一）請說明 SMMH 特性並說明以 SMMH 建構之優先佇列與以一般的堆積（heap）建構 之 優 先 佇 列 功 能 有 何 不 同 ？ 並 從 一 個 空 的 SMMH 開 始 ， 依 序 插 入30,20,50,5,4,9,70,2,80。請畫出最後 SMMH 的樹狀結構圖。（10 分）
（二）請畫出第（一）小題建構的 SMMH，刪除數字 2 後 SMMH 的樹狀結構圖。 （5 分）
（三）請以一維陣列設計一資料結構儲存 SMMH，該資料結構可以使節點透過其對應之陣列索引值 x 構成的數學式計算出其祖父節點 g、父節點 p、左子節點 l、右子節點 r 與兄弟節點 s 等在陣列中的索引值。假設一維陣列之起始索引值為 0，請列出由 x 構成之計算 g、p、l、r、s 的數學式。並請畫出以此一維陣列儲存第（一）小題建構完成的 SMMH 的結果。（15 分）
（30 分）
參考架構・破題
SMMH 是根為空節點的完全二元樹，能同時以 O(log n) 取出最小值與最大值（雙端優先佇列）。本題要寫出性質、逐步插入與刪除，再設計以陣列索引計算親屬關係的公式。
完整答題架構與關鍵字：到站內看全文
106 年（考試時間 120 分鐘） 原卷 PDF
- 1
給定二元樹（binary tree）如右圖，樹高為 4 且共有 7 個節點。 T T
（一）請寫出該樹之後序遍歷（postorder traversal）結果。（5 分） S S U U
（二）若以陣列 A[1..15]實作該二元樹，請列舉陣列 A[1..15]的內容。O G G（5 分）
（三）若要將數值 x 設為或取代 A[i]（任一 1 ≤ i ≤ 7）所代表的節點 P P X X之右子節點（right child node）的內容，令 x 會被放入陣列中A[j]的位置。請以 j、i 表示，寫出 j 位置之公式。（5 分）
（四）若要在原始的二元樹中加入一些節點使其成為完整二元樹（complete binary tree）及完滿二元樹（full binary tree），請問最少各需加入幾個新節點？（5 分）
（20 分）
- 2
遊樂園設計公司正在設計新的遊樂園，遊樂園將有 9 個遊樂設施，設施名稱暫定為 A, B, C, D, E, F, G, H, I。遊樂設施之間將透過不盡相同距離但極具特色的商店街相連。給定遊樂園的初步規劃如表一，表內數字為兩遊樂設施之間商店街道之預計長度（每條街道長度皆不同）。若無數字則代表兩遊樂設施之間沒有商店街道之規劃。設計公司將依不同考量來決定實際建置那些商店街道。表一A B C D E F G H I A 18 5 13 1 B 18 9 10 16 8 C 9 11 7 12 3 D 5 17 19 E 13 10 11 17 2 F 1 16 14 15 G 7 19 2 4 H 12 14 4 6 I 8 3 15 6
（一）若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分）
（二）請計算符合上述（一）小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分）
（三）但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍 9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle），旅行商人問題（Traveling Sales Man Problem），最短路徑（例如 Dijkstra 演算法），任兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分）全一張（背面）
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 3
表二列出五種常見的排序演算法，請填滿該表以顯示各排序法在最佳情況、一般情況、最壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資料已事先填入作為範例。（(a),(b),(c),(d)各 5 分，共 20 分）表二最佳情況 一般情況 最壞情況 是或不是（best case） （average case） （worst case） 所需額外空間 穩定排序法（stable sort）快速排序法 O(n log n) O(n log n) O(n2) O(n) 不是（quicksort）(a)泡沫排序法bubble sort (b)插入排序法insertion sort (c)合併排序法merge sort (d)堆積排序法heap sort
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定 n 個矩陣，A1, A2, …, An，且任一矩陣 Ai 大小為 pi −1 × pi , p0 , ..., pn 皆為正整數。A1 × A2 × … × An 實際計算過程可以是(…((A1 × A2) × A3) × … × An)、(A1 × (A2 × (…× (An-2 × (An-1 × An))…)))、或其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次數的計算順序。方法如下：令 m[i, j ] 為計算 Ai × Ai+1 × … × Aj 時所需最少乘法運算次數，m[i, j ] 可以下列遞迴公式表示之：⎧imin {m[i, k ] + m[k + 1, j ] + pi −1 pk p j }, if i < j m[i, j ] = ⎨ ≤ k < j ⎩ 0, if i ≥ j
（一）請說明 A1 × A2 × … × An 相乘過後的矩陣大小為何？（3 分）
（二）透過上述方法所找到的最少乘法運算次數，應為二維陣列 m[i, j ] 中的那個元素，亦即 i, j應分別為何？（3 分）
（三）若 n = 4 且 p0 , p1 , p2 , p3 , p4 分別為 3, 4, 5, 4, 2，請計算並填寫出二維陣列 m[i, j ]。（11 分）
（四）承上小題（三），請說明該四矩陣相乘，A1 × A2 × A3 × A4，最少共需有幾次乘法運算。（3 分）
（20 分）
參考架構・破題
矩陣鏈乘積（Matrix-Chain Multiplication）是動態規劃的經典題：由短鏈往長鏈填 m[i, j] 表，取各分割點 k 的最小值。本題要正確計算各格並回推最佳括號方式。
完整答題架構與關鍵字：到站內看全文
- 5
請依序將 17, 23, 36, 13, 38, 11, 52, 44, 25, 35, 2, 18, 21 儲存至下列 13 桶（buckets）× 1 槽（slots）的雜湊表（hashing table）。請以各小題所設定的雜湊函式（hashing function）將資料依序存入並顯示最後的雜湊表。雜 0 1 2 3 4 5 6 7 8 9 10 11 12湊表
（一）雜湊函式 F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linear probing）來放入資料。請顯示最後的雜湊表。（5 分）
（二）雜湊函式 F(x) = x mod 13，碰撞時，採取「二次方探測法」 （open addressing with quadratic probing）來放入資料。請顯示最後的雜湊表。（5 分）
（三）雜湊函式 F1(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）來放入資料，第二雜湊函式為 F2(x) = 7－(x mod 7)。請顯示最後的雜湊表。（5 分）
（四）若雜湊表夠大（例如 slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最差？（5 分）
（20 分）
本題含圖表或公式，請對照原卷 PDF。
105 年（考試時間 120 分鐘） 原卷 PDF
- 1
假設一個無向圖（undirected graph）的邊（edges）如下：S, T S, Z T, Y T, Z V, Y V, Z Y, Z
（一）使用堆疊（stack），從 S 開始，進行深度優先走訪（depth-first traversal），請寫出走訪結果。（10 分）
（二）使用佇列（queue），從 S 開始，進行廣度優先走訪（breadth-first traversal），請寫出走訪結果。 （10 分）
（20 分）
參考架構・破題
本題考圖形的兩種走訪：DFS 以堆疊實作（後進先出），BFS 以佇列實作（先進先出）。結果會因相鄰節點的處理順序而不同，作答時先說明假設（例如相鄰節點依字母順序）再逐步追蹤。
完整答題架構與關鍵字：到站內看全文
- 2
（一）請將下列值 2, 1, 4, 5, 9, 3, 6, 7 依序插入原來為空的紅黑樹（red-black tree），請寫出結果。作答時，請標示節點如下：例如節點 2B 表示其值為 2 的黑（Black）節點，又如節點 5R 表示其值為 5 的紅（Red）節點。（10 分）
（二）請畫出與上面（一）小題相對應的 2-3-4 樹（2-3-4 tree）。 （10 分）
（20 分）
參考架構・破題
本題考紅黑樹插入時的重新著色（recoloring）與旋轉（rotation），以及紅黑樹與 2-3-4 樹的一一對應關係。作答要逐步畫出每次插入後的樹，最後再把黑節點與其紅色子節點合併成 2-3-4 樹的節點。
完整答題架構與關鍵字：到站內看全文
- 3
請對下面的樹，分別做前序（preOrder） 、中序（inOrder）、後序（postOrder）及廣度優先（breadth-first）四種走訪（traversals），請分別寫出結果。 （20 分）＋－ ／Ｘ Ｙ Ｚ ＊Ａ Ｂ
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
（一）依序插入 2, 1, 4, 5, 9, 3, 6, 7 於原來為空的堆（min heap），請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）
（二）從上面（一）小題的結果刪除兩個元素，請畫圖顯示此堆（min heap）的樹狀結構，並請寫出此堆（min heap）的陣列內容。（10 分）
（20 分）
參考架構・破題
本題考最小堆積（min heap）的插入（向上調整 sift-up）與刪除最小值（向下調整 sift-down），以及完全二元樹的陣列表示法。每一步都要寫出比較與交換的過程。
完整答題架構與關鍵字：到站內看全文
- 5
對下列程式片段，請用 Big-O 符號（Big-O notation），分別估計最長執行時間（worst time）。注意：S 中沒有與 n 相關的迴圈（n-dependent loops）。（每小題 5 分，共 20 分）
（一） for (int i = 0; i * i < n; i++) S
（二） for (int i = 1; i < n+1; i*=2) S
（三） for (int i = 1; i < n+1; i*=2) for (int j = 0; j < n; j++) S
（四） k=1; for (int i=0; i<n; i++) {k*=3; for (int j=0; j<k; j++) S}
（20 分）
104 年（考試時間 120 分鐘） 原卷 PDF
- 1
有位程式設計師在撰寫程式時遇到了一個難解的問題，後來發現有兩個演算法可以解這個難題：演算法 A 的時間複雜度為 O(n 2 log(n!)) ，演算法 B 的時間複雜度為O(n 2 ((log n)!)) 。假設輸入資料的個數 n 通常都很大，他應該選擇那個演算法比較好，原因何在？（20 分）
（20 分）
參考架構・破題
本題核心是比較 log(n!) 與 (log n)! 的成長速度：前者依 Stirling 公式為 Θ(n log n)，屬多項式等級；後者成長超過任何多項式。因此演算法 A 較佳。
完整答題架構與關鍵字：到站內看全文
- 2
樹（tree）是一個很常用的資料結構。一個樹是指一個沒有迴圈（cycle）的聯通圖（connected graph）。（每小題 10 分，共 20 分）
（一）證明：每個具有 n 個節點（node）的樹， n > 1，至少有 2 個分支度（degree）為1 的節點。（分支度就是指有多少邊以此節點為端點。）
（二）用前項結果證明：每個具有 n 個節點的樹，n > 1，恰好有n − 1 個邊（edge）。
（20 分）
- 3
給定一個權重圖（weighted graph）， G = (V , E , w) ，其中每個邊（edge） e 的權重w(e) 都是正整數，為了簡單，假設 V = {1,2,..., n} 。任意點 v 與起始點 s 的距離可以用一個矩陣 d [1..n] 來表示。（每小題 10 分，共 20 分）
（一）設計一個只需 O(n) 空間的方法來記錄從 s 出發，到達每個點的最短路徑。
（二）說明計算與印出從起始點 s 到任意點 t ∈ V 的最短路徑的演算法。（解此小題時可參考Dijkstra 或其他演算法來設計，且不須將 Dijkstra 或別的演算法做詳細的描述。）
（20 分）
參考架構・破題
本題考最短路徑的「前驅節點（predecessor）」記錄法：只要為每個點存一個前一站指標，就能以 O(n) 空間表示從 s 出發的最短路徑樹，再由終點反向追回並反轉輸出。
完整答題架構與關鍵字：到站內看全文
- 4
有個矩陣 A[1..n] ， n 的值很大。在矩陣 A 中存有 n 個正整數，且從小到大排列。給定某個整數 x ，二分搜尋法（ binary search ）可以在 O (log n) 的時間內找出 x 在矩陣A[1..n] 的位置，或宣告在 A[1..n] 中沒有 x 。在某個應用中，已知絕大部分的 x 都會出現在矩陣 a[1..n] 的前面 m 個元素，且 m 的值遠小於 n ，但是無法預知 m 的範圍。設計一個演算法，可以在 O (log m) 的時間內完成搜尋。（20 分）
（20 分）
參考架構・破題
本題考指數搜尋（exponential search，又稱 galloping／doubling search）：先以倍增方式找出包含 x 的區間，再於該區間做二分搜尋，總時間只與 x 的位置 m 有關，為 O(log m)。
完整答題架構與關鍵字：到站內看全文
- 5
假設有個矩陣 A[1..n] 儲存 n 個整數。Quick sort 是一個排序演算法。假設有個副程式partition ( A, l , r ) 其輸入參數 A 是一個矩陣， l , r , l < r < n ，是兩個指標。其回傳的值 m也是一個指標。這個副程式可將矩陣中從 l 到 r 的這一段資料 A[l..r ] 區分成兩段：A[l..m] 和 A[m + 1..r ] ，使得在 A[l..m] 中的元素都小於或等於 x ，而在 A[m + 1..r ] 中的元素都大於或等於 x ，其中 x 是從 A[l..r ] 中隨機選擇的一個整數。接下來要在此兩段資料遞迴執行 partition。避免這些遞迴計算可以用一個堆疊（stack）來處理。假設partition ( A, l , r ) 回傳 m ，則執行：if (l < m) push (l , m) into stack if (m + 1 < r ) push (m + 1, r ) into stack一開始，堆疊中只有一組資料， (1, n) 表示 A[1..n] 需要排序。如此反覆將堆疊最上面的資料 (l , r ) 移出，執行 partition ( A, l , r ) ，直到堆疊沒有資料為止。（每小題 10 分，共 20 分）
（一）證明在最糟情況下，堆疊的高度可以達到 n / 2 。
（二）設計一個好的演算法以降低 stack 的高度，並證明堆疊的高度最多只需要 log n + 1 。
（20 分）
參考架構・破題
本題考非遞迴快速排序的堆疊空間分析：（一）構造最壞分割使堆疊累積約 n/2 筆；（二）改為「先處理較小段、較大段後處理」（較大段先 push、較小段後 push），可證堆疊高度不超過 log n + 1。
完整答題架構與關鍵字：到站內看全文
103 年（考試時間 120 分鐘） 原卷 PDF
- 1
給一個排序好的陣列（Sorted Array）A[low...high]，當我們要搜尋一個元素 X 是否在 此陣列 A 中， 二元搜 尋法（ Binary Search ） 是檢查 陣列的 中間位 置的元 素A[next], next = (low+high)/2，和 X 做比較，並依比較結果作下列更新。Case：A[next]＝X：return A[next]＞X：high next - 1 A[next]＜X：low next + 1重複上述步驟搜尋更新的陣列 A[low...high]直到找到 X 或確認 X 不是在此陣列 A 中。若我們設計一個新的搜尋法來修改二元搜尋法，每次都是以下列方式選取 A[next]。next←low+(high - low) * (X - A[low])／(A[high] - A[low])其他步驟都和二元搜尋相同。請回答下列問題：（每小題 5 分，共 15 分）新的搜尋法特色為何？請說明之。新的搜尋法在何種情形下，會比二元搜尋的搜尋速度為佳？請說明之。新的搜尋法，在最差的情況下，它的執行時間複雜度為多少？原因為何？假設陣列 A 中有 n 個元素。
（15 分）
- 2
L 為一鏈結串列（Linked List），函數 Reverse(L)是要求把在原來 L 的每個節點（Node）的地址指標（Pointer），更改為指向它在鏈結串列 L 中的前面一個節點。請設計一個以疊代（Iterative）方式的程式來執行函數 Reverse(L)的功能，程式限制只能使用常數個（constant）額外空間（External Memory），可用程式語言 C、C++、Java 或Pseudocode，寫出你的答案。請先說明你的作法，再寫出程式。（15 分）
（15 分）
參考架構・破題
本題考單向鏈結串列就地反轉（in-place reversal）：以三個指標 prev、cur、next 由頭到尾逐一把每個節點的 link 改指向前一個節點，時間 O(n)、額外空間 O(1)。
完整答題架構與關鍵字：到站內看全文
- 3
若只能使用下列 6 種方式排序（Sorting）：(a)Insertion Sort (b)Radix Sort (c)Merge Sort (d)Counting Sort (e)Heap Sort (f)Quick Sort。在下列各情形下，應選擇上述何種排序方法為最佳？請說明原因。（每小題 5 分，共 15 分）只要將全部資料中的前 20 名最大值排序好，並且主記憶體空間足夠。只有少數資料在被已排序好的資料修改過，需要重排序，並且主記憶體空間足夠。資料無明顯特性，需要做第一次的排序，並且主記憶體空間足夠。
（15 分）
參考架構・破題
本題考依資料特性選擇排序法：要比較各法的時間複雜度、是否需要全部排完、對近乎有序資料的表現，以及是否需額外記憶體或資料限制（Radix、Counting 需鍵值範圍或位數有限）。
完整答題架構與關鍵字：到站內看全文
- 4
如右的權重圖（weighted graph）共有 9 個節點（vertices）19 條邊（edges），回答下列問題：請列出在運用 Kruskal’s 演算法產生最小連結樹 F B（Minimum Spanning Tree）中把邊納入最小連結 14 D樹的順序。（3 分） I 2 G 17 10 7 13請列出運用 Prim’s 演算法從 A 點開始產生最小 11 E 15 A 3 6連結樹，把邊納入最小連結樹的順序。（4 分） 4 5 9設計一個 O(V)的演算法，判定在新增加一個 H 1 C (x,y)的邊到原圖形後，是否要更新已經產生的最小連結樹。（8 分）全一張（背面）
（15 分）
本題含圖表或公式，請對照原卷 PDF。
- 5
若處理的資料，其數值均不同且已知均為 1 到 100 之間的整數或小數。若 K≦X＜K+1，集合 Lx 代表數值在[K,K-1]間全部資料，1≦K≦99, K 為整數，資料結構支援下列功能。Insert(X)：增加 X，若 X 不存在 Lx 中。Delete(X)：移除 X，若 X 存在 Lx 中。List(X)：將 Lx 中的資料全部依序印出。設計一資料結構滿足在最差情況的條件分析（Worst Case Analysis），每個功能的執行時間要求為：Insert(X) and Delete(X)須在 O(log | Lx |)時間內完成，List(X)則須在O(| Lx |)時間內完成。請說明設計的資料結構為何？並解釋其執行時間為何滿足需求？（15 分）
（15 分）
參考架構・破題
本題考複合資料結構設計：先用陣列以 X 的整數部分 O(1) 找到對應的區間集合 Lx，再讓每個 Lx 以平衡二元搜尋樹（AVL 或紅黑樹）存放，使插入、刪除為 O(log |Lx|)，中序走訪可在 O(|Lx|) 依序印出。
完整答題架構與關鍵字：到站內看全文
- 6
若 G=(U,E)為一權重圖（weighted graph），每條邊的權重均不為負數，則單源最短路徑問題（Single Source Shortest Path Problem）可以用著名的 Dijkstra 演算法求得，回答下列問題：（每小題 5 分，共 15 分）說明 Dijkstra 演算法的主要觀念。Dijkstra 演算法在最差情況下（Worst Case Analysis），下列三個功能 Insert、Delete、Decrease_Key 各自需要執行的次數，可用 Big-Oh 符號表示。若是要在 O(| E | + | V | log | V |)最差情況分析下的時間內執行 Dijkstra 演算法，請問該選擇使用那種資料結構，並說明其原因。
（15 分）
參考架構・破題
本題考 Dijkstra 演算法的貪婪觀念與優先佇列操作次數分析，並說明以費波那契堆積（Fibonacci heap）實作可達 O(|E| + |V| log |V|)。
完整答題架構與關鍵字：到站內看全文
- 7
下 面二小題 各有 一段程式 ，其 執行的時 間是 以執行 sum++的 次數計 算，請用Θ-notation 表示其執行時間，並說明其理由。（每小題 5 分，共 10 分）sum=0 for(i=0; i＜2*n; i++) for(j=0; j<i; j++) sum++; sum=0 for(i=1; i＜2*n; i++) for(j=1; j＜i*i; j++) for(k=1; k<j; k++) if(j%i==1) sum++;
（10 分）
參考架構・破題
本題考迴圈的次數分析：把 sum++ 的執行次數寫成總和式，化簡後取最高次項，以 Θ 表示。第二小題的陷阱在於 if 條件會篩掉大部分 j，要算的是「sum++ 被執行的次數」而不是迴圈跑了幾次。
完整答題架構與關鍵字：到站內看全文
102 年（考試時間 120 分鐘） 原卷 PDF
- 1
將整數資料 80, 40, 19, 120, 94, 110, 115, 90, 88, 92, 98 依序存入一棵空的二元搜尋樹（binary search tree）。
（一）請畫出完成資料輸入的二元搜尋樹。（6 分）
（二）從（一）產生的二元搜尋樹中刪除（delete）資料 94，請畫出完成刪除動作後的二元搜尋樹。（給出一個正確樹即可）（6 分）
（三）請寫出自二元搜尋樹找到最大值資料所在節點（node）的演算法。（10 分）
（22 分）
參考架構・破題
本題考二元搜尋樹（BST）的插入、刪除與找最大值。插入依「小往左、大往右」逐一比較；刪除有兩個子節點的節點要用中序後繼或中序前驅取代；最大值在最右邊的節點。
完整答題架構與關鍵字：到站內看全文
- 2
請寫出執行下列程式碼的時間複雜度，並敘明理由。（10 分）for (i = 1; i < n; i++){ a = 1; b = n; while( a < b ){ a = 3 * a; b = b / 3; } }
（10 分）
- 3
下圖為一 AVL 樹 T，請依各小題要求加入指定新資料後，畫出新產生的 AVL 樹。每小題各自獨立，都是對原先的 AVL 樹 T，加入資料。20 80 10 30 90 25 70 35 50
（一）加入資料 27。（6 分）
（二）加入資料 45。（6 分）
（三）加入資料 95。（6 分）全一張類 科： 資訊處理
（18 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
函數 f (n)定義如下，其中 n 為非負整數。⎧0, 若n = 0 ⎪ f (n) = ⎨1, 若n =1 ⎪ f (n − 1) + f (n − 2), 若 n > 1 ⎩
（一）請設計遞迴演算法，輸入非負整數 n，輸出 f (n)數值。（7 分）
（二）請設計非遞迴演算法，輸入非負整數 n，輸出 f (n)數值。（7 分）
（三）請分別說明（一）與（二）所設計演算法的時間複雜度（time complexity）。（10 分）
（24 分）
- 5
（一）依據下圖內容，請寫出它的相鄰矩陣（adjacency matrix）表示法。（4 分）6 13 a b e d 15 5 9 8 16 7 c f g 12 3
（二）請定義生成樹（spanning tree）。（6 分）
（三）請畫出此圖的最小成本生成樹（minimum cost spanning tree），以及計算最小成本。（10 分）六、有一雜湊表格（hash table）T 的記憶空間共含 11 個桶（buckets），位址編號由 0 至10，每個桶有一個槽（slot）。雜湊函數 h1 定義為 h1(key) = key % 11，當有碰撞（collision）發生時採二次雜湊開放定址法（open addressing with double hashing）處理，其函數定義為 h(key, j) = (h1(key)＋j * h2(key)) % 11，其中 j 為碰撞次數，j = 1, 2, 3, ..., 11，h2(key) = 1＋(key % 10)。欲將 26 放入雜湊表格 T，總共經過 6 次探測才成功找到存放位址。請問 26 在雜湊表格 T 的探測順序為何？（6 分）
（26 分）
本題含圖表或公式，請對照原卷 PDF。
其他等別的「資料結構」
- 資料結構（地方特考三等）（63 題）
題目來源：考選部考畢試題查詢平臺（政府資訊公開資料）；參考架構為本站自撰，僅供準備方向參考，非官方標準答案。最後更新：。