Course: Introduction to Computer Science Exam. #3 Date: Jan. 10, 2005

Instructor: 趙坤茂 (台大資訊工程系) TA: 王弘倫 陳明江

請在答案卷依序作答，記得填上系級、學號及姓名

考試時間：100分鐘

簡答題 (每題10分，共100分)

1.     給定數列23、12、58、85、72、98、13、37，請找出其中的最小數及第二小數，把你的做法記錄下來。(用的比較次數愈少，分數愈高)

2.     給定數列25、1、8、5、7、9、13、3，請分別以「選擇排序法」、「插入排序法」及「泡沫排序法」將它由小排到大，記錄你的過程。

3.     給定已排序好的數列12、18、25、34、66、79、82、88，請以「二元搜尋法」找看看81在不在這數列中，也找找看12在不在這數列中，記錄你的過程。

4.     在課堂上，我們分別以遞迴呼叫方式及列表式方法等兩種程式計算費氏數（Fibonacci number），哪一個程式比較有效？為什麼有個程式要等很久？為什麼另一個有效的程式只要一瞬間就算好了呢？

5.     以LCS的方法，找ATTAGTCGT和GTAAATGGTC這兩個序列的最長共同子序列，記錄你的列表及回溯路程。

6.     軟體生命週期的五大過程為何？何謂白箱測試？何謂黑箱測試？

7.     請解釋下面這個SQL查詢句：

            SELECT 姓名，地址，監護人

            FROM  student，enroll

            WHERE      課程 = ‘程式語言’　and

                         期末考 < 60 and

                         student.學號  = enroll.學號

8.     簡述你操作Access的經驗。

9.     何謂XML？DTD是用來做什麼的？XQuery的敘述式為FLWR表示式，這四個字母分別是哪四個？

10. 何謂資料壓縮？為什麼我們要做資料壓縮，有什麼好處呢？