資訊處理 94 年演算法考古題
民國 94 年（2005）資訊處理「演算法」考試題目，共 5 題 | 資料來源：考選部
0 題選擇題 + 5 題申論題
考慮三種排序方法：選擇排序法（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 分）
資訊處理 94 年其他科目
國文基礎能力測驗外國文(英文)法學知識法學知識與英文程式語言資料庫應用資料結構資訊管理資訊系統與分析資通網路資通網路與安全程式設計概要計算機概要資通網路與安全概要憲法與英文系統分析與設計研究資訊管理與資通安全研究軟體專案管理研究高等資料庫設計資料處理概要資訊管理概要程式設計系統專案管理英文資訊管理與資通安全概要系統分析與設計資訊管理與資通安全中華民國憲法與英文程式語言概要策略規劃與問題解決系統分析研究資訊管理研究策略規劃與問題解決(依類科命題)資料通訊電腦網路系統分析資料處理專利法規計算機通信網路資料庫設計中華民國憲法中華民國憲法概要電子計算機概要資料庫運用世界地理大意資訊管理大意電子計算機大意作業系統概論本國歷史與地理概要公民與本國史地大意計算機大意資料處理大意專業知識測驗(資料處理概要)綜合知識測驗(一)(中華民國憲法概要、本國歷史、地球科學)綜合知識測驗(二)(法學緒論、數的推理)程式語言大意資訊系統管理高等資料處理資料庫管理系統資料庫管理系統概要資訊網路資訊網路概要中外地理中外地理大意中外地理概要公路法商港法系統分析與設計概要