資訊處理 100 年程式語言概要考古題

大部分程式語言要求陣列（array）的元素必須是同一種資料型態（data type），而 且將陣列元素依照行（row）或列（column）為主的方式將其對應到記憶體位置， 假設A 是一個m×n 的二維整數陣列：（10 分） var A : array[1..m,1..n] of integer; 另外假設每個整數需要k 個bytes，陣列A 的開始位置為a。 ㈠以m = 2, n = 3, k = 4, a = 2000 為例，說明以行為主和以列為主時，陣列A 每個元 素在記憶體中的開始位置。 ㈡分別推導出以行為主和以列為主時，A[i, j], 1 ≤ i ≤ m, 1 ≤ j ≤ n 在記憶體中的開始 位置。

程式語言通常要求等號（assignment, =或:=）左右兩邊需要有相同的資料型態，檢查 資料型態是否相同的方法可分為靜態（static）和動態（dynamic）兩種方式，針對 以下敘述，判斷那些是對的？那些是錯的？並簡單說明其理由。（只有答案者不計 分）（20 分） ㈠動態核對資料型態會使我們撰寫的程式執行起來更有效率。 ㈡核對資料型態使我們撰寫的程式比較不容易出錯。 ㈢任一種程式語言都可以用靜態方式來核對資料型態。 ㈣若程式可以分成許多模組，分別在不同時間翻譯，例如C 程式，則不管怎麼做， 採用靜態核對資料型態就無法完全核對資料型態是否相符。

許多程式語言的編譯器將程式所需使用的資料分別放在不同區域：(1)固定區（static）、 (2)堆疊區（stack）和(3)堆積區（heap）。（20 分） ㈠說明將資料分區儲存的目的為何？ ㈡分別舉例說明那些資料最適合存放在那個區域。

以下是1 個函數（function），用類似C（C-like）的語言來表示。假設輸入的參數 n 都是正整數，請回答下列問題：（10 分） ㈠這個函數在計算什麼？（用n 的函數來表示） ㈡將這個函數改成不用recursive call 的寫法。 1) int f(n) { 2) if (n > 1) 3) return n * f(n – 1); 4) else 5) return 1; 6) } 100年公務人員特種考試海岸巡防人員考試、100年公務 人員特種考試關務人員考試、100年公務人員特種考試稅 務人員考試、100年特種考試退除役軍人轉任公務人員考 試及100年國軍上校以上軍官轉任公務人員考試試題 類(科)別： 資訊處理

Prolog 是一個邏輯程式語言（logic programming language），它可以描述事實（fact）、 規則（rule）以及目標（goal），以下有5 個事實、2 個規則： 1) parent(carol, john). 2) parent(john, mary). 3) parent(mary, jim). 4) parent(john, sue). 5) parent(david, jim). 6) ancestor(X, Y) :=parent(X, Y). 7) ancestor(X, Z) :=parent(X, Y), ancestor(Y, Z). 假設目標是ancestor(john, X).則根據這些事實，滿足條件的X 有那些？（20 分） 六、程式語言的語法可用BNF（Backus-Naur Form）來描述，請參考以下語法，其中開 始符號（starting symbol）是S、a 為運算元（operand）、其餘3 個terminal symbols 為運算子（operator），請回答下列問題：（20 分） 1) S → S @ T | T 2) T → W ! T | W 3) W → # W | a ㈠依照句子的長度，從短到長，寫出符合語法且長度不超過3 的所有句子。 ㈡依照從高到低的優先順序（precedence），列出此語言的3 個運算子。 ㈢那些為二元運算子？ ㈣那些二元運算子是左結合（left associative）？那些二元運算子是右結合（right associative）？