資訊科技概論

1. 下列有關暴力法解決問題方法的敘述，下列何者不正確？

（A）是最原始的解題方法

（B）是最簡單的解題方法

（C）是一種一一嘗試的方法

（D）適用於解決各種問題

解析：

（D）暴力破解法僅是用於「簡單」、「資料量小」的問題，過於複雜或資料量大的問題不適合使用暴力破解法

2. 將大而複雜的問題，分解成較小較簡單的問題，並且以解決這些小問題的方式，解決整個問題。這種解題方式屬於哪一種方法？

（A）由上而下

（B）由下而上

（C）由大而小

（D）由繁而簡

3. 下列何種電腦解題方法常被稱為模組化設計？

（A）由下而上

（B）由上而下

（C）貪進法

（D）回溯法

4. 下列何者不是模組化設計的優點？

（A）易於分工

（B）模組可重覆使用

（C）方便設計者獨立作業

（D）易於測試與除錯

解析：

（A）模組化設計可將各個模組分工給不同的程式設計師負責，只要設計師之間對於模組間的互動有共同標準即可
（B）同樣功能的程式不必反覆重寫，只要寫一個模組便可以重複使用
（C）通常一個經過模組化的程式裡面含有多個子模組，設計者無法獨立以一個模組作業
（D）模組通常功能較整個大程式來得簡單，因此除錯較容易

5. 校務行政系統可細分成校務、教務、學務、輔導、系統管理等子系統，這種設計方式屬於哪一種解題方式？

（A）回溯法

（B）分治法

（C）由下而上

（D）由上而下

6. 分割輸入、解決子問題、組合解答是何種電腦解題方法的基本步驟？

（A）回溯法

（B）分治法

（C）由下而上

（D）貪進法

7. 何種電腦解題方法會把大而複雜的問題，分解成較小且較簡單的問題，以解決這些小問題的方式，解決整個問題？

（A）回溯法

（B）由下而上

（C）由上而下

（D）貪進法

8. 有一找出最大數的解題方法：1.設最大數為第一個數。2.重複取下一個數和最大數比較，如果此數大於最大數，則將大最數設為該數，直到所有的數都比過。此解題方式是採用哪一種方法？

（A）回溯法

（B）由下而上

（C）由上而下

（D）貪進法

9. 在解題的過程中，一次一步一步，每次都找最有利的步驟進行，直到找到解決問題的解答。這是哪一種解題方法？

（A）回溯法

（B）由下而上

（C）由上而下

（D）貪進法

10. 要找出一條最小成本的路徑，將許多城市連接起來，而不產生循環，可以使用哪一種解題方法？

（A）回溯法

（B）由下而上

（C）由上而下

（D）貪進法

11. 可分割之背包問題（Knapsack Problem）屬於哪一種解題方法？

（A）回溯法

（B）由下而上

（C）由上而下

（D）貪進法

解析：

「可分割」之背包問題屬於「貪進法」；「不可分割」之背包問題屬於「回溯法」

12. 何種電腦解題方法是採由上而下的方法？

（A）分治法

（B）回溯法

（C）貪進法

（D）由下而上

13. 電腦軟體的「還原」功能，屬於哪一種解題方法之概念？

（A）分治法

（B）回溯法

（C）貪進法

（D）由下而上

14. 如果要設計電腦象棋，可採用哪一種解題方法？

（A）回溯法

（B）分治法

（C）貪進法

（D）由下而上

15. 體育競賽的賽程通常會使用哪一種解題方法？

（A）回溯法

（B）由下而上

（C）由上而下

（D）貪進法

16. 下列有關循序搜尋的敘述，下列何者不正確？

（A）資料需要事先排序

（B）搜尋的效率差

（C）適用於小資料量的搜尋

（D）最簡單的搜尋方法之一

解析：

（A）使用循序搜尋法資料無須事先排序，使用二分搜尋法的資料才須事先排序

17. 二分搜尋法是將所欲搜尋的元素與資料中的哪一個元素進行比較？

（A）任意一個

（B）第一個

（C）最後一個

（D）最中間的

18. 有 7 筆資料（2, 13, 27, 32, 44, 58, 67），以二分搜尋法找尋關鍵值為 58 的資料，總共要作幾次比較？

（A）2

（B）3

（C）4

（D）6

解析：

共有 7 筆資料。以下是運算過程：
原始資料：（欲搜尋58）
　2　13　27　32　44　58　67

第一次比較：欲搜尋的數58比中間數32還要大，因此向右搜尋
　2　13　27　32　44　58　67

第二次比較：欲搜尋的數58恰等於中間數58，找到所求，因此停止搜尋
　2　13　27　32　44　58　67

因此共需比較 2 次即可在資料中找到 58

19. 如有 128 筆資料，在最壞的情形下，循序搜尋會比二分搜尋多幾次比較？

（A）120

（B）121

（C）122

（D）123

解析：

循序搜尋：
一開始，第 1 個數會被紀錄為最大值，然後與後面 127 個數依序比較，若是有更大的數則取代原先的紀錄。在最壞的情形下，最大值紀錄需要與第 2 個數到第 128 個數比較，因此最多需要比較 127 次

二分搜尋：
令在最壞的情形下需要比較 k 次
則 2^k ≧ 128
試求 k 的最小值為 7

127 - 7 = 120即為所求

20. 在300筆已由大至小排序好的資料中，用二分搜尋法搜尋某一筆特定資料時，若資料存在，最多需要比較幾次，可以搜尋到該筆資料？

（A）12

（B）16

（C）20

（D）30

解析：

令最多需要比較 k 次
則 2^k ≧ 3000
2¹¹ = 2048
2¹² = 4096
因此 k 的最小值為 12

21. 火車訂票系統是一種主從式的網路架構，以訂票的過程為例，下列何者不是伺服器端進行的動作？

（A）送出訂票完成的結果

（B）查詢訂票資料庫

（C）送出客戶填寫的基本資料

（D）新增資料庫內的資料

解析：

主從式網路架構中，「主」稱為伺服端，「從」稱為客戶端
（A）客戶端送出訂票的相關資料訊息，由伺服端送出訂票完成的結果
（B）客戶端輸入搜尋條件向伺服端查詢訂票資料，伺服端收到查詢條件後，便以該條件查詢訂票資料庫中是否有符合的資料
（C）客戶填寫基本資料後，由客戶端送出給伺服端
（D）伺服端收到客戶端的訂票資料後，新增資料庫內的資料