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

大學生只剩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）

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 的計算過程， 不予計分。）

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

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

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

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

二元搜尋法（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 分） （注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）

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

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

如下圖設背包限重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 分）