110年 - 110 高等考試_三級_資訊處理：資料結構#102802

科目：公職◆資料結構 | 年份：110年 | 選擇題數：0 | 申論題數：10

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (10)

(一)請列出此 5 個矩陣相乘 A✖B✖C✖D✖E 所有可能的乘法順序（請用括號表示乘法順序）。（5 分）

(二)請使用 Dynamic Programming（動態規劃）的技巧計算出此五個矩陣相乘 A✖B✖C✖D✖E 的最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費的乘法數量最少。（15 分）

(三)請列出此五個矩陣相乘所需要花費的最少乘法數量。（5 分）（注意：未說明 Dynamic Programming 的計算過程，不予計分。）

(一)請設計一個 Greedy（貪婪）的演算法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量最少，並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。（15 分）

(二)此 Greedy 演算法適合使用何種資料結構來完成。（5 分）

(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5 分）

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

(一)請使用 C 語言寫一副程式 void FindMeanAverage(int A [], int n, int * mean, int * average)，對一個未排序的（unsorted）且長度為 n 的陣列 A[0:n1]，尋找陣列中的中位數與平均數，並分別存入 mean 及 average 運算複雜度。（17 分）

(二)請舉例說明此副程式最差情況（worst case）所花費的運算複雜度。（8 分）（注意：請加註解說明程式碼作法。）