演算法考古題｜歷屆國考試題彙整

考慮三種排序方法：選擇排序法（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 分）

已知甲電腦在input size 為1000 時，執行A、B、C 三個演算法都需要1 分鐘， A、B、C 三個演算法的Time Complexity 分別為a n、b n2、c 10n（a、b、c 為常 數，n 為input size）。假設乙電腦的執行速度比甲電腦快10000 倍，請問對於A、 B、C 三個演算法，乙電腦在1 分鐘內可以解的input size 最大是多少？（24 分）

請證明利用Greedy Approach 來解Fractional Knapsack Problem 可以得到最佳解。 （15 分） 請設計一個Dynamic Programming 的演算法來解0-1。Knapsack Problem（須加上 適當的說明來解釋你的設計），並分析該演算法的Time Complexity。（15 分）

請簡述NP 與NP-Complete 的定義。（6 分） 請簡述Cook’s Theorem 的內容（不須證明），並說明其對研究NP-Complete 重要 性。（10 分） 要如何才能證明P=NP 或P≠NP？請分別說明。（10 分） 請問Sorting Problem 是不是NP？請說明原因。 （10 分）

請簡述何謂Pseudo-Polynomial-Time Algorithm？（10 分）