資訊處理 94 年演算法考古題

考慮三種排序方法：選擇排序法（Selection sort）、插入排序法（Insertion sort）、 與泡沫排序法（Bubble sort）。對於下列的問題請說明其原因：（20 分） ㈠當欲排序的資料都是很長的資料錄，且它們的鍵值長度都很短時，最適合用選擇 排序法，為什麼？ ㈡當欲排序的資料已經幾乎達到排序結果時，最適合用插入排序法，為什麼？ ㈢當欲排序的資料是完全相反次序時，最適合用選擇排序法，為什麼？ ㈣當欲排序的資料是完全相同時，最適合用泡沫排序法，為什麼？

數學上求兩數的最大公因數（Greatest Common Divisor，簡稱GCD）可使用歐幾里 德（Euclid）的輾轉相除法來完成。規則是“兩數m 與n 的最大公因數等於這兩數的 差和較小數的最大公因數”，由此可看出遞迴規則。請寫一個遞迴程式或演算法來 計算m 與n 兩數（m＞n）的最大公因數。（20 分）

請指出下列敘述為“真＂或為“假＂，並說明之。（20 分） ㈠一個NP-complete 的問題對任何輸入皆需指數次方的計算時間。 ㈡若P1 和P2 為兩個NP-complete 的問題，則P1 可轉換成P2，而P2 亦可轉換成P1。

考慮下列程式片段： for k := 1 to n do for i := 0 to k-1 do for j := 0 to k-1 do S（i,j,k）； 若n 0，則上述S（i,j,k）共執行了幾次？（20 分）

試提出兩種divide-and-conquer 演算法來將a1, a2,…,an 排序（sorting），並分別計算 其時間複雜度（time complexity）。（20 分）