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