資料結構 申論題歷屆試題與參考架構
地方特考三等，民國 102～114 年共 13 份試卷、63 題，其中 41 題附參考答題架構。考這一科的類科：資訊處理、離島・資訊處理。本頁列出歷年全部題目，參考架構只列開頭的「破題」，完整的答題架構、關鍵字與作答提醒請到站內查看。
114 年（考試時間 120 分鐘） 原卷 PDF
- 1
請回答下列問題：（每小題 4 分，共 20 分）
（一）請說明堆疊（Stack）及佇列（Queue）那一種資料結構較適合用來進行後序（Postfix）運算式的計算？
（二）請說明在二元搜尋樹中，前序（Preorder）走訪、中序（Inorder）走訪、後序（Postorder）走訪、層序（Level-order）走訪那一種走訪順序可得到遞增的鍵值？
（三） 請 說 明 在使用 雜 湊 表 時，若 使 用 鏈 結串列 （ chaining ）處 理 碰 撞（collision）問題，則搜尋的平均時間複雜度為下列何者？O(1)、O(log n)、O(n)或 O(sqrt{n})。
（四）請說明若一個圖 G（V, E）的頂點數|V|為 n，而邊數|E|接近 n²，則相鄰串列（adjacency list）、相鄰矩陣（adjacency matrix） 、或邊列表（edge list）中，那一種資料結構最適合用來儲存該圖？
（五）下列那幾項演算法可用於找出圖的最小生成樹（Minimum Spanning Tree）：Dijkstra 演算法、Floyd-Warshall 演算法、Prim 演算法、Bellman- Ford 演算法？
（20 分）
參考架構・破題
本題全面檢驗資料結構核心基礎觀念，包含堆疊與運算式評估、二元搜尋樹之走訪特性、雜湊表碰撞處理之效能分析、稠密圖之儲存結構選擇，以及圖形演算法中最小生成樹與最短路徑演算法之辨析。作答應精準指出正確選項，並簡明扼要闡述背後的底層運作機制與時間複雜度依據。
完整答題架構與關鍵字：到站內看全文
- 2
Priority Queue（優先佇列）是一種「每次取出的元素都是優先權最高的」資料結構。
（一）如果用「排序好的陣列」來實作優先佇列，插入與取最大值的時間複雜度為何？（5 分）
（二）如果用「未排序陣列」 ，來實作優先佇列，插入與取最大值的時間複雜度為何？（5 分）
（三）如果用最大堆積（max-heap）來實作優先佇列，插入與取最大值的時間複雜度為何？（5 分）
（四）請以最大堆積來實作優先佇列，並顯示以下動作過程的最大堆積樹：加入 10, 30, 50, 40，取出最大數，加入 50, 60，取出最大數。（10 分）
（25 分）
參考架構・破題
本題評量優先佇列（Priority Queue）於不同底層資料結構（已排序陣列、未排序陣列、最大堆積）下的時間複雜度差異，以及最大堆積（Max-Heap）的動態操作與樹狀調整過程。
完整答題架構與關鍵字：到站內看全文
- 3
二元搜尋樹（binary search tree）是一種常見的資料結構。
（一）請將 50, 30, 70, 20, 40, 60, 80 依序插入一個二元搜尋樹，然後再從該二元樹刪除 50，並畫出每個數字放入或刪除後的二元搜尋樹。 （10 分）
（二）以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，若針對該二元樹刪除 40，請顯示該陣列的變化。（5 分）i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 A(i) 40 30 70 10 -- 50 90 -- 20 -- -- -- 60 80 -- -- --
（三）以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，若針對該二元樹刪除 30，請顯示該陣列的變化。（5 分）i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 A(i) 40 30 70 10 -- 50 90 -- 20 -- -- -- 60 80 -- -- --
（四）以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，請列舉可依序插入的五個數值，使得該二元樹成為完整二元樹（full binary tree）。（10 分）i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 A(i) 40 30 70 10 -- 50 90 -- 20 -- -- -- 60 80 -- -- --
（30 分）
參考架構・破題
本題評量二元搜尋樹（BST）的建立、節點刪除機制（前驅與後繼節點替代），以及一維陣列儲存二元樹時的索引映射關係與完全二元樹（Complete Binary Tree）之結構補全。
完整答題架構與關鍵字：到站內看全文
- 4
一個自動化工廠大量採用機器人協助裝箱作業。該工廠固定時間生產出一組 n 個不同大小的塑膠球並放到裝箱作業輸送帶上。輸送帶上配置數個機器人，當輸送帶上的球經過時，機器人負責將眼前兩顆球將順序排序正確，大的在前，小的在後。當輸送帶上的球經過了所有機器人後，球的順序就完全由大排到小了。（每小題 5 分，共 25 分）
（一）若 n = 6，且生產後放上裝箱輸送帶的球的大小為 3, 2, 5, 6, 1, 4。請說明若輸送帶配有 4 個機器人是否足夠將球的順序完全由大排到小？
（二）若 n = 20，且生產後放上裝箱輸送帶的球的大小為 11, 12, 20, 16, 3, 1, 7, 15, 2, 18, 10, 5, 14, 6, 8, 13, 19, 4, 9, 17，請說明輸送帶上最少該配置幾個機器人才能將球的順序由大排到小？
（三）若 n = 6，且輸送帶上配有 4 個機器人，請給一組放上裝箱輸送帶的球的大小順序，使得其經過這 4 個機器人後，整組球的順序仍未能排好。
（四）若每一組球生產後放上裝箱輸送帶的球的大小順序非固定順序，請說明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排到小？
（五）若 n = 10，且每一組球生產後放上裝箱輸送帶的球的大小順序非固定順序。假設輸送帶上原本配置 n 個機器人，若改成配置 2n 個機器人，整組球順序排好的速度可以加快多少？請說明。
（25 分）
參考架構・破題
本題以輸送帶機器人對塑膠球進行相鄰兩兩排序為情境，本質為氣泡排序法（Bubble Sort）的實體管線化（Pipelining）模型；評量相鄰交換之最差情況移動距離、逆序數與管線延遲概念。
完整答題架構與關鍵字：到站內看全文
113 年（考試時間 120 分鐘） 原卷 PDF
- 1
考慮下面以虛擬碼（Pseudocode）表示的遞迴演算法，請回答相關問題：Algorithm Q(n) if n＝1 return 1 else return Q(n－1)＋2n－1
（一）列出虛擬碼中 Q(n)的遞迴關係式，並說明此虛擬碼最終計算的是什麼？（5 分）
（二）用遞迴函式表示此虛擬碼所使用的乘法運算次數，並用漸進式符號Big-O 表示此遞迴函式的成長速率。（5 分）
（三）以遞迴函式表示此虛擬碼的執行時間 T(n)並說明其時間複雜度（以Big-O 表示）。（10 分）
（20 分）
- 2
請回答下列關於二元樹（Binary Tree）的問題：
（一）一個算術運算式（Arithmetic Expression）可以用一個二元樹表示，稱為算術運算樹（Expression Tree），請將下列算術運算式以算術運算樹表示。（5 分）( ( ( 5 + 1 ) 3 － (7 + 2 ) ) / ( ( ( 2 8 ) + 5 ) / 7 ) )
（二）請判斷下列敘述是否正確：（5 分）“一個算術運算樹是一個滿二元樹（Full Binary Tree, or Proper Binary Tree）”
（三）子題（一）中的算術運算式是何種順序的運算表示式？請利用其算術運算樹將此運算式表示為一前序表示式（Preorder Expression），並說明其過程。（5 分）
（四）請敘述如何以子題（一）的算術運算樹計算出算術運算式的值，並逐步表示其過程。 （10 分）
（25 分）
參考架構・破題
本題運算式中缺漏的符號依上下文應為乘號，即 (((5+1)×3−(7+2)) / (((2×8)+5)/7))。重點在建運算樹、判斷滿二元樹、轉前序式，以及用後序走訪求值。
完整答題架構與關鍵字：到站內看全文
- 3
在許多應用中，往往需要以物件的優先權來進行處理，為了區別物件的優先順序，我們可以簡單地賦予物件一個鍵值（Key）來代表優先權，此鍵值通常是一個數值可以用來區別物件前後順序。在此，我們考慮物件的鍵值是一個數值而其值愈小，物件的優先權愈高，優先佇列（Priority Queue）則是一種以物件的優先權來管理物件的資料結構。
（一）請說明優先佇列的抽象資料型態（abstract data type, ADT）定義。（10 分）
（二）給定一個最小二元堆積（Minimum Heap）H 與一個鍵值 k，在 H 中快速地找出所有鍵值小於或等於 k 的資料物件。請描述一個有效的方法，此方法所花的時間（或運算量）與欲找出的資料物件之數量成線性比例。（5 分）
（15 分）
參考架構・破題
優先佇列為電腦科學中管理動態權重集合的基礎抽象資料型態。本題首要闡明其形式化操作介面與語意規範；次就最小堆積結構，設計能在輸出敏感時間內檢索所有鍵值不超過門檻 k 之高效演算法，並嚴謹證明其時間複雜度與符合物件數量成線性比例。
完整答題架構與關鍵字：到站內看全文
- 4
關於紅黑樹（Red Black Tree）與(2,4)-樹((2,4)-Tree)：
（一）請分別說明紅黑樹與(2,4)-樹的定義。（10 分）
（二）考慮下面的紅黑樹（實線節點代表黑色節點，虛線節點代表紅色節點），代表節點的字元符號可視為鍵值，請說明如何將此紅黑樹轉換為一個(2,4)-樹，並將其結果畫出。此外，請申論轉換的(2,4)-樹是否唯一。（10 分）
（三）請說明為何一個有 n 個節點（鍵值）的紅黑樹其高度是 O(log n)。（5 分）
（25 分）
- 5
下面的矩陣 M 是表示一個無向圖 G=(V, E)的相鄰矩陣（Adjacency Matrix），V 與 E 分別為節點與邊的集合：a b c d e f g a 0 1 0 1 1 1 0 b 1 0 1 0 1 1 0 c 0 1 0 0 0 1 1 d 1 0 0 0 0 0 1 e 1 1 0 0 0 0 0 f 1 1 1 0 0 0 1 g 0 0 1 1 0 1 0
（一）請畫出此無向圖 G。（10 分）
（二）若以字母順序為考量對 G 進行廣度優先搜尋（Breadth-First Search, BFS） ，因此將由節點 a 開始，請繪出尋訪完後所產生的 BF 樹（Breadth- First (BF) Tree）。（5 分）
（15 分）
112 年（考試時間 120 分鐘） 原卷 PDF
- 1
請以 C, C++, C#, Java 或 Python 撰寫 2 個方法，一個以迴圈方式，一個以遞迴方式，對存在 singular linked list 的資料進行 linearly search。假設Node 的結構如下：（12 分）
（12 分）
參考架構・破題
本題測驗單向鏈結串列之基本走訪操作與程式實作能力。作答應先定義清晰之節點結構，隨後分別以迴圈迭代與遞迴呼叫兩種核心程式設計範式實作線性搜尋，並比較兩者在執行時間、呼叫堆疊空間與終止判斷上的關鍵差異。
完整答題架構與關鍵字：到站內看全文
- 2
請為數列 0, 10, 30, 20, 50, 80, 40, 90, 70, 60 建立 AVL tree, Min/Max heap, 2− 4 tree，並依它們的性質以 yes or no 完成下表。註：所建立的 tree or heap請以圖示，如果是 Searching Tree，請以左小右大的方式建立。 （24 分）Balance Searching Tree AVL tree Min heap Max heap 2− 4 tree
（24 分）
參考架構・破題
依序插入 0,10,30,20,50,80,40,90,70,60，分別建立 AVL tree、Min heap、Max heap、2-4 tree，畫出結果並依「平衡」與「搜尋樹」性質填表。
完整答題架構與關鍵字：到站內看全文
- 3
請以如下的 Huffman Tree 所做的數字編碼，解讀 01010111110100100011編碼對應的數字。（10 分）
（10 分）
- 4
針對如下的有向圖（節點為走訪對象，連線上的數字為走訪的 cost） ，依如下 BFS（配合 queue）與 DFS（配合 stack）演算法，進行所有節點的走訪，多個節點可以走訪時，以連線上 cost 較低者優先，結果請以迴圈內部的顯示要求，依下表形式填入（stack 垂直表示，開口在上方，queue水平表示，出口在左，入口在右） 。註：假設節點 S 為起始點。（24 分）BFS 演算法 Loop1 … DFS 演算法 Loop1 … print node print node queue Stack processSet processSet BFS/DFS 演算法（/前為 BFS 使用 queue, /後為 DFS 使用 stack）Step1: set queue/stack to empty set processSet to empty Step2: enqueue/push S and add S into processSet Step3: while queue/stack is not empty Step31: dequeue/pop and print it Step32: enqueue/push all one step neighbors which are not in processSet according to the cost of edges and add them into processSet Step33: display content of queue/stack and processSet
（24 分）
參考架構・破題
依題目給的演算法（加入時即標記 processSet）分別以 queue 與 stack 走訪有向圖，鄰點依邊的 cost 由小到大處理，每一輪填出 print node、容器內容與 processSet。
完整答題架構與關鍵字：到站內看全文
- 5
請完成下列表格有關排序演算法的 time complexity（假設排序資料有 n個，資料位數有 d 個） 、是否為 In− Space 演算法、是否為 Stable 演算法及範例數列 50, 46, 37, 28, 19 進行降冪排列時所需的比較次數。（30 分）Time Complexity In−Space Stable 降冪比較次數排序演算法Best Worst （Yes/No） （Yes/No） 50, 46, 37, 28, 19 Bubble Insertion Merge（奇數時，後半段多 1）Quick（第一個當pivot）Radix（base 10）Selection
（30 分）
111 年（考試時間 120 分鐘） 原卷 PDF
- 1
請用 Big-O 符號來表示下列函式的成長速率，並說明之：
（一）T( ) = 3 + 7 √ + log （5 分）
（二）T( ) = 2T( ⁄2) + （10 分）
（15 分）
- 2
常用的算術運算式（ Arithmetic Expression）有：中序運算式（ Infix Expression）、前序運算式（Prefix Expression）、後序運算式（Postfix Expression）三種表示法，考慮下面的算術運算式（Arithmetic Expression）並回答下列問題：((6 (5 – 3))-(1 + 2))(((4 + 2)/ 3)+(5 4))
（一）請寫出其前序運算式（Prefix Expression） 。（5 分）
（二）請繪出其算術運算樹（Expression Tree）。（5 分）
（三）請說明如何以此算術運算樹計算出算術運算式的值，並一步一步列出運算過程。 （10 分）
（20 分）
- 3
回顧二元樹結構，其為 m 路樹（m-ary Trees，亦稱多元樹、m 元樹）的一個特例，請回答下列相關問題：
（一）給出 m 路樹的定義。（5 分）
（二）若用陣列來表示一個 m 路樹，請說明如何利用陣列的索引值來表示節點間的親子連結關係（意即，假設陣列索引起始值為 0，若節點 v 在陣列的第 i 個位置，節點 v 的第 c 個子節點的位置為何？另一方面，節點 v 的 parent 位置為何？）？（10 分）
（三）基於此 m 路樹結構及二元搜尋樹（Binary Search Tree）的概念，我們可以定義出一個多元搜尋樹。當 m=4 的時候，可以稱此搜尋樹為四元搜尋樹。請給出(2,4)-樹((2,4)-tree)的定義並比較與四元搜尋樹的差異。（10 分）
（25 分）
- 4
二元堆積（Binary Heap）是一種優先佇列（Priority Queue），主要用來管理具有優先權順序的資料物件，每個資料物件具有一個可以界定大小或前後順序的鍵值（Key） ，我們在此假設鍵值越低的資料物件有越高的優先權。
（一）請完整描述最小堆積（Min_Heap）的定義與相關的操作功能。 （5 分）
（二）請說明堆積排序（Heap Sort）的方法並分析其時間複雜度。（5 分）
（三）若有兩個二元樹 T1 及 T2，其節點具有堆積特性且高度分別是 O(log n)與 O(log m)，請提供一個方法將此兩個二元樹結合成為一個節點具有堆積特性的二元樹 T，此方法的時間須為 O(log n+ log m)。（10 分）
（20 分）
參考架構・破題
本題評量二元堆積（Binary Heap）中最小堆積（Min-Heap）的定義與基本操作、堆積排序法之執行步驟與複雜度推演，以及如何利用樹高特性在對數時間內合併兩個獨立的二元堆積。
完整答題架構與關鍵字：到站內看全文
- 5
下圖是一個加權圖 G=(V, E)，其中 V 是點集合而 E 是邊集合。
（一）請使用相鄰矩陣（Adjacency Matrix）表示法來表示加權圖 G。 （5 分）
（二）不考慮權重，從節點 g 開始並按照字母順序對 G 進行廣度優先尋訪（Breadth-First Search, BFS），請繪出尋訪完後所產生的 BFS 樹（BFS Tree）。（5 分）
（三）請利用 Prim's 演算法，從節點 d 起始，找出一個最小擴張樹（Minimum Spanning tree），請以圖示方式一步步畫出過程與結果，並說明 Prim's演算法的時間複雜度。（10 分）
（20 分）
參考架構・破題
依圖讀出 8 個節點（a,b,c,d,f,g,h,i）與 11 條無向加權邊，分別完成相鄰矩陣、從 g 的 BFS 樹，以及從 d 起始的 Prim 最小擴張樹並分析複雜度。
完整答題架構與關鍵字：到站內看全文
110 年（考試時間 120 分鐘） 原卷 PDF
- 1
（一）請分別寫出下圖二元樹的前序走訪法（preorder traversal） 、中序走訪法（inorder traversal）、後序走訪法（postorder traversal）的結果（6 分）
（二）請在無法預知二元樹的節點數條件下，設計在程式中表示二元樹的資料結構。再假設二元樹已依前述結構儲存在程式，設計一副程式（或函式）的演算法，在提供樹根給此副程式（或函式）後，其執行二元樹中序走訪法的程序並輸出走訪結果。此副程式（或函式）不可使用遞迴呼叫技術但可添加其他資料結構，演算法的時間複雜度和空間複雜度須均為 O(n)，n 為二元樹的節點個數。演算法可以虛擬碼（pseudo- code）或以高階語言如 C 呈現。需分析說明副程式（或函式）演算法的時間複雜度和空間複雜度均為 O(n)。（提醒：若用遞迴呼叫技術設計，演算法部分不給分） （13 分）
（三）請分別說明在程式執行過程，以第（二）子題非遞迴呼叫技術設計相較於以遞迴呼叫技術設計在時間與空間的效能優勢各為何？（6 分）A B C D E F G H K
（25 分）
本題含圖表或公式，請對照原卷 PDF。
- 2
二維方陣 A 大小為 nn，方陣中的元素除了主對角線之元素以及緊鄰它的上下兩條對角線之元素的值可能不為零外，方陣 A 其他元素之值一定為零，以 55 方陣為例如下圖。請以一維陣列 B 設計儲存此方陣 A 之結構，陣列 B 之索引值自 0 開始，且陣列 B 的元素數量須小於或等於 3n-2。設計的結構須包含如何有效率地決定儲存方陣 A 之元素 aij 以及如何自陣列 B 中取得或決定方陣中元素 aij 值，其中 0 i, jn-1 而 i 與 j 分別為元素在方陣 A 中之列號與行號。（20 分） a00 a01 0 0 0 a a11 a12 0 0 10 0 a21 a22 a23 0 0 0 a32 a33 a34 0 0 0 a43 a44
（20 分）
參考架構・破題
本題為三對角矩陣（Tridiagonal Matrix）的壓縮儲存：非零元素只在 |i−j|≤1，共 3n−2 個，以列主序存入一維陣列 B，並推導 aij 與 B 索引的對應公式。
完整答題架構與關鍵字：到站內看全文
- 3
（一）請畫出下圖以鏈結串列（link list）為基礎的相鄰串列（adjacency list）結構表示之結果。（5 分）
（二）請運用一維陣列設計一資料結構採循序串列（sequential list）架構，其仍舊以類似子題（一）相鄰串列策略表示無向圖（undirected graph）節點與邊的關係，但僅以一維陣列呈現第（一）子題之相鄰串列概念。圖之節點與邊的關係僅以此一維陣列元素記錄並呈現，不可使用其他資料結構，另外，陣列中亦需記錄此陣列中用來記錄與圖相關資訊之元素個數；除了說明資料結構外，也請寫出下圖以此資料結構表示之一維陣列結果。（8 分）
（三）請列出兩項在程式中以第（一）子題之以鏈結串列（link list）表示圖比以第（二）子題一維陣列表示圖適合的應用情境或效能優勢。另外，也請列出兩項在程式中以第（二）子題一維陣列表示圖比以第（一）子題鏈結串列（link list）表示圖適合的應用情境或效能優勢。（12 分）1 0 3 2
（25 分）
- 4
區間堆積（interval heap）是一種優先佇列（priority queue），請回答下列相關的問題。
（一）從一個沒有元素的區間堆積開始，依序插入 40, 30, 60, 15, 14, 19, 80, 12, 90 等元素。請畫出最後區間堆積的樹狀結構圖。 （9 分）
（二）請自第（一）子題建構的區間堆積中刪除元素 12，並畫出刪除該元素後區間堆積的樹狀結構圖。（3 分）
（三）請以一維陣列設計資料結構儲存區間堆積，該資料結構可以透過節點對應之陣列索引值 index 構成的數學式計算出其父節點 parent、左子節點 left、右子節點 right 與兄弟節點 brother 等在陣列中的索引值。假設此一維陣列之起始索引值為 0，請列出由 index 構成的計算 parent、left、right、brother 的數學式。並請畫出以此一維陣列儲存第（一）子題建構完成的區間堆積的結果。 （12 分）
（四）舉例並說明一既需要提供最高優先元素，也需要提供最低優先元素的優先佇列的應用實例或系統。（6 分）
（30 分）
109 年（考試時間 120 分鐘） 原卷 PDF
- 1
請設計演算法複製一棵二元樹（copy a binary tree）。（10分）
（10 分）
- 2
（一）請描述 order 為 m 的 B-tree 之特性。（6分）
（二）請問 order 為 m 高度為 h 的 B-tree：⑴最多有幾個節點？最多有幾個Key？（6分）⑵最少有幾個節點？最少有幾個 Key？（8分）
（20 分）
參考架構・破題
本題考 B-tree 的結構限制，並由限制推出節點數與鍵值數的上下界。先把定義寫清楚（order m 指每節點最多 m 個子節點），高度的計算方式（根在第 1 層）也要先講明，後面的公式才不會被質疑。
完整答題架構與關鍵字：到站內看全文
- 3
請利用 Double Hashing 將下列 key 值放入 hash table of size 13中（如表1）： （14分）{24, 53, 17, 46, 14, 32, 37, 92} h1(k)=k mod 13，h2(k)=1+(k mod 11)，h(k,i)=(h1(k)+i*h2(k)) mod 13 (i=0, 1,…, 12)表1 0 1 2 3 4 5 6 7 8 9 10 11 12
（14 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
（一）在一棵高度為 h(h=0,1,2,…)的 AVL tree 中：⑴高度為6之 AVL tree 最多可能有幾個 nodes？最少可能有幾個 nodes？（假設 root 之 h=0） （6分）
⑵假設此樹共有45個 nodes。請問此 AVL tree 可能最高之高度及最矮之高度各為何？（6分）
（二）請將下列數字{17, 60, 24, 5, 7}逐步插入圖1的 AVL tree 中，並平衡之。（12分）圖1
（24 分）
本題含圖表或公式，請對照原卷 PDF。
- 5
請利用堆積排序法（Heap Sort）將圖2逐步建立成 Min Heap，並將數字從小到大逐一列舉。（10分）圖2
（10 分）
本題含圖表或公式，請對照原卷 PDF。
- 6
（一）請利用 KMP（Knuth, Morris, Pratt）演算法寫出失敗函數（failure function)之定義。 （4分）
（二）找出 pattern “abcdabcabcdabcdabc”之失敗函數（failure function）值（請填入表2 failure value 中）。 （14分）
（三）假設（二）之 pattern 嘗試在 string “abcdabcabcdabcabcda…..”找出 pattern。當 pattern 從 index 0開始比對到 index 13都一樣，而在 index 14時發現字母不一樣，請問 pattern 如何利用 failure function 所得之結果很快找到下一個要對應之位置？也就是 pattern 的那一位置的值要位移到string 的那一對應位置。（4分）表2 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 string a b c d a b c a b c d a b c a b c d a pattern a b c d a b c a b c d a b c d a b c failure value ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
（22 分）
本題含圖表或公式，請對照原卷 PDF。
108 年（考試時間 120 分鐘） 原卷 PDF
- 1
對下列三個程式片段，請使用 Big-O 符號，分別估計其最長執行時間 （worst time）。程式片段中，S 代表一段沒有與 n 相關的迴圈（no n-dependent loops）。
（一） for (int i = 0; i * i < n; i++) （5 分）S
（二） for (int i = 0; Math.sqrt (i) < n; i++) （5 分）S
（三） int k = 1; （10 分）for (int i = 0; i < n; i++) k *= 2; for (int i = 0; i < k; i++) S
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 2
有下列資料元素（data elements） ，其數值越小則優先權（priority）越高，請分別依序將各元素加入（add）優先佇列（priority queue）中，且分別以下列三種資料結構實作之。90, 10, 80, 20, 70, 50, 40, 30
（一）用雙向鏈接串列（doubly-linked list）來實作此優先佇列，請畫出其資料結構圖。 （6 分）
（二）用紅黑樹（red-black tree）來實作此優先佇列，請畫出其資料結構圖。注意: 紅節點請標示 R，例如 20R 表示其值為 20 的紅（Red）節點；黑節點則請標示 B，例如 50B 表示其值為 50 的黑（Black）節點。 （7 分）
（三）用最小堆積（min heap）來實作此優先佇列，請畫出其資料儲存的陣列（array）圖。注意: 陣列索引（array index）由左向右遞增。 （7 分）
（20 分）
參考架構・破題
同一組資料用三種結構實作優先佇列，考的是各結構的插入規則：串列維持排序、紅黑樹依插入修正規則旋轉與換色、最小堆積往上調整（heapify up）。每一步要畫得出來，最後的圖才可信。
完整答題架構與關鍵字：到站內看全文
- 3
下圖為一棵 2-3-4 樹。
（一）請畫出對應的紅黑樹（red-black tree）。請參閱上題紅黑樹節點的標示說明。（6 分）
（二）首先，插入（insert）33；接著，刪去（delete）78。請分別畫出對應的 2-3-4 樹與紅黑樹。（14 分）40 62 83 10 20 31 45 55 70 78 90 92
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
下面的無向圖（undirected graph）表示四個人的關係，如張三與李四有關係，這二人之間有邊（edge）相連，則可走訪。括弧內為人名縮寫，如張三（Chang San）的縮寫為 CS。若同時有兩個以上的人可處理，則先處理人名縮寫的字母順序較小者。李四(LS)張三 王五(CS) (WW)趙六(CL)
（一）由張三（CS）出發，用佇列（queue）做廣度優先搜尋（breadth-first search）走訪所有人，請寫出走訪順序的中文人名。 （10 分）
（二）由張三（CS）出發，用堆疊（stack）做深度優先搜尋（depth-first search）走訪所有人，請寫出走訪順序的中文人名。 （10 分）
（20 分）
- 5
將下列六個鍵值: 33, 72, 71, 55, 112, 109存入大小為 19 的雜湊表（a hash table of size 19）雜湊函數 h 為: h(key) = key mod 19分別用下面兩種衝突處理方式（collision handler） ：
（一）間隔為 1（offset of 1）（12 分）
（二）間隔為商（quotient-offset）（8 分）請分別寫出兩個雜湊表；並在間隔為 1 的雜湊表上，標示出一次聚集（primary clustering）。
（20 分）
參考架構・破題
本題考開放定址法的兩種探測方式：線性探測（間隔 1）會產生一次聚集，以商為間隔的探測則讓不同鍵走不同步長以減少聚集。先算出每個鍵的雜湊值，再逐一處理碰撞。
完整答題架構與關鍵字：到站內看全文
107 年（考試時間 120 分鐘） 原卷 PDF
- 1
計算正整數 a 和 b 的最大公因數 gcd(a, b)的演算法，以類似 C 語言表示如下: 1 integer gcd(a, b) { 2 x = a; y = b; 3 while (y > 0) {r = x % y; x = y; y = r;} 4 return x; 5 }其中資料型態 integer 表示整數，x % y 表示 x 除以 y 的餘數。請回答下列問題：（每小題 10 分，共 20 分）
（一）請證明：輸入任意兩個正整數，此程式執行一定時間後就會停止，不會造成無窮迴圈。
（二）假設 a > b，請證明此程式之 while 迴圈（第 3 行）至多只會被執行2 log2 b +1 次。
（20 分）
- 2
給定一個權重圖（weighted graph），G =(V, E, w)，假設 V = {1, 2,...,n}，且每個邊（edge）e 的權重 w(e)都是正整數。令 l(v)為以 v 為端點的所有邊中權重最小的邊。將這些邊集合起來稱作 L，也就是 L = ∪ l (v) 。v∈V（每小題 5 分，共 20 分）
（一）假設每個邊的權重都不相同。請證明由 L 中這些邊所構成的子圖 （edge induced subgraph）G[L]沒有迴圈。
（二）G[L]是否一定是 G 的擴張樹（spanning tree）？若是請證明之，若不一定是請給一個反例。
（三）用以上之結論，設計一個計算 G 的最小權重擴張樹 （minimum spanning tree）的演算法。
（四）在一般的應用中，邊的權重可能會相同，請修正上述之演算法，使修正後之演算法可以正確找出答案。
（20 分）
參考架構・破題
本題是 Borůvka 演算法的推導：每個頂點選最輕的鄰邊，這些邊必屬於最小擴張樹，但未必連通，所以要縮點後重複。四小題依序是無迴圈證明、反例、演算法設計、權重相同時的處理。
完整答題架構與關鍵字：到站內看全文
- 3
假設陣列 A[1..n]儲存 n 個正整數 x1, x2,..., xn。（每小題 10 分，共 20 分）
（一）已知所有的正整數 xi ≤ M。請設計一個 O(n + M )時間的演算法將這些整數由小到大排列。
（二）已知所有的正整數 xi ≤ n2。請設計一個 O(n)時間的演算法將這些整數由小到大排列，或證明這是不可行的。
（20 分）
參考架構・破題
本題考非比較式排序。比較式排序下界為 Ω(n log n)，要突破就得利用數值範圍：範圍 M 用計數排序 O(n+M)；範圍 n² 則把數字看成 n 進位的兩位數，用基數排序在 O(n) 完成，所以第二小題是「可行」。
完整答題架構與關鍵字：到站內看全文
- 4
假設有個陣列 A[1..n]儲存著 n 個整數。可將 A[1..n]看成二元樹，其中 A[1]是樹根。A[i]的左右子節點分別為 A[2i]和 A[2i + 1], i =1, 2, . . . , n/2。若2i>n 或 2i+1>n，則這些子節點是不存在的。若 A 滿足 A[i] ≥ max{A[2i], A[2i + 1]},1 ≤ i ≤ n/2，則稱陣列 A[1..n]是一個堆疊（heap）。假設有個副程式 sift(A, r, n)其輸入參數 A 是一個陣列，n 是 A 的大小，r ≤ n 是一個指標，指向此子樹的樹根。副程式 sift(A, r, n)的功能是將 A[r]為樹根的子樹變成 heap。在呼叫 sift(A, r, n)之前，它的左右子樹都已經是 heap。副程式 sift(A, r, n)所需的計算時間是 O(h(r))，其中 h(r)是以 A[r]為樹根的子樹的高度，也就是從樹根到任一樹葉的最長距離。（每小題 10 分，共 20 分）
（一）用 sift(A, r, n)設計一個線性時間的演算法，將陣列 A[1..n]變成 heap。
（二）分析以上所設計演算法的計算複雜度為 O(n)。
（20 分）
參考架構・破題
本題是由下而上建堆（bottom-up heap construction，Floyd 方法）。從最後一個非葉節點往根逐一呼叫 sift，可在 O(n) 完成；分析關鍵在於多數節點高度很小，不能直接用 O(n log n) 的粗估。
完整答題架構與關鍵字：到站內看全文
- 5
斐波納契數（Fibonacci number）Fn 的定義是 F0 = 0, F1 = 1, Fn = Fn－1+ Fn－2, n> 1。計算 Fibonacci number Fn 的演算法，以類似 C 語言表示如下：1 integer f [N]; // array of N integers 2 integer F(n) { 3 if ( f [n] < 0) 4 f [n]= F(n－1)+ F(n－2); 5 return f [n]; 6 } 7 integer Fib(n) { 8 f [0] = 0; f [1] = 1; 9 for (i = 2; i ≤ n; i = i + 1) 10 f [i]=－1; 11 return F(n); 12 }其中資料型態 integer 表示整數。假設輸入的整數 n>1。主程式執行Fib(n)，則副程式 F(n)第 4 行之指令：f [n]= F(n－1)+ F(n－2)會被執行幾次？請說明理由。 （20 分）
（20 分）
參考架構・破題
本題是帶備忘錄（memoization）的費氏數計算。f[i] = -1 表示尚未計算，每個 F(k)（2 ≤ k ≤ n）只在第一次被呼叫時執行第 4 行，之後直接回傳，所以第 4 行恰執行 n-1 次。
完整答題架構與關鍵字：到站內看全文
106 年（考試時間 120 分鐘） 原卷 PDF
- 1
給定一個以一維陣列 A[i]所表示的二元樹（binary tree）如下：（每小題 5 分，共 30 分）i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A[i] T S U B O G P X
（一）請問該樹樹高為何？
（二）請列舉該樹所有葉節點（leaf node）。
（三）A[i]所代表的節點之左子節點（left-child node）應在陣列 A[.]的那一個位置？請寫出公式。
（四）請寫出該樹之後序遍歷（Postorder Traversal）結果。
（五）請寫出該樹之前序遍歷（Preorder Traversal）結果。
（六）請寫出該樹之中序遍歷（Inorder Traversal）結果。
（30 分）
- 2
下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下（average，搜尋（search）case） 、插入（insertion）、刪除（deletion）資料之時間複雜度。陣列的各項資料已事先填入作為範例。 （每小題 5 分，共 20 分）搜尋 插入 刪除（search） （insertion） （deletion）陣列 O(n) O(n) O(n)
（一）佇列（queue）
（二）雙向連結串列（doubly-linked list）
（三）二元搜尋樹（binary search tree）
（四）AVL樹（AVL tree）全一張（背面）等 別：三等考試
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 3
給定如下圖所示之兩個環狀單向鏈結串列（circular singly linked list），並以 A，B 分別指向其中兩個串列中的一個節點，另有一個指標 C 可以使用。請用類 C 之虛擬語言（C-like pseudo code）完成下列動作。A C link link link ... link B link link link ... link
（一）請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分）
（二）請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10 分）
（三）請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15 分）
（30 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
給定下列數列，若以快速排序法（Quick Sort）、選擇排序法（Selection Sort）、堆積排序法（Heap Sort）、泡沫排序法（Bubble Sort）進行排序。請問下列數列是那一個排序法排序過程的暫時結果，並說明之。 （每小題 5 分，共 20 分）75 93 32 81 75 89 89 99 25 78 54 75 87 12 75 28
（一） 99 93 89 81 78 87 89 75 25 75 54 75 32 12 75 28
（二） 25 28 32 75 12 75 54 75 99 78 89 89 87 75 81 93
（三） 12 25 28 32 54 75 75 75 75 78 81 87 89 99 93 89
（四） 32 75 75 81 89 25 78 54 75 87 12 75 28 89 93 99
（20 分）
參考架構・破題
本題要從中間結果辨認排序法，關鍵是每種演算法的特徵：堆積排序先建最大堆積、快速排序以基準值切成兩半、選擇排序前段已是最終位置、泡沫排序後段累積最大值。逐一比對原數列與暫時結果，說明符合哪個特徵。
完整答題架構與關鍵字：到站內看全文
105 年（考試時間 120 分鐘） 原卷 PDF
- 1
請回答下列問題：
（一）畫出 AVL 平衡二元樹，其中序（inorder）拜訪為 1、2、3、4、5 任三種。（24 分）
（二）請問共有多少種 AVL 平衡二元樹，其中序拜訪為 1、2、3、4、5？（6 分）
（30 分）
參考架構・破題
AVL 樹是每個節點左右子樹高度差（平衡因子）不超過 1 的二元搜尋樹；中序為 1～5 代表五個鍵值固定，題目實際問的是「5 個節點的高度平衡二元樹有幾種形狀」，以根節點分類列舉即可。
完整答題架構與關鍵字：到站內看全文
- 2
分別給定矩陣 A、B、C 與 D 的大小為 2×4、4×3、3×5 和 5×1：（每小題 5 分，共 15 分）
（一）共有幾種加括號的方法？
（二）例如(AB)(CD)，共需多少次乘法？
（三）求出三者乘積之最有效的方式為何？
（15 分）
參考架構・破題
這是矩陣連乘（Matrix Chain Multiplication）問題：括號方式數由卡塔蘭數決定，成本以 p×q 乘 q×r 需 p·q·r 次純量乘法計算，最佳順序用動態規劃求得。
完整答題架構與關鍵字：到站內看全文
- 3
試針對下列無向網路圖形（Undirected Network Graph）N(V,E,C),V={1,2,3,4,5,6},N={(1,2,6),(1,5,19),(1,6,21),(2,3,5),(2,4,16),(2,5,11), (3,4,10),(4,5,8),(4,6,9),(5,6,7)}，成本 C(1,2)=6, C(1,5)=19…等，求最小成本擴張樹（minimal cost spanning tree）的最小成本。 （10 分）
（10 分）
- 4
有一浮點數三維陣列（three dimensional array）float A [6] [7] [10]；假設 sizeof(float)＝4：
（一）請問此陣列共佔多少位元組？（10 分）
（二）若 A[0][0][0] 在記憶體中的位址為 03C416，則元素 A[5] [2] [9] 的位址為何？（15 分）
（25 分）
參考架構・破題
三維陣列的大小為各維度乘積乘以元素大小；位址計算要先講清楚 C 語言採列主序（row-major），再以位移量乘元素大小加上起始位址，最後換回十六進位。
完整答題架構與關鍵字：到站內看全文
- 5
二項式係數（Binomial Coefficient）的計算公式如下：⎛n⎞ n! ⎛ n − 1⎞ ⎛ n − 1 ⎞ ⎜⎜ ⎟⎟ = = ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ ⎝ m ⎠ m!(n − m)! ⎝ m ⎠ ⎝ m − 1⎠ ⎧ 1, if m = 0 or m = n Bino (n, m) = ⎨ ⎩Bino (n − 1, m) + Bino (n − 1, m − 1) ; otherwise
（一）求 Bino(5,3)的值？（5 分）
（二）求 Bino(5,3)時，共呼叫 Bino 此函數多少次？（5 分）
（三）當 n, m∈ N 且 n ≥ m ≥ 0 求 Bino(n, m)時，共呼叫 Bino 函數 T(n, m)次，求 T(n, m) =？（10 分）
（20 分）
104 年（考試時間 120 分鐘） 原卷 PDF
- 1
二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法技巧，對一個已排序（sorted）且長度為 n 的陣列 A[0:n−1]，進行資料搜尋，其最差時間複雜度（worst case time complexity）可降到 Θ(log n)。
（一）請使用 C 或 Java 語言，修改此二元搜尋法，使其能對未排序（unsorted）且長度為n 的陣列 A[0:n−1]，以 divide-and-conquer 技巧，進行二元化搜尋。（15 分）
（二）請分析修改後的二元搜尋法其最差時間複雜度（worst case time complexity）以 order Θ的方式表示。 （5 分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法）
（20 分）
- 2
請使用 C 或 Java 語言寫一副程式 void merge(int [] A, int [] B, int [] C, int n)，此副程式將對兩個長度為 n 且已依小到大排序的整數陣列 A 與 B，合併至長度為 2n 且依小到大排序的整數陣列 C，此副程式的時間複雜度需為 Θ(n)。（20 分）（注意：請加註解說明程式碼作法）
（20 分）
- 3
（一）請說明使用何種資料結構及其演算法，可有效判斷一運算式（expression）中的巢狀（nested）括號是否正確配對（matched）。 （10 分）
（二）請以兩個運算式實例{A*[B−(C+D)+8]−16}及{A+[B−(C+5])}，分別說明此演算法判斷的過程及結果。（10 分）（注意：未說明判斷的過程，不予計分）
（20 分）
參考架構・破題
括號配對是堆疊（stack）的經典應用：利用後進先出特性，最晚出現的左括號必須最先被配對；第（二）小題必須逐字元列出堆疊變化，題目明言未說明過程不給分。
完整答題架構與關鍵字：到站內看全文
- 4
（一）一運算式（expression）為：–a+(z+f)/y–b*a/c+d，請依運算元優先順序，繪出其二元樹（binary tree）。（10 分）
（二）請列出此二元樹的前序走訪（preorder traversal）。 （5 分）
（三）請列出此二元樹的廣度優先走訪（breadth-first search traversal）。（5 分）
（20 分）
- 5
一個圖形（Graph）包含五個頂點（vertex） ，V 1 , V 2 , …, V 5，其相鄰矩陣（adjacency ⎡ 0 3 1 ∞ ∞⎤ ⎢3 0 1 7 6⎥ ⎢ ⎥ matrix）A= ⎢ 1 1 0 5 2 ⎥ 。⎢ ⎥ ⎢ ∞ 1 5 0 4 ⎥ ⎢⎣∞ 6 2 4 0 ⎥⎦
（一）請使用 Floyd 的方法，計算此圖形的最短路徑長度矩陣（shortest path length matrix） ，表示任兩頂點間最短路徑長度。請依序列出最短路徑長度矩陣變化過程。 （15 分）
（二）請使用 Kruskal 的方法，依序繪出加入此圖形的最小成本擴張樹（minimum cost spanning tree）每一邊的過程。 （5 分）
（20 分）
參考架構・破題
Floyd 演算法以動態規劃逐一允許頂點 k 當中繼點，更新 D(k)[i][j]＝min(D(k-1)[i][j], D(k-1)[i][k]＋D(k-1)[k][j])；Kruskal 則依邊權由小到大選邊、避開迴路。題目要求列出變化過程，D(0)～D(5) 都要寫。
完整答題架構與關鍵字：到站內看全文
103 年（考試時間 120 分鐘） 原卷 PDF
- 1
給定一個權重圖（weighted graph）G(V, E) 如下圖所示。請用 Kruskal 演算法找出最小生成樹 MST(G) (minimum spanning tree)。請依序寫出加入此最小生成樹的每一個邊。（5 分）請用 Prim 演算法找出最小生成樹 MST(G)。若以 A 為起始點，請依序寫出加入此最小生成樹的每一個邊。（5 分）假設最小生成樹 MST(G) 已知。若在原圖 G(V, E) 中加入一個新的邊 vi - vj 且其權重為 w。請設計一個 O(V) 的演算法，從已知的 MST(G) 中快速找出新圖的最小生成樹。請以文字敘述說明。（10 分）請說明上一小題 的演算法為 O(V)。（5 分）B 30 A 35 19 I 32 23 16 14 21 64 D 20 C 26 F H 24 15 25 E
（25 分）
本題含圖表或公式，請對照原卷 PDF。
- 2
給定一個二元樹T。若T之後序巡行（postorder traversal）結果是P D J M O A I H K G L N E B C，而中序巡行（inorder traversal）結果是 J D P I A M O C K H G B E L N：請畫出該二元樹 T。（10 分）請寫出該二元樹之前序巡行（preorder traversal）結果。（10 分）全一張（背面）等 別： 三等考試
（20 分）
- 3
請用 Dijkstra 演算法找出下圖中從 S 到 T 的最短路徑長度：請依序寫出過程中逐一加入已被選擇的頂點（vertex），起始頂點為 S。（10 分）請問以此演算法所找出的 S 到 T 最短路徑長度為何？（5 分）G 3 6 T 1 D L 1 4 F 3 3 3 4 1 H 2 7 K B 4 E 5 5 6 M 1 6 5 5 C S 5 A
（15 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
給定一個陣列（array） A[0], A[1],…, A[99] 用以表示一個循環佇列（circular queue）。另外再以兩個整數變數 front 及 back 記錄該循環佇列之前端（front of the queue）及尾端（back of the queue）。一個尚未有任何資料的循環佇列之 front = back = -1：若要新增加一筆資料於此循環佇列，front 及 back 變數該如何改變？（5 分）若要從循環佇列中取出並刪除一筆資料，front 及 back 變數該如何改變？（5 分）此循環佇列最多可以儲存幾筆資料？（5 分）若此循環佇列已經全滿，在未刪除任何資料前已不能再儲存新資料，請問此時front 及 back 的關連為何？（5 分）
（20 分）
參考架構・破題
本題的循環佇列以 front＝back＝-1 表示空佇列，屬於「front 指向第一筆、back 指向最後一筆」的設計，能用滿 100 格；作答時先講清楚指標意義，再分別說明加入、刪除、容量與全滿條件。
完整答題架構與關鍵字：到站內看全文
- 5
給定下列尚未排序之數列：80, 24, 11, 47, 19, 91, 2, 32, 85, 7, 16, 36, 99, 52, 41，請以泡沫排序法（bubble sort）及快速排序法（quick sort）分別將該數列由小到大排序：請依序寫出泡沫排序法前五回合的排序結果。（10 分）請依序寫出快速排序法前五回合的排序結果，每一回合用一個樞紐（pivot），並把每一回合所用的樞紐圈起來。（10 分）
（20 分）
參考架構・破題
本題考兩種交換式排序的逐回合追蹤。重點不是最後的排序結果，而是每一回合結束時整個陣列長什麼樣子。先講明採用的版本（泡沫排序由左往右比較、每回合把最大值推到最右；快速排序以子陣列第一個元素為樞紐），再逐回合列出結果。
完整答題架構與關鍵字：到站內看全文
102 年（考試時間 120 分鐘） 原卷 PDF
- 1
請參考圖 1：
（一）由 a 點出發，做 depth-first traversal（深度優先拜訪），請問那些節點（node）不會被訪問到？（3 分）
（二）由 a 點出發，做 breadth-first traversal（寬度優先拜訪），請問那些節點（node）不會被訪問到？（2 分）
（三）假設圖 1 代表 heap 上各個節點（node）及其相互指向的關係。p、q、r 三節點代表全域變數（global variables），其他的節點代表 heap 上的記憶體區塊。如果p→a 的指標被消除，那些節點會變成無用的垃圾節點？你必須詳細描述尋找垃圾節點的方法及所需之資料結構。你的演算法只能從 a 節點出發，它必須指出所有的垃圾節點，並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演算法必須在每一個節點儲存那些資料？（15 分）d e f h b p a g c j r x k l m n q圖 1 一個有向圖（a directed graph）
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 2
定義如下的函數 F：如果 x 是偶數，則 F(x) = x/2;否則 F(x) = F(F(3x + 1))
（一）請問 F(11) =？（5 分）
（二）請證明對於任何正整數 w，我們都可以在有限時間內計算 F(w)。（提示：每個奇數可以寫成(2i + 1)2k – 1 的形式，再採用數學歸納法來證明。）（15 分）（請接第二頁）全三頁第二頁等 別： 三等考試類 科： 資訊處理
（20 分）
參考架構・破題
這是一個遞迴定義中又套遞迴（F(F(3x+1))）的函數，第一小題直接展開計算，第二小題要證明遞迴必定終止。關鍵是依提示把奇數寫成 (2i+1)·2^k − 1，觀察每次奇數步驟會讓 k 減 1，以 k 做數學歸納法。
完整答題架構與關鍵字：到站內看全文
- 3
Knuth，Morris 及 Pratt 發明了一個快速的字串比對方法（string pattern matching）。他們的方法採用一個失敗函數（failure function）。失敗函數其實就是一個輔助的資料結構，用來加速比對。請依他們的方法計算下列字串的失敗函數。你必須說明失敗函數的定義為何，以及失敗函數如何加速比對。（15 分）index 0 1 2 3 4 5 6 7 8 9 pattern a b b a b c a b b a failure ？ ？ ？ ？ ？ ？ ？ ？ ？ ？
（15 分）
本題含圖表或公式，請對照原卷 PDF。
- 4
請參考圖 2。每一條線段上的數字代表兩節點間的距離。請找出 a 節點到 k 節點的最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。（15 分）14 c b 16 11 10 41 d 49 a 4 21 k 23 e 5 3 7 12 35 17 f 26 13 h g圖 2 最短路徑
（15 分）
本題含圖表或公式，請對照原卷 PDF。
- 5
請參考圖 3。圖 3 是一個 activity-on-edge 網路。在 activity-on-edge 網路中，一項計畫可以分成很多件工作，每一件工作由一條線段代表，線段上的數字代表該工作所需的時間（以工作日為單位），線段的箭頭代表工作的先後關係。例如在圖 3 中，ab 及 db 線段代表的工作完成之後，bc、be、及 bf 線段代表的工作才可以開始進行，其他的先後關係依此類推。a 節點是起點，k 節點是全部工作的完成點。請找出 k節點的最早完成時間及關鍵路線（critical path）。並請說明你的方法如何應用在非常大型的圖裡。（15 分）11 c b 22 11 21 27 23 14 19 a d 21 k 13 e 5 3 12 7 12 21 23 g f h圖 3 Activity-on-edge 網路（請接第三頁）全三頁第三頁等 別： 三等考試類 科： 資訊處理 六、在一個二元樹裡有許多節點（nodes）。假設每一個節點的資料結構如下圖：LEFT DATA RIGHT其中 DATA 欄位為該節點的資料。LEFT 欄位為指向左方子樹的指標變數。RIGHT 欄位為指向右方子樹的指標變數。如果節點 p 沒有左方子樹，其 LEFT 欄位為空指標（null pointer）。同理，如果節點 p 沒有右方子樹，其 RIGHT 欄位為空指標（null pointer）。
（一）如果一個二元樹有 n 個節點，那麼它有幾個空指標？（5 分）
（二）我們可以利用原本是空指標的欄位來儲存引線（threads）。二元樹加上引線的結果稱為引線樹（threaded trees）。當然我們必須在各節點再加上兩個欄位 LTAG及 RTAG，共 5 個欄位，如下圖所示：LTAG LEFT DATA RIGHT RTAG如果 LEFT 欄位代表一般的節點指標，則 LTAG = 0。如果 LEFT 欄位代表引線指標，則 LTAG = 1。同理，如果 RIGHT 欄位代表一般的節點指標，則 RTAG = 0。如果RIGHT 欄位代表引線指標，則 RTAG = 1。請將下圖的二元樹加上適當的引線指標，讓它變成引線樹，並請繪圖標出 A 到 I 共9 個節點中所有引線指標指向的節點。（10 分）A B C D E F G H I
（30 分）
本題含圖表或公式，請對照原卷 PDF。
其他等別的「資料結構」
- 資料結構（高考三級）（64 題）
題目來源：考選部考畢試題查詢平臺（政府資訊公開資料）；參考架構為本站自撰，僅供準備方向參考，非官方標準答案。最後更新：。