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

A 君寫了以下的物件導向程式碼： class employee : public listcontainer { public: string getName(); Address GetAddress(); PhoneNumber getWorkPhone() ; bool isZipCodeValid(Addrss address); // given an address, this function check if the address’s zip // code is valid or not bool isPhonenumberValid(PhoneNumber phone); // given a phone number, this function check if the phone no. // is valid or not. public: static string _name ; static Address addr ; static PhoneNumber phoneno ; } A 君寫程式的思維是這樣子的，他想要用linked list 來儲存姓名、住址以及電話 。尤其是住址的部分，由於需要切割住址內容然後儲存到linked list 中，所以 他繼承了listcontainer（系統提供的list library）。另外A 君實做了幾 個method 來幫忙判定住址與電話號碼的格式是否合法。 請問上述的物件導向程式碼，犯了那一些違反物件導向原則的錯誤？（25 分）

給定下列十二種程式語言： (a) C++ (b) C (c) ALGOL 60 (d) Simula-67 (e) PASCAL (f) COBOL (g) Ada (h) Java (i) Fortran (j) SmallTalk (k) BASIC (l) Lisp 請針對上面十二種語言，回答下列各小題：（每小題3 分，共24 分） ㈠UNIX 作業系統是由那種語言所寫的？ ㈡第一個成功可編譯的高階語言（first compiled high-level language）是那一種語言？ ㈢第一個使用類別（class）觀念的語言是那一種？ ㈣第一個機器無關的語言（machine-independent language）是那一個語言？ ㈤在1970 年中期與1990 年後期間，那一種語言對教學有最大的影響力？ ㈥第一個使用BNF（Backus–Naur Form）語法的程式語言是那一種？ ㈦在過去五十年，那一種程式語言最常用在數學計算中？ ㈧第一個完全實現物件導向的程式語言，是那一種？

請回答下列程式語言的問題： 就程式語言來說，什麼是Object-Oriented languages? Functional languages? Logic languages? Script languages?（12 分） 從上述的四種語言中，除Logic languages 外，每種語言各舉兩個現存的語言。 （6 分） 最近語言的發展中，像Functional languages 與Script languages，都逐漸引進物件 導向性質（OO），就這兩類語言，各舉一個近來發展出且具有OO 性質的語言。 （2 分）

以下的C 程式碼需要實作一個SwapAndAdd function。SwapAndAdd()要達成 的功能是交換兩個變數，然後建立一個新的整數變數，將兩個變數相加存在該變數 之後，回傳新的變數位址讓呼叫端來使用。以下的main()顯示如何使用這個 SwapAndAdd() function。 int main() { int x, y, *result ; x = 100 ; y = 50 ; result= SwapAndAdd(......); // 請填寫參數x,y 應如何傳遞來使用SwapAndAdd printf(“%d %d %d”, x, y,(*result)); } 在這個main()中，我們會將x,y 變數作為參數傳到SwapAndAdd()。如果 SwapAndAdd()實作正確，這個main()會印出 50 100 150 請以C 語言完成SwapAndAdd()的程式碼，並且將main()當中的呼叫參數填入。（25 分） 102年特種考試地方政府公務人員考試試題 類 科： 資訊處理 全一張 （背面）

考慮下列文法： SÆ(L)| a LÆL,S | a ㈠請指出此文法的terminal symbol, non-terminal symbol, and start symbol.（6 分） ㈡請為(a, (a, a))字串，根據上述文法，做出left-most derivation sequence.（4 分） ㈢請為(a, (a, (a, a)))字串，根據上述文法，做出right-most derivation sequence.（4 分）

考慮下述用類似C 語言的語法寫出的程式： void swap(int a, int b) { int temp; temp = a; a = b; b = temp;} void main() { int value = 1, list[4] = {2, 3, 4, 5} //Array list is list[1..4] swap(value, list[1]); swap(list[1], list[2]); swap(value, list[value])} 根據以下的參數傳遞（parameter passings）模式，逐一列出在程式執行完畢之後的 value 與list 值： Passed by value? （5 分） Passed by reference? （5 分） Passed by name?（5 分）

以下的語法是ambiguous string → string + string | string – string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 這個文法針對9-5+2 可以產生兩個剖析樹（parsing tree），請畫出這兩個剖析樹。 （10 分） 為了糾正這樣的問題，請將上述的語法改寫成左結合（Left Associativity）來產生 單一的剖析樹。以9-5+2 為例，你的左結合語法所產生的剖析樹，將可以單一的 解釋9-5+2 為((9-5)+2)。（15 分）

給定下列的語法（grammar） SÆ aAb |bBA AÆab|aAB BÆaB|b, 請畫出下列各字串所對應的分析樹（parse tree）：（每小題5 分，共15 分） ㈠aaAbb ㈡baaBaaABab ㈢aaaAaBaBb

根據每一個元素（element）包含16 個英文字母的circular queue，當用長度m 的 陣列（array）來實作使用JAVA 語言寫出下列兩個方法的完整定義： Enqueue（10 分） Dequeue（10 分） 102年公務人員高等考試三級考試試題 類 科： 資訊處理 全一張 （背面）

Internet and web programming 其實結合了許多的技術與標準，請解釋下列幾個web programming 常用到的縮寫專有名詞。請寫出完整的英文名詞，然後請用數行文字 解釋這個專有名詞所代表的實質意義與技術內容。 CSS（6 分） AJAX（6 分） XML DOM（6 分） SOAP（7 分）

在高階語言函數傳遞，主要有四種方法 (a)call-by-reference (b)call-by-value (c)call- by-address (d)call-by-name，請就下列程式，利用上述四種參數傳遞方式，將結果 輸出。（16 分） int i= 0; void fun(int x, int y, int z) {i=y+1;y=y+1; x=z+x;} main( ){ int list[12]={1,2,3,4,5,6,7,8,9,10,11,12}; int a=1; fun(i, a, list[i]+a); printf(“i=%d, list[i]=%d”, i, list[i]);} 102年公務人員升官等考試、102年關務人員升官等考試 102年交通事業郵政、港務、公路人員升資考試試題 等別(級)： 薦任 類科(別)： 資訊處理 全一張 （背面）

對C#與JAVA 的concurrency 而言： C#的thread 可以是actor thread 嗎？JAVA 的呢？（5 分） C#的thread 可以被非同步呼叫嗎？JAVA 的呢？（5 分） C#的sleep method 與JAVA 的sleep method 有何不同？（5 分）

int c=1；請問下列迴圈內A 的指令會個別執行幾次？（每小題5 分，共15 分） ㈠while (c = 100) {A; c++;} ㈡for(; c++ < 100; c++) A; ㈢for(; ++c < 100; c+=2) A; 六、給定16 個數字如下：int Data[16]={233, 11, 19, 3, 217, 269, 235, 4, 111, 2171, 38, 91, 42, 117, 9, 452}，請分別利用Heap sort 的概念，試寫出程式，對這些數字做排序 （從大到小），先描述概念，再寫程式（可使用各種程式語言或虛擬碼）。（16 分）

考慮下述Prolog 程式： ancestor (x, x). ancestor(x, y) :- ancestor(z, y), parent(x, z) parent(Allen, John). 用一個subgoal 的搜尋樹（search tree），描述此Prolog 程式在執行查詢： ancestor(Allen, X)時的執行步驟。（10 分） 六、考慮下述的Scheme 程式： (define A (lambda () (let* ((x 2) (C (lambda (P) (let ((x 4)) (P)))) ( D (lambda () x)) (B (lambda () (let ((x3)) (C D))))) (B)))) 這程式列印什麼東西？（10 分） 如果Scheme 使用dynamic scoping 和shallow binding，它會印出什麼？（10 分）