資訊處理 114 年資料結構考古題

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

費伯納西數列（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 分）

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

假設每個運算元都是一位整數，使用堆疊方法，模擬後序式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 分）

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

假設現有五個字母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）過程，最後給出排序後的結果。

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

請逐步寫出下列使用遞迴函式的呼叫與輸出過程。（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; }

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

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

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

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

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 個機器人， 整組球順序排好的速度可以加快多少？請說明。