資料結構考古題｜歷屆國考試題彙整

某系統A 使用雜湊表（hash table）儲存不同的正整數鍵值，亦即不允許重 複鍵值，雜湊表有11 個儲存格，索引從0 開始，雜湊函數（hash function） 為 ( ) 11 A h k k mod  ，其用平方探查法（quadraticprobing）處理碰撞（collision） 問題，探查序列為

( ) ( ( ) ) 11( 0,1,2,...) A A ih k h k i mod i    ，刪除資料時， 被刪除資料的位置標記為特殊符號DELETED。請回答下列問題： 給定一個空的雜湊表，依序插入下列鍵值22、1、13、24、35、46、7、 18，請畫出所有鍵值插入完成後的雜湊表狀態，並列出插入鍵值46 時 的完整探查過程。（10 分） 承上題，依序刪除鍵值24、13，畫出刪除後的雜湊表狀態。並說明為 什麼刪除鍵值時需用DELETED 標記，而不能將該鍵值所在的儲存格 恢復成「從未存放過鍵值」的空狀態。（5 分） 承上題，執行插入鍵值12，請列出插入時的探查過程、操作停止的理 由，並寫出12 最後插入那一個儲存格。插入時，DELETED 標記視為 可放入新鍵值的儲存格。請注意鍵值不能重覆。（5 分） 相較於系統A，考慮另一個採用平方探查法之系統，系統B 的表格大小 為8，索引亦從0 開始，雜湊函數 ( ) B h k 及探查序列 ( ) B ih k 分別定義為 ( ) 8 B h k k mod  、 2 ( ) ( ( ) 2 ) 8 ( 0,1,2,...) B B ih k h k i i mod i     。在非均 勻雜湊（non-uniform hashing）的情況下，也就是許多鍵值可能被分配 到相同或少數幾個初始雜湊位置時，那一個系統的雜湊表儲存格利用 率可能較高？並說明理由。（5 分） 二、給定一個無向圖G (V, E)  ，每個頂點代表一個地點，每條邊( E) e e 代 表一條道路，邊的正整數權重( )e  表示該道路的塞車程度，數值越大越 壅塞。對於一條從起點s 到終點( , V) t s t  的路徑P，其最大塞車程度C(P) 定義為路徑上所有邊權重的最大值： C(P) max ( ) e P e    本題透過修改Dijkstra 最短路徑演算法中陣列d 的定義與更新方式，求出 從s 到t 可行路徑所能達到的「最大塞車程度的最小值」。修改後的演算法 流程與Dijkstra 最短路徑演算法相同，差異僅在於 ( ) [ ] V d v v 的定義與更新 規則，其中，新的[ ] d v 表示目前已知從s 到v 的路徑中，最大邊權重的最 小值。初始時令[ ] 0 d s ，其他頂點v 的 ) [ ( ] d v v s   。之後依照Dijkstra 演算法，每一輪選出尚未被選定且d 值最小的頂點u，並將原本的更新方 式[ ] min [ ], ) ] ( [ ( , ) d v d v d u u v    改為[ ] min [ ], ma ) x [ ] , ) ( ( ( ) , d v d v d u u v   ， 其中( , ) u v  為邊( ) ( ) , , V u v u v 的權重。重複進行，直到終點t 被選定為止。 以下列無向圖為例，令起點s 為A，終點t 為F，依照修改後的演算 法，逐步列出每次選定一個頂點後陣列d 的變化過程。陣列中的頂點 順序請依字母順序排列。（15 分） 說明修改後演算法之正確性，是基於[ ] d v 更新規則具有何種性質。（5 分） 假設圖以相鄰串列（adjacency list）表示。若要在尚未選定的頂點中找 出d 值最小者，可使用以下兩種方法： 方法一：每次以線性方式掃描所有尚未選定的頂點找出最小d 值。 方法二：使用最小堆積（min-heap）維護目前d 值最小的頂點。 分別就這兩種方法，分析修改後演算法最壞情況的時間複雜度。（5 分）

給定一棵二元搜尋樹（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 分）

(1)　(2)　(3)　(4) 5 分

考慮以下兩個互相呼叫（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 分）

(10)　(10) 10 分　(10) 10 分

費伯納西數列（Fibonacci Sequence）定義如下：F(0) = 0，F(1) = 1， F(n) = F(n-1) + F(n-2)，n≥2。請完成下列各題： 使用遞迴方法（Recursion）撰寫虛擬碼，計算第n 項的費伯納西數。 （8 分） 使用動態規劃方法（Dynamic Programming）撰寫虛擬碼，透過自底向 上（Bottom-up）的方式計算第n 項的費伯納西數。（8 分） 比較兩個方法的時間複雜度（Time Complexity）。（6 分）

(0)　(1) 8 分

一棵空的階數為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 分)

給予一前序（preorder）表示式ABCD 和後序（postorder）表示式DCBA， 試畫出所有可能的二元樹。（25 分）

有一個三維整數陣列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 分）

假設每個運算元都是一位整數，使用堆疊方法，模擬後序式2542+6+的 計算過程。（25 分）

已知B+-tree 的階數（Order）為m = 3。葉節點至多可存放2 個鍵值，至 少須存放1 個鍵值；內部節點至多可有3 個子節點，至少須有2 個子節 點。當節點因插入而溢位時，規定葉節點分裂時將右子節點之第一個鍵 值提升至父節點，內部節點分裂時則將中間鍵值提升至父節點。請完成 下列各題： 依序插入17、5、12、23、7、19、3、30 等8 個鍵值以建構B+-tree。 請逐步說明並繪製每次插入後之樹形結構。（12 分） 承接之結果，依序刪除7、23 與5 等三個鍵值。刪除過程中若需借 值時，一律自右兄弟節點借取；若無法借值，則與左兄弟節點合併。 請逐步說明並繪製每次刪除鍵值後之樹形結構。（6 分） 承接之結果，說明在該B+-tree 中搜尋鍵值19 之完整過程，並列出 查找時經過之節點及比較順序。（4 分）

假設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 分）

假設現有五個字母A, B, C, D, E 的頻率分別為0.19, 0.09, 0.21, 0.12, 0.39， 請依步驟建構霍夫曼樹（Huffman Tree）。（25 分）

已知待排序數列如下：36, 45, 59, 81, 72, 64, 36, 27，其中36 與另一個36 數值相同，但以底線標示以便在排序過程中追蹤其相對次序。請完成下 列各題：（每小題6 分，共24 分） 說明何謂穩定排序（Stable Sort），並解釋若演算法不屬於穩定排序， 在處理相同鍵值時會造成什麼影響。 使用選擇排序（Selection Sort）對上述數列進行排序，並逐步描述每次 選擇與交換的過程，最後給出排序後的結果。 使用合併排序（Merge Sort）對上述數列進行排序，並描述拆分與合併 的過程，最後給出排序後的結果。 使用基數排序（Radix Sort）對上述數列進行排序，並描述逐位（個位 數、十位數）的桶排序（Bucket Sort）過程，最後給出排序後的結果。

根據下列的虛擬碼，若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)

19 世紀電報傳輸以訊號數計費。為了降低成本，電報公司決定採用霍夫 曼編碼（Huffman Coding）壓縮電文。假設要傳輸字母TURING，其出 現次數如下：T (15 次)，U (7 次），R (6 次），I (6 次)，N (5 次)，G (5 次)。 在建構過程中，每次取出權重最小的兩個節點合併；若兩者權重相同， 則依字母順序決定先後。請完成下列各題： 依步驟建構霍夫曼樹，並寫出各字母的編碼。（10 分） 比較固定長度編碼（假設每個字母以3 位元表示）與霍夫曼編碼，並 計算壓縮率（需列計算過程）。（6 分）

請逐步寫出下列使用遞迴函式的呼叫與輸出過程。（25 分） #include <iostream> using namespace std; int A(int n, int c = 1) { if (n == 0) return c + 1; return A(n - 2, c * n); } int main() { cout << A(6) << endl; return 0; }

(6)

下列虛擬碼是利用某演算法對陣列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

下圖為一有向圖（Directed Graph）G。請完成下列各題： （每小題4 分，共16 分） 畫出圖G 的相鄰串列（Adjacency List）。 畫出圖G 的相鄰矩陣（Adjacency Matrix）。 從節點a 開始，寫出廣度優先搜尋（Breadth-First Search, BFS）的節點 拜訪順序。 從節點a 開始，寫出深度優先搜尋（Depth-First Search, DFS）的節點 拜訪順序。

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 -- -- -- 四、一個自動化工廠大量採用機器人協助裝箱作業。該工廠固定時間生產出 一組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 個機器人， 整組球順序排好的速度可以加快多少？請說明。

(1) 5 分　(1) 10 分

資料結構中的二元樹（binary tree）依其走訪節點的順序可以得出不同的 運算表示式。給予一中序（inorder）表示式FBACEIGJH 和後序（postorder） 表示式BCAFIHJGE，請說明並畫出其對應的二元樹。有一後序表示式 36 12 / 10 23 - * 50 40 - +（此運算式中的數值均為二位 數），利用堆疊運算其結果為何？（請勿只寫出最後結果，需詳細寫出堆 疊內每一步的變化並說明）。（20 分）

若有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

一串含有8 個整數的資料：48, 55, 10, 88, 26, 80, 35, 40，請以第一個數值 為樞紐（pivot）進行快速排序法（quick sort），將這些資料由小排到大， 並寫出詳細的比較過程。（20 分）

快速排序法（Quick Sort）最壞的情況下所需的時間複雜度（Time Complexity）為O(n2)，請說明是在何種情況下造成？（10 分） 請列出其最壞的時間複雜度為O(n2)的推導過程。（15 分）

有一棵高度平衡二元搜尋樹（balanced binary search tree）又稱AVL 樹 （Adelson-Velskii Landis tree）如下圖，加入90，請詳細說明該如何調整 成一棵AVL 樹？接著再加入85，請詳細說明該如何調整成一棵AVL 樹？ 接著再刪除15，該如何調整成一棵AVL 樹？請將最後調整後的AVL 樹 中每個節點之平衡因子（balance factor）寫在節點旁邊。（25 分） 30 80 25 60 15

請使用虛擬碼（Pseudo Code）或任何程式語言，完成下列問題： 撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分） 推導二元搜尋的時間複雜度（Time Complexity）。（5 分）

有一棵二元樹（binary tree）利用一維陣列來存放其節點，假設樹根（root） 存放在索引（index）為1 的位置，若有一節點i 存放在索引為1024 的位 置，請問該節點i 的父節點存於陣列的那個位置，其索引為何？若節點i 有 一右子節點j，請問節點j 存於陣列的那個位置，其索引為何？用一維陣 列存放二元樹，最浪費陣列空間的二元樹是那一種？請畫出並詳細說明。 （15 分）

堆疊（Stack）與佇列（Queue）是常見的資料結構，請回答下列問題： 利用雙向佇列（Deque）循序輸入1, 2, 3, 4, 5, 6, 7，請問能否得到 5174236 的輸出排列？並說明其過程或理由。（10 分） 若有1, 2, 3, 4 四個數字要依序Push 進堆疊，再於任意時間點Pop 出 堆疊，請列出可能的輸出組合。（15 分）

給定一個以相鄰矩陣（adjacency matrix）表示的一無方向圖如下表，∞表 示沒有邊（edge）相鄰。請畫出對應的圖形，每個邊和其對應的權值必須 列出。另外請使用Kruskal’s 演算法計算權重最小的生成樹（minimum spanning tree），並詳細列出該生成樹的形成過程。（20 分） a b c d e f g a ∞ 13 9 10 ∞ ∞ ∞ b 13 ∞ ∞ 16 ∞ ∞ ∞ c 9 ∞ ∞ 12 2 3 ∞ d 10 16 12 ∞ ∞ ∞ 18 e ∞ ∞ 2 ∞ ∞ 4 ∞ f ∞ ∞ 3 ∞ 4 ∞

g ∞ ∞ ∞ 18 ∞ 6 ∞

假設有一宣告為float A[18][10]的浮點數陣列（假設Sizeof(float) = 4 Bytes）： （每小題5 分，共15 分） 此陣列共占多少位元組（Bytes）？ 若A[0][0]在記憶體的位址為(03C4)16，則元素A[5][3]的位址為何？ 若A[16][2]在記憶體的位址為(10E9)16，則元素A[5][3]的位址為何？

某一公司有下圖所示的8個優先順序分別為高或低的待執行工作，且將依 順序自A至H每間隔一天的時間放入對應的高優先執行佇列（Queue）或低 優先執行佇列（Queue），例如A（低）表示A工作將於第一天放入低優先 執行佇列，而C（高）表示C工作將於第三天放入高優先執行佇列。此外， 執行每個工作所需完成的時間均於工作名稱下顯示，例如執行A工作需要 2天時間完成，而執行B工作需要1天時間完成。最後，各個工作的執行規 則為，當高優先執行佇列內有工作待完成時，須優先執行該佇列內的工作 （由第一個開始執行），直到高優先執行佇列內沒有任何待完成工作時， 方可執行低優先執行佇列內的工作（由第一個開始執行）。 自A至H每間隔一天的時間放入對應的高優先佇列或低優先佇列 H（低） G（高） F（高） E（低） D（高） C（高） B（低） A（低） 1

將中序運算式轉換成後序運算式演算法常使用堆疊資料結構，如相同 問題，改成使用二元樹資料結構來儲存一中序運算式，以中序運算式 A/B－C+D＊E－A＊C 為例，畫出表示此中序運算式的二元樹，並依前 序（Preorder）與後序（Postorder）列出拜訪（Visit）此二元樹的順序。 （25 分）

請將下列表示式轉成後序（Postfix）（5 分） (A + B)× (C ^ (D − E) + F) – G 請將下列表示式轉成中序（Infix）（5 分） AB + D ∗EBA //+ AD ∗C /+ CD ∗ +A − B + CD ∗ −

1 1 2 2 1 2 試計算執行此8個工作需要多少天方可完成。（10分） 試計算此8個工作自放入佇列至開始執行的平均等待時間。（15分） 二、某一物流公司有下圖所示的8個地點要運送，每條方向性連線及其數字代 表兩個地點的運送順序及運送成本。 試使用拓樸排序法，找出此8個地點的運送順序以及總共運送成本。（15分） 若將上圖的地點2與地點4之間以及地點6與地點7之間的連線方向顛 倒，則運用拓樸排序法後，此8個地點的運送順序以及總共運送成本 為何？（10分）

用G = (V, E)表示一個無方向性圖形，其中V 是點的集合，E 是一組節點 （Vertices）形成邊的集合。今有一圖形G = (V, E)，V(G) = {T, W, X, Y, Z}, E(G) = {(T, W),(T, Y),(T, Z),(W, X),(W, Z),(X, Z)}，每一個邊對應的權重值 分別為2, 1, 7, 4, 3, 6，請用相鄰矩陣（Adjacency Matrix）與相鄰串列 （Adjacency List）表示此圖形，並使用Prim’s 演算法，計算最小成本擴張 樹（Minimum Cost Spanning Tree），依序寫出從點X 加入邊的順序，最小 成本擴張樹的權重總和為何？（25 分）

給予一串資料60, 70, 50, 10, 20, 80, 95, 90，依序畫出產生2-3 樹（Order 3 的B-Tree）的過程，之後依序畫出刪除50、20 與80 的2-3 樹。（25 分）

下圖為一棵二元搜尋樹（Binary Search Tree），若要刪除節點48，在維持 最小變動的狀況下，但仍需維持一棵二元搜尋樹，請畫出所有可能的二 元搜尋樹。（20 分） 2 11 8 3 5

在電腦網路中，透過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分）

給予如下程式片段，假設x[] = [25, 57, 48, 37, 12, 92, 86, 33]，請只用下述 C 語言宣告的變數及兩個for 迴圈，完成下面的選擇排序（Selection Sort）， 假設有n 個資料要由小排到大，每一外迴圈將最大值放在第n-1 個位置， 然後第二大的資料放在第n-2 個位置，依此類推，將資料放到適當的位置， 執行後陣列x[]內容由小排至大。（25 分） Selectsort(x, n) int x[], n; { int i, index, j, large; for (i = n－1; i > 0; i－－){ for (j = 1; j <= i; j++){ } } }

6 4 9 2 四、若將下圖當作樹，請分別用陣列與鏈結串列（Linked List）的方式來表 示。（20 分）

某一系統有下表所示的使用者帳號與密碼資料，今為了保密需要欲將使 用者密碼透過雜湊函數加以加密，並將雜湊後的密碼連同使用者帳號儲 存於一個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分）

請完成下列表格有關排序演算法的time complexity（假設排序資料有n 個，資料位數有d 個）、是否為In−Space 演算法、是否為Stable 演算法 及範例數列50, 46, 37, 28, 19 進行降冪排列時所需的比較次數。（30 分） 排序演算法 Time Complexity In−Space （Yes/No） Stable （Yes/No） 降冪比較次數 Best Worst 50, 46, 37, 28, 19 Bubble Insertion Merge（奇數時， 後半段多1） Quick（第一個當 pivot） Radix（base 10） Selection

請使用Prim 演算法找出下圖的最小生成樹（Minimum Spanning Tree）， 起始點為節點a，請將搜尋結果畫出來。（15 分）

假定一個整數序列：3, 12, 11, 13, 10, 8, 1, 4, 9, 15, 2, 6, 7, 14, 5, 16，請使 用合併排序（Merge Sort）從小到大進行排序及整理，並且一步步寫出過 程。（20 分） 3 a b c f e d

請回答下列Big O 的相關問題： Big O Notation，根據維基百科又稱為漸進符號，它是用於描述演算法漸 進行為的數學符號。更確切地說，它用更簡單的函式來描述一個演算法在 數量上的漸進趨勢。某個問題可採用5 個演算法A～E 求解，各演算法執 行時間的Big O 分別如下：A 為O（N2），B 為O（Nlog（log N）），C 為O（N1.5），D 為O（N2log（N）），E 為O（SQRT（N））。當N 很 大時，請根據演算法的執行時間，由慢至快排序這5 個演算法。（10 分） 給定100 萬個介於0 到100（含0 及100）的整數，請利用任一種高階 程式語言寫出一個O（N）的由大至小的排序演算法，並說明此演算法 為何是O（N）的方法。（15 分）

以下是一中序運算式（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 (

以下7 個數字[21, 1, 16, 11, 25, 9, 35]，要儲存到Hash Table 中，Hash Table 的儲存空間是一個索引從0 開始的一維陣列（Array）。假設Hash 函數為 H（Key）=（Key * 3）mod 7，裝填因子（Load Factor）為0.7。 若處理Hash Table 衝突的方法為開放定址法（Open Addressing Hashing） 中的線性探測法（Linear Probing）：增量函數F（i）= i（i 為衝突的次 數）。請依序列出每存入一個數字後的Hash Table 的內容。接著計算在 相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length; ASL）。（15 分） 若處理Hash Table 衝突的方法為開放定址法（Open Addressing Hashing） 中的平方探測法（Quadratic Probing）：增量函數F（i）= i2（i 為衝突 的次數）。請依序列出每存入一個數字後的Hash Table 的內容。接著計 算在相同機率的情況下，查找成功及查找失敗的平均查找長度（Average Search Length; ASL）。（15 分）

+

請寫出對以下8 個數字[44, 62, 31, 5, 82, 49, 16, 7]，依序建構最小堆積樹 （Min Heap Tree）的過程。為方便最小堆積樹的建構，我們通常會使用一 個一維陣列來儲存堆積樹中的數字。請說明如何用一維陣列來處理最小堆 積樹的建構。最小堆積樹建構完成後，請寫出如何用此樹依序將數字由小 到大的排序過程。請說明此種排序法的計算複雜度Big O 為何？（25 分）

) *

下圖中有4 個城市8 條公路，公路上的數字表示這條公路的長短。請注意 這些公路是單向的。若使用Floyd Warshall 的動態規劃法求解從任意兩個 城市之間的最短路徑，請回答下列問題： 首先將圖的信息建成一個N*N 的初始距離矩陣，其中N 是節點的個 數，矩陣的各列（Rows）代表From Nodes，矩陣的各行（Columns） 代表To Nodes，矩陣中的值則分別代表上圖中從From Node 到To Node 的距離。（5 分） 其次列舉從D 到C 的最短路徑求解過程（需輸出最短路徑的值及路徑）， 並說明此方法的計算複雜度Big O 為何。（15 分）

eos 二、利用鏈結串列（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; } 三、一個二元搜尋樹（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){ } 四、用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 分）

下圖是一個加權圖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 分）

利潤 40 15 60 20 45 10 55 最後期限 2 4 3 2 1 3 1 以文本（text）X=“AGTCATTCGATTC”，樣式（pattern）Y=“ATTC”兩字 串為例，請問使用暴力比較/窮舉法（exhaustive search）中的樣式前向法 （forward）及後向法（backward）各需比較幾次？（10 分） m,n N   ,已知三維陣列（three-dimensional array）A[1：8, 1：9, 1：4]每一 個元素占用2 個儲存單元，並且A[1,2,1]的儲存地址為234，A[2,3,1]的儲 存地址是m，A[2,3,4]的儲存地址為n。 採用列序為主序（row major）方式儲存，則m、n 分別為何？（10 分） 採用行序為主序（column major）方式儲存，則m、n 分別為何？（10 分）

A 為（8×4）矩陣、B 為（4×10）矩陣、C 為（10×3）矩陣、D 為（3×20） 矩陣、E 為（20×4）矩陣，請列出此5 個矩陣相乘ABCDE 所有 可能的乘法順序（請用括號表示乘法順序）。（5 分）請使用Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘ABCDE 的 最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費 的乘法數量最少。（15 分）請列出此五個矩陣相乘所需要花費的最少 乘法數量。（5 分）（注意：未說明Dynamic Programming 的計算過程， 不予計分。）

大學生只剩5 天準備4 科X1, X2, X3, X4，估計的成績點數如下表所示，每 1 科準備至少1 天，使用窮舉法（exhaustive search）有幾種可能？如何最 適化？最適成績s =？（20 分） 天數 科目 X1 X2 X3 X4 1（天） 3 5

請試述下列名詞之意涵：（每小題5 分，共20 分） B+ 樹（B+ Tree） 完美雜湊函數（Perfect Hash Function） 霍夫曼編碼（Huffman Coding） 拓撲排序（Topology Sort）

假設收銀機內銅板的集合S={$50, $20, $20, $15, $10, $2, $1, $1, $1}，而 預計找錢給顧客的金額W=$75。請設計一個Greedy（貪婪）的演算 法，來解決找錢給顧客的問題，使得找給顧客金額W 所使用的銅板數量 最少，並依此Greedy 的演算法列出找給顧客金額W=$75 的過程。（15 分） 此Greedy 演算法適合使用何種資料結構來完成。（5 分）此Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5 分）

4 2 5 6 4 4

給定一個環狀鏈結串列，節點資料結構宣告如下： struct node { char info; struct node *next; }; typedef struct node NODE; 請用C 語言或類似虛擬語言（pseudo code）寫出void swapnodes（NODE *p）函式將兩個指定節點位置交換，過程中不能更動節點內info 內容， 僅能修改節點內next 指標，且兩個節點交換後仍保持環狀鏈結串列。 將指標p 之後面連續兩個節點位置交換，如下圖所示。（15 分） A p 交換節點前 infonext B C D E A p 交換節點後 infonext B D C E 將指標p 之前後節點位置交換，如下圖所示。（15 分） A p 交換節點前 infonext B C D E A p 交換節點後 infonext D C B E

二元搜尋法（binary search）使用divide-and-conquer（分而治之）演算法 技巧，對一個已排序的（sorted）且長度為n 的陣列A[0:n1]，以二元化 方式進行資料值x 的搜尋，其最差時間複雜度（worst case time complexity）可降到(log n)。請使用C++或Python 語言，修改此二元 搜尋法，使其能對未排序的（unsorted）且長度為n 的陣列A[0:n1]，進 行三元化搜尋，即以divide-and-conquer 技巧將此陣列切成三個子陣列， 並在可能包含資料值x 的子陣列繼續進行divide-and-conquer 技巧的搜 尋，如果找到則回傳1，如果找不到則回傳0。（17 分）（注意：請寫一 個searching 類別，內含一個search 功能）請分析修改後的三元化搜尋 法其最差時間複雜度（worst case time complexity）以order 的方式表示。 （8 分） （注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）

6 8 7 5 二、求下列遞迴函數值 (3) f ？（10 分） int f(int n){if(n == 0)return 0；else return f(n-1)+n*n;} 求遞迴函數f(n) ？,nN（10 分） 三、k N-{1}，若有一棵k 元樹（k_ary tree）其中分支度（degree）為i 的節 點數為i 個，i = 1, 2, ..., k，請問該k 元樹其葉節點數L(k)為何？（15 分）

(3) 10 分

二維平面空間內包含資料節點，編號為1 到11。依編號由小到大加入此 二維平面空間。節點1 加入時，將空間分割為左右兩個二維空間。之後 每加入一資料節點時，若包覆此節點二維空間為前次分割為上下空間， 則此次分割為左右空間；反之，則此次分割為上下空間。左圖顯示加入 6 個資料節點後之空間分割結果，右圖顯示對應的二元樹。若繼續加入 節點7 到11。（每小題10 分，共20 分） 此二維空間平面分割結果將為何？ 對應的二元樹將為何？ 1 2 3

請使用C 語言寫一副程式void FindMeanAverage(int A [], int n, int * mean, int * average)，對一個未排序的（unsorted）且長度為n 的陣列 A[0:n1]，尋找陣列中的中位數與平均數，並分別存入mean 及average 運算複雜度。（17 分）請舉例說明此副程式最差情況（worst case）所 花費的運算複雜度。（8 分）（注意：請加註解說明程式碼作法。）

密文（Cipher text or Cypher text）：明請到家玩天你我來，應用環狀串列 （circular linked list），請問明文（Plain text or Clear text）為何？（15 分）

如下圖設背包限重100，有A、B、C、D、E 共五個不可分割物件，請 問依貪婪策略（Greedy Algorithm），0_1 整數背包問題（knapsack problem）/貨物裝載問題（cargo loading problem）其最大利益為何？其 對應的0_1 整數規劃為何？（20 分） 有A、B、C、D、E 共五個可分割物件，請問依貪婪策略，0_1 分數背 包其最大利益為何？（10 分） 物件 重量 利益 A 10 20 B 20 30 C 30 66 D 40 40 E 50 60

1 2 3 4 5 6

9 10 11 四、給予如下之加權雙向圖，邊上的加權值表示此邊的成本。 a b c e f d 7 3 8 2 10 5 6 9 4 使用Kruskal’s algorithm 找最小成本擴張樹（Minimal Cost Spanning Tree, MST）。執行過程中，將邊（edge）逐步加入此MST 之順序為何？ 請以邊所對應的兩端節點表示此邊。（5 分） 使用Prim’s algorithm 找出最小成本擴張樹（MST），從節點a 出發。 執行過程中，將邊（edge）逐步加入此MST 之順序為何？請以邊所對 應的兩端節點表示此邊。（5 分） 使用Dijkstra’s algorithm 找出從節點a（來源節點）到其五個節點（目 的節點）之最短路徑（shortest path）。執行過程中，逐步找出最短路徑 的目的節點順序為何？從節點a 到目的節點之最短路徑被找出表示演 算法不再檢視此目的節點之其它可能最短路徑。（10 分） 來源節點a 出發到其他五個目的節點之最短路徑走法與成本分別為 何？（10 分）

資料庫應用中，需要根據主鍵值（Primary Key）建立索引檔，索引檔的 建立常使用B-tree 樹狀結構，今有一串資料，其主鍵值分別為：44, 29, 39, 64, 67, 59, 69, 49，畫出將此串資料建成order 3 的B-tree，接著，畫出從此串 資料，新增（Insert）主鍵值55 後order 3 的B-tree，最後，畫出從此串資料 刪除（Delete）主鍵值49 後order 3 的B-tree。（20 分）

考慮數字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分）

(5)　(1)　(4)　(3)　(2) 5 分

給定一個無向圖（Undirected Graph）G 的鄰接列表（Adjacency List）如圖， 試依據該列表提供的資訊繪製出對應的無向圖G，然後由節點（Vertex）H 為 起始點繪製Depth First Search（DFS）與Breadth First Search（BFS）生成樹 （Spanning Tree），遇有多個節點可被走訪時，字母順序越前面的節點，其 被走訪的優先順序就越高。（20 分） 無向圖G 鄰接列表

優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮 管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入 （Insert）與擷取最小者（Delete_Min）。 請說明如何利用優先佇列對n個鍵值進行排序。（6分） 我們使用一個未排序的陣列（Unsorted Array）來管理鍵值以實現一個 優先佇列，請回答下列問題：（10分） ⑴若有n個鍵值，請說明兩個主要操作（加入（Insert）與擷取最小者 （Delete_Min））的時間複雜度。 ⑵請判斷下面的敘述是否為真，並請說明原因： 若以此優先佇列進行排序（Sorting），其所對應的排序原理為插入排 序（Insertion Sort）。 二元堆積（Binary Heap）是一個優先佇列的資料結構，因為我們考慮鍵值 小的物件有高的優先權，所以又可稱為最小堆積（MinimumHeap）。（14分） ⑴在結構上最小堆積為一個完全二元樹（Complete Binary Tree），若使 用一個陣列來實作最小堆積，陣列中物件的鍵值放置如下，請描述此 陣列對應的完全二元樹（以樹狀結構表示）。 Index 1 2

新冠肺炎肆虐全球，目前世界各國生物及醫學實驗室均在尋找新型冠狀病 毒的基因，假設新型冠狀病毒的基因由A, T, C, G, H, M 核苷酸所組成， 今有一新型冠狀病毒的基因為ATATATCCHCGMCMA，請使用霍夫曼演 算法（Huffman Algorithm）設計霍夫曼樹（Huffman Trees），並設計出一 編碼表（Code Words），依序分別寫出A, T, C, G, H, M 核苷酸的編碼位 元數，將此新型冠狀病毒基因以最少位元數（Minimum Bit Strings）編碼， 並計算出最少位元數（Minimum Bit Strings）。（20 分）

給予一串資料：45,30,40, 65,68,60, 70,50，將此串資料依序建成一max-heap 樹，並說明如何從此max-heap 樹進行由小至大的排序（Sorting）。（20 分）

給予兩線性鏈結串列，其節點C 語言的宣告如下：（20 分） #include <stdio.h> #include <stdlib.h> struct node{ int data; struct node *next; }; typedef struct node *NODEPTR; 此兩線性鏈結串列，分別由指標plist1 與plist2 指在串列首，請完成下列 程式片段，將plist2 所指串列接在plist1 所指串列後面。 void concate（NODEPTR plist1, NODEPTR plist2） { NODEPTR p; }

9 10 11 12 四、在一棵高度為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的AVLtree 中，並平衡之。 （12分） 圖1 五、請利用堆積排序法（Heap Sort）將圖2逐步建立成Min Heap，並將數字 從小到大逐一列舉。（10分） 圖2 六、請利用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 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

9 10 Key 35 18 42 24 7 14 25 12 38 21 ⑵請說明二元堆積中何謂堆積特性（Heap Property）？ ⑶前揭⑴中的完全二元樹並未有堆積特性，請將其進行堆積化 （Heapify），並以陣列表示出堆積化後的最小堆積所對應之完全二元樹。 三、請回答下列關於AVL樹（AVL Tree）的問題： 我們欲將所管理的鍵值（Key）依序列出，請問是否可以利用一個AVL 樹對鍵值來進行排序（Sorting）？若不行，請說明原因；如果可以，請 描述方法及時間複雜度。（5分） 請提供一個線性時間的演算法來判斷一個二元搜尋樹是否為AVL樹。 （10分） 在AVL樹上進行一個加入（Insert）操作後，是否最多只需要一次的重構 （Restructuring）即可恢復其平衡的特性？請說明原因。（10分） 四、若我們用相鄰矩陣（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 Graph, DAG），所以存在節點的拓樸排序（Topological Sort），請對G’ 給出一個拓樸排序（Topological Sort）。 ⑵請給一個方法來判斷一個有向圖是否沒有迴圈。

下列程式函式 doit()以C 語言語法呈現，用以對雙向鏈結串列（doubly linked list）進行處理。請依據該函式回答問題。 void doit(struct node **head){ struct node *temp = NULL; struct node *current = *head; while(current != NULL){ temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } if(temp != NULL) *head = temp->prev; }  若X 指向一個雙向鏈結串列如下，其中X->prev 指向NULL，X->next 指向資料為21 的節點。請顯示並說明doit（&X）執行過後該串列變化 結果。（10 分）  若X 指向一個雙向鏈結串列如下，其中X->prev 指向資料為17 的節點， X->next 指向資料為35 的節點。請顯示並說明doit（&X）執行過後該 串列的變化結果。（5 分）  若X 指向一個環狀雙向鏈結串列（circular doubly linked list），請說明 doit（&X）是否仍能順利執行。（5 分） NULL NULL X 17 21 35 74 95 NULL NULL X 17 21 35 74 95

一般常用的算術運算式（Arithmetic Expression）有：中序運算式（Infix Expression）、前序運算式（Prefix Expression）、後序運算式（Postfix Expression）三種表示法，請回答下列問題： 考慮中序運算式 7 4 )3 / 9 5 ( )

給予如下二元樹節點的宣告，分別寫出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){ }

給定T 為一個以陣列表示的二元搜尋樹（binary search tree）。  若有一些介於1 及1,000 的正整數被儲存於T，且要搜尋數字364，請 說明搜尋過程是否有可能為3, 400, 388, 220, 267, 383, 382, 279, 364？ （5 分）  若有一些介於1 及1,000 的正整數被儲存於T，且要搜尋數字364，請 說明搜尋過程是否有可能為926, 203, 912, 241, 913, 246, 364？（5 分）  若對T 進行前序遍歷（pre-order traversal）的結果為30, 20, 10, 15, 25, 23, 39, 35, 42。請說明若以後序遍歷（post-order traversal），結果為何。（5 分）  若對T 進行後序遍歷（post-order traversal）的結果為25, 20, 34, 37, 31, 49, 46, 57, 60, 52, 41。請說明若以中序遍歷（in-order traversal），結果為何。 （5 分）  請說明可將二元搜尋樹T 轉換為最小堆積（min heap）的程序為何？（10 分）

6 ( × + + × − ，請說明其前序與後序運算式 分別為何？（8 分） 請說明為何中序運算式需要使用括號來輔助界定運算元的優先順序 而前序與後序運算式則無需括號？（7 分） 請說明如何利用一個堆疊（Stack）結構計算出一個後序運算式的值， 並以後序運算式a b × c + d c / −為例，其中a = 3, b = 5, c = 2, d = 6， 請逐步列出運算過程中堆疊的內容。（10 分） 二、以下是關於二元搜尋樹（Binary Search Tree）的問題： 請說明二元搜尋樹的定義？（5 分） 是否可以使用一個二元搜尋樹對鍵值（Key）來進行排序（Sorting）？ 如果不行，請解釋其原因。若可以，請描述作法及執行時間。（5 分） AVL 樹是一個基於二元搜尋樹的資料結構，請敘述AVL 樹的定義 並說明為何一個有n 個節點（鍵值）的AVL 樹其高度是O（log n）。 （5 分） 若將鍵值36、25、14、27、55、30 以依序加入的方式建構一個AVL 樹，請繪出每次加入後的AVL 樹。（10 分）

給予如下二元樹節點的宣告，寫一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){ }

給定以相鄰矩陣（adjacency matrix）表示的圖G，矩陣中的數字為相鄰兩 節點間的距離，若空白則代表兩節點不相鄰。 G a b c d e f g h j a 1 6 5 b 1 6 c 6 6 7 3 d 5 2 10 e 7 12 f 3 2 8 g 10 7 3 h 12 8 7 8 j 3 8 圖G  請說明若以Kruskal’s 演算法建立最小生成樹（minimum spanning tree） 的過程中，依序被加入生成樹的邊。（5 分）  請說明若以Prim’s 演算法建立最小生成樹（minimum spanning tree）的 過程中，依序被加入生成樹的邊。（5 分）  請說明Dijkstra’s 演算法的用途，並說明該演算法應用上的限制。（10 分）  請說明將圖G 從f 節點開始執行Dijkstra’s 演算法的過程並顯示節點加 入的順序。（10 分）

優先佇列（Priority Qu 提供的功能有：加入 有最高優先權的資料物 有越高的優先權，加入 請說明如何利用優先 二元堆積（Binary H 定義。（6 分） 若我們分別使用排序 二元堆積三種資料結 三種方式在加入in 度。（6 分） 在考慮鍵值低的資料 稱為最小堆積（Min 請說明如何輸出所有 運算量）與鍵值小於

給予如下程式，假設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; }

請將所給定數字藉由所指定雜湊函數依序置入雜湊表  若雜湊函數為H(k) = k mod 11，並以線性探測（linear probing）解決溢 位（overflow）問題，請顯示將15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12, 0, 21 依序置入11 桶（buckets）x 2 槽（slots）雜湊表的最終結果。 （10 分）  若雜湊函數為H(k) = k mod 7，並以平方探測（quadratic probing）解決 溢位（overflow）問題，請顯示將15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12 依序置入7 桶（buckets）x 2 槽（slots）雜湊表的最終結果。（10 分） A[.] 0 1 2 3 4 … 槽1 槽2

一個圖形結構（Graph 一個有向圖（Directed 一個有向圖不具有迴 Acyclic Graph, DAG 種不同的拓樸排序 若在圖G 上由節點 請列出此一拓樸排序 一個有向圖若具有強 點u 與v 彼此可藉由 否具強連通性的方法 a d g ueue）用來管理具有優先權順序的 （Insert）任意資料物件，以及移 物件。我們在此假設鍵值（Key 入與移除功能分別命名為insert() 先佇列將資料物件以鍵值進行排 Heap）是一個實現優先佇列的資 序串列（Sorted List）、未排序串列 結構來實現有n 個資料物件的優 nsert()與移除remove_Min()功能 料物件有高的優先權的情況下， nimum Heap）。若給定一個最小堆 有鍵值小於或等於k 的資料物件 於或等於k 的資料物件之數量成線 h）中，若所有的邊都具有方向 d Graph）。 迴圈（Cycle）則稱為一個有向非 G），考慮下方的有向非循環圖G （Topological Sort）？（7 分） c 開始進行拓樸排序，並考慮字 序並說明方法與所需要的時間複 強連通性（Strong Connectivity） 由不同路徑相互連通。請提供一個 法，並說明其正確性與時間複雜 有向非循環圖G b c e f h i j 序的資料物件，主要 移除（Remove）具 y）越低的資料物件 )及remove_Min()。 排序。（5 分） 資料結構，請敘述其 列（Unsorted List）、 優先佇列，請比較這 能上所需的時間複雜 所使用的二元堆積 堆積與一個鍵值k， 件，而所花的時間（或 成線性比例。（8 分） ，則此圖形結構為 非循環圖（Directed G，請說明G 共有幾 字母順序進行排列， 複雜度。（8 分） ），則其中任意兩節 一個驗證一有向圖是 雜度。（10 分）

用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 分）

將下列六個鍵值: 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）。 40 62 83 10 20 31 45 55 70 78 90 92 李四(LS) 趙六(CL) 王五 (WW) 張三 (CS)

計算正整數a 和b 的最大公因數gcd(a, b)的演算法，以類似C 語言表示 如下: 1 integer gcd(a, b) {

若已知一個二元樹（binary tree）的節點數（node）總共有305 個，且有104 個樹葉 節點（leaf node），試求出分支度（degree of branch）為1 的節點數有多少個？（10 分）

請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩 者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的 差異（13 分）。 若有n 個鍵值，以下列甲和乙兩種資料結構策略儲存： 策略甲：由小到大依序儲存在一陣列中 策略乙：以AVL tree 架構儲存 請以Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或 兩者效能相近：尋找特定鍵值k；尋找排序為j 的鍵值；刪除特定鍵值k； 刪除排序為j 的鍵值；插入新鍵值；依序輸出所有鍵值。（12 分）

x = a; y = b;

一非空的二元樹（binary tree），如果有n0 個葉節點（leaf node）且n2 個節點之分支 度（degree）為2，請證明n0 = n2+1。（25 分）

已知一個二元樹（binary tree）的後序追蹤（postorder traversal）為FEACGHBD，而 中序追蹤（inorder traversal）為EFADCBGH，其中字母A 到H 分別代表一個節點的 名稱。 請畫出此二元樹。（10 分） 請寫出此二元樹的前序追蹤（preorder traversal）。（5 分） 請寫出此二元樹的廣度優先走訪順序（breadth-first traversal）。（5 分）

while (y > 0) {r = x % y; x = y; y = r;}

一無向圖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 分）

給定一權重圖（weighted graph）如下： 試寫出下圖的相鄰矩陣（adjacency matrix）及相鄰串列（adjacency list）。（10 分） 請使用Kruskal 演算法找出下圖的其一種最小生成樹（minimum spanning tree）， 並寫出最小生成樹的邊之建構順序。（15 分）

return x;