資訊處理 95 年程式語言考古題

試說明編譯程式（compiler）中，碼最佳化（code optimization）模組之功能及主要 之作法，並舉例說明之。（20 分）

解釋名詞：（每小題5 分，共20 分） Parsing Register Management Loop Optimization Functional languages

在達文西密碼一書中有提及Fibonacci 序列為1,1,2,3,5,8,13,21,…，即其定義為 f(n) = f(n-1) + f(n-2)，n≥3，f(1) = f(2) = 1，請以PASCAL，C，JAVA 中任一種語 言寫一程式來計算Fibonacci 數f(n)，並請使用遞迴副程式（recursive call，即副 程式呼叫本身）。（20 分）

試說明評鑑一種程式語言優劣之準則。（10 分） 試以上述準則評鑑一種你（妳）所知之程式語言。（10 分）

在C 程式語言中使用遞迴函數，受到甚麼限制？每家廠商的C 程式語言編譯器會都 相同嗎？（10 分）

試寫出一BNF 文法，使其產生二進位數字，且數字之值為3 之倍數。（20 分）

請使用任一程式語言，分別以遞迴（recursive）及非遞迴演算法來計算利用N 條線 將平面分成最多的區域，其中N 為大於等於0 之整數。（20 分）

寫一個最小的程式讓UNIX 作業系統當機。（20 分）

若程式語言本身不提供捷徑計算，則下列虛擬指令程式片段會出現什麼錯誤訊息？ （10 分） index := 1; while(index <= listlen) and (list[index] <> key) do index := index + 1; （假設list[1..listlen]為被查詢之陣列，而key 為要查詢之值） 試說明Ada 程式語言預設為不提供捷徑計算之理由，並舉例說明之。（10 分）

請舉例並以任一物件導向（object-oriented）程式語言，說明動態繫結（dynamic binding）之功能及使用時機。（20 分）

比較下列三種程式語言的異同：Fortran，C，java。（15 分）

一個平行程式語言（concurrent programming language）較非平行程式語言在設計上 須增加競爭（competition）及合作（cooperation）同步（synchronization）機制，試 以Ada 或Java 程式語言分別說明之。（20 分）

試以兩個資料交換之副程式為例，說明C 程式語言如何利用以值呼叫（called by value）參數傳遞方法來達成以址呼叫（called by reference or called by address）之效 果。（20 分）

不同的程式語言各有各的註解方式（comments），試舉三種並分析其特色。（15 分） 六、程式語言的定義與它的編譯器有何關係？為何一個C 語言的定義會有許多廠商提供 不同的編譯器？（20 分）

試算出下列虛擬指令之時間複雜度：（每小題10 分，共20 分） for i = 0 to n do begin j = i ; while j > 0 do j = j / 2; end for i = 0 to n do begin j = i ; while j > 0 do j = j - 1; end