加載中. ..
PDF
110年公務人員高等考試三級考試試題
類 科
：
資訊處理
科 目
：
資料結構
考試時間
：
2
小時
座號
：
※注意：禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
代號：
37950
頁次：
2
－
1
一、A為（8×4）矩陣、B為（4×10）矩陣、C為（10×3）矩陣、D為（3×20）
矩陣、E為（20×4）矩陣，請列出此 5個矩陣相乘 ABCDE所有
可能的乘法順序（請用括號表示乘法順序）。（5分）請使用 Dynamic
Programming（動態規劃）的技巧計算出此五個矩陣相乘 ABCDE的
最佳乘法順序（請用括號表示乘法順序），使得五個矩陣相乘所需要花費
的乘法數量最少。（15 分）請列出此五個矩陣相乘所需要花費的最少
乘法數量。（5分）（注意：未說明 Dynamic Programming 的計算過程，
不予計分。）
二、假設收銀機內銅板的集合 S={$50, $20, $20, $15, $10, $2, $1, $1, $1}，而
預計找錢給顧客的金額 W=$75。請設計一個 Greedy（貪婪）的演算
法，來解決找錢給顧客的問題，使得找給顧客金額 W所使用的銅板數量
最少，並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。（15 分）
此Greedy 演算法適合使用何種資料結構來完成。（5分）此Greedy
演算法的解法是否能保證為最佳解？請舉例說明。（5分）
三、二元搜尋法（binary search）使用 divide-and-conquer（分而治之）演算法
技巧，對一個已排序的（sorted）且長度為 n的陣列 A[0:n1]，以二元化
方式進行資料值 x的搜尋，其最差時間複雜度（worst case time
complexity）可降到(log n)。請使用 C++或Python 語言，修改此二元
搜尋法，使其能對未排序的（unsorted）且長度為 n的陣列 A[0:n1]，進
行三元化搜尋，即以 divide-and-conquer 技巧將此陣列切成三個子陣列，
並在可能包含資料值 x的子陣列繼續進行 divide-and-conquer 技巧的搜
尋，如果找到則回傳 1，如果找不到則回傳 0。（17 分）（注意：請寫一
個searching 類別，內含一個 search 功能）請分析修改後的三元化搜尋
法其最差時間複雜度（worst case time complexity）以 order 的方式表示。
（8分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法。）
代號：
3
7950
頁次：
2
－
2
四、請使用 C語言寫一副程式 void FindMeanAverage(int A [], int n, int *
mean, int * average)，對一個未排序的（unsorted）且長度為 n的陣列
A[0:n1]，尋找陣列中的中位數與平均數，並分別存入 mean 及average
運算複雜度。（17 分）請舉例說明此副程式最差情況（worst case）所
花費的運算複雜度。（8分）（注意：請加註解說明程式碼作法。）