試題評析

Size: px

Start display at page:

Download "試題評析"

裕贸
7 years ago
Views:

1 104 公職地方特考分詳解程式語言一請試述下列名詞之意涵 :( 每小題 3 分, 共 15 分 ) ( 一 )Context-Free Grammar ( 二 )LR parser ( 三 )Binding time ( 四 )Turing Machine ( 五 )Dynamic Programming 考命中本題為名詞解釋, 相較於以往三等程式語言考試中, 屬於較少見的題目但名詞部分除 LR parser 外, 其餘充分準備的考生應都不陌生, 歷年也曾出現過許多相似題, 如 103 檢事官 100 檢事官 99 考 94 地特等由於每題僅佔 3 分, 因此僅需簡單說明每個概念的內容即可, 不需要太深入探討以免錯失其餘題目得分機會 1. 程式語言講義第六回, 金乃傑編撰, 頁程式語言講義第三回, 金乃傑編撰, 頁程式語言講義第一回, 金乃傑編撰, 頁程式語言講義第二回, 金乃傑編撰, 頁 ( 一 ) 下文無關文法 (Context-Free Grammar): 若一個形式文法 G = (N, Σ, P, S) 的產生規則都如 :V w, 則稱之, 其中 V N,w (N Σ)* 因為 V 符號總可以被 w 字串自由替換, 而無需考慮 V 符號出現的下文故為下文無關由於下文無關語法表達能力好, 幾乎所有程式語言的語法都是用此語法定義 ( 二 )LR 剖析器 (LR parser): 為編譯器中語法剖析的程式, 功能為建構語法樹 LR 意指由左至右 (left to right) 處理輸入字串, 並以最右邊優先衍生 (Right derivation) 的推導順序由於 LR 剖析器嘗試由剖析樹的葉節開始, 向一層層透過文法規則的化簡, 最後規約回到樹的根部 ( 起始符號 ), 所以它是一種由下而的剖析方法 ( 三 ) 繫結時間 (Binding time): 為程式實體 (program entity) 與其屬性 (attributes) 發生關聯 (association) 的動作依照時間的不同可分為定義 (Definition, 設計程式語言 ) 實作 (Implementation, 在機器的運行規範 ) 編譯 (Compilation / Translation) 及執行 (Execute) 等四個時期 ( 四 ) 圖靈機 (Turing Machine): 為英國數學家圖靈於 1936 年提出的一種抽象計算模型圖靈的基本思想是用機器來模擬人用紙筆進行數學運算的過程, 可分為兩種動作 : 在紙寫或擦除某個符號 ; 把注意力從紙的一個位置移動到另一個位置基於此動作, 圖靈機的元件包括一條無限長的紙帶讀寫頭狀態暫存器及一套控制規則 ( 五 ) 動態規劃 (Dynamic Programming): 是一種在數學電腦科學中使用的計算方法, 透過將原問題分解為相對簡單的子問題的方式求解複雜的問題動態規劃的效益來自於將子問題的答案暫存, 避免子問題被重新計算, 以空間換取時間例如 : 在計算費式級數時, 將 f(2) f(3) 的結果暫存, 因此在計算 f(4) 時就不需要重複計算 f(1)~f(3) 了二 1O TBytes 換算為多少 bits?(5 分 ) 本題屬於計算機概論題目, 只要細心應可輕鬆得分 1 TB = 8 * 2^40 bits = 8,796,093,022,208bits 因為 : 1TB = 1,024GB = 2^10GB 1GB = 1,024MB = 2^10MB 1MB = 1,024KB = 2^10KB - 1 -

念的內容即可, 不需要太深入探討以免錯失其餘題目得分機會 1. 程式語言講義第六回, 金乃傑編撰, 頁 1-2 2. 程式語言講義第三回, 金乃傑編撰, 頁 56-57 3. 程式語言講義第一回, 金乃傑編撰, 頁 115 4.

2 104 公職地方特考分詳解 1KB = 1,024B = 2^10B 1B = 8bits 三關於副程式中參數的 binding 可分為 shallow binding deep binding 和 ad hoc binding 等方法 : ( 一 ) 請解釋述三種 binding 的差別與優缺 (9 分 ) ( 二 ) 下列為 Java Script 的 syntax codes, 請問執行 subl 之後, 最後 x 的輸出 ( 在 sub2) 為多少? 請根據述三種 binding 分別作答 (6 分 ) function subl() { var x; function sub2() {altert(x);} // 輸出 x function sub3() { var x; x=3; suh4(sub2);} function sub4(subx) { var x; x=4; subx();} x=l; sub3();}; 本題為繫結的進階考題, 考非區域變數取值的三種方法雖以往繫結都以名詞解釋出現 ( 如 101 年關務四等考試 ), 沒有較深入題目, 但由於此題為講義中經典補充, 若充分準備的考生應能得心應手, 獲得不錯的分數考命中 1. 程式語言講義, 第三回, 金乃傑編撰, 頁地方特考題神考前猜題程式語言重整理, 金乃傑編撰, 考 6 再次命中! ( 一 ) 三種繫結的差別與優缺比較如下 : 內容淺繫結 (Shallow Binding) 深繫結 (Deep Binding) 特設繫結 (Ad-hoc Binding) 為副程式變數取值的實作方為副程式變數取值的實作方為副程式變數取值的實作方式, 指副程式中若無定義變式, 指副程式中若無定義變式, 指副程式中若無定義變數, 則會參考執行副程式的敘數, 則會參考副程式定義時結數, 則會參考呼叫副程式時的述當時環境的變數值來取值構的層來取變數值環境來取變數值優執行效率 : 可直接參考活動可讀性 : 依照結構取值, 容彈性 : 可在執行時動態決定紀錄堆疊層決定變數值易理解推算變數值副程式中的變數值缺可讀性低 : 難以直觀判斷函數彈性低 : 程式設計師無法根據執行效能差 : 尋找變數定義必中的變數值, 程式維護難需求自動替換函數中的變數須沿動態鏈往找到呼叫處才值能決定 ( 二 )X 的輸出結果如下 : 1. 淺繫結 (Shallow Binding): 印出 4 sub1() 中敘述呼叫 sub3(), 而 sub3() 將 sub2() 視為參數傳入 sub4(), 在 sub4() 中的 subx() 即為 sub2(), 且 sub4() 中區域變數 x 值為 4, 故 sub2() 將 4 印出 2. 深繫結 (Deep Binding): 印出 1 sub1() 中經過一連串的呼叫到版 sub2() 權時所, 要有取 x 的, 值即重往 sub2() 製必的究層 (sub1()! 中 ) 取出區域變數 x 值為 1, 故將 1 印出 3. 特設繫結 (Ad-hoc Binding): 印出 3 sub1() 中敘述呼叫 sub3(), 而 sub3() 將 sub2() 視為參數傳入 sub4(), 在此同時, 也是程式調用 sub2() 之處, 故 sub2() 要取出 x 值的時候, 就會參考到此時 sub3() 中的 x 的值, 故印出 3-2 -

請根據述三種 binding 分別作答 (6 分 ) function subl() { var x; function sub2() {altert(x);} // 輸出 x function sub3() { var x; x=3; suh4(sub2);} function sub4(subx) { var x; x=4; subx();} x=l; sub3();};

3 104 公職地方特考分詳解四函數 f(n) 定義如下 :f(l)=1,f(0)=0,f(n)=f(n-2)+2f(n-l), 請問 f(5) 等於多少?(5 分 ) 本題為費式數列計算, 必須寫出計算過程, 若僅寫答案分數恐不理想由於題目較簡單, 應細心作答, 以免懊悔萬分考命中程式語言講義, 第二回, 金乃傑編撰, 頁 f(5) = 5 計算過程如下 : f(5) = f(3) + f(4) = = 5 f(4) = f(2) + f(3) = = 3 f(3) = f(1) + f(2) = = 2 f(2) = f(0) + f(1) = = 1 五對於字串的長度, 不同的語言有不同的設計方式, 包括 static length string limited dynamic length string dynamic length string:( 每小題 6 分, 共 12 分 ) ( 一 ) 請解釋述三種不同設計方式 ( 二 ) 對於 Java C 和 C++ 這三種語言, 它們對字串長度設計的方式各採取那種方式或混和? 本題為字串長度之題目以往雖有不同語言中字串的細部考題, 如 101 年警察 100 年普考 96 關務四等, 但今年的題型不僅較有結構, 而且還須說明三種語言的實作, 必須對每種語言的字串都有一定了解才能拿到分在答案撰寫面, 亦必須注意題意, 第一小題先條列寫出三種方法, 並配合舉例說明三種方法之用法背後可能的技術 ; 第二小題也應切合問題指出各採取哪種方式, 始能拿到分考命中 1. 程式語言講義第三回, 金乃傑編撰, 頁程式語言講義第四回, 金乃傑編撰, 頁 2 ( 一 ) 三種不同的設計方式說明如下 : 1. 靜態長度字串 (static length string): 字串在宣告時長度已決定, 且不能再修改例如 : 在 C 語言中以 char *s = hello world 宣告, 則此時 s 之長度就已經固定為 12 個 char 了 ( 包含最後一個結束符號 \0) 2. 有限可變長度字串 (limited dynamic length string): 字串在宣告時長度已決定, 但可能會預留一些空間以在未來存入更多字串例如 : 在 C 語言中以 char s[50] 宣告, 則 s 最大長度是 50, 但程式設計師可透過 strcpy(s, hello world ) 將較短的字串存入 3. 動態長度字串 (dynamic length string): 字串在使用時, 可以依照需求動態改變長度, 通常在實作時必須將字串型態定義為類別, 並透過宣告字串物件來建立因為字串為一個物件, 故內容可透過鏈結串列或參考到另一實際儲存字串的空間來儲存字元, 達到長度可動態變化 ( 二 ) 對於 Java C 與 C++ 三種語言所採取的方式說明如下 : 1.Java: 提供動態長度字串靜態長度字串在 Java 中字串為一類別, 宣告方法如 String s1 = new String( hello world ); 但另外也可以透過 String s2 = hello world 將字串定義為一常數若字串為常數時, 則字串為靜態長度 ( 儲存在 code segment) 但因 s2 為一個參考, 仍然可以透過 s2 = new String( Jack ) 等語法參考到其他字串物件, 引此長度的限制不會對程式造成影響 2.C 語言 : 提供靜態長度字串有線靜態長度字串在 C 語言中字串是使用字元陣列模擬而來, 因此若預先沒有宣告長度, 如 char *s1 = hello world 就為固定長度 ; 若預先宣告長度 char s2[50] 則為有限可變長度 3.C++: 提供靜態長度字串有線可變長度字串動態長度字串三種在 C++ 標準函式庫提供了 string 類別, 使用前要先 include <string> C++ 中建立 String 物件可透過 string - 3 -

5 f(4) = f(2) + f(3) = 1 + 2 = 3 f(3) = f(1) + f(2) = 1 + 1 = 2 f(2) = f(0) + f(1) = 0 + 1 = 1 五對於字串的長度, 不同的語言有不同的設計方式, 包括 static length string limited dynamic length string

4 104 公職地方特考分詳解 s1( hello world ) 來建立六給定下列的文法 (Grammar): <assign> <id> = <expr> <id>=a B C <cxpr> <expr>+<id> <expr>*<id> (<expr>) <id> 請畫出右列字串 :A = ((A*B)+C*A), 所對應 right-most derivation sequence 與對應的分析樹 (parse tree) (5 分 ) 本題為 104 身心障礙 104 關務 4 等 102 升官 101 地特 101 鐵路等的相似題, 若充分練習, 細心作答, 得到滿分絕非難事考命中 1. 程式語言講義第六回, 金乃傑編撰, 頁地方特考題神考前猜題程式語言重整理, 金乃傑編撰, 考 15 再次命中! ( 一 ) 最右推倒過程如下 : 1. <assign> 2. <id> = <expr> 3. <id> = (<expr>) 4. <id> = (<expr>*<id>) 5. <id> = (<expr>*a) 6. <id> = (<expr>+<id>*a) 7. <id> = (<expr>+c*a) 8. <id> = ((<expr>)+c*a) 9. <id> = ((<expr>*<id>)+c*a) 10. <id> = ((<expr>*b)+c*a) 11. <id> = ((<id>*b)+c*a) 12. <id> = ((A*B)+C*A) 13. A = ((A*B)+C*A) ( 二 ) 分析樹如下 : - 4 -

程式語言講義第六回, 金乃傑編撰, 頁 56-57 2. 地方特考題神考前猜題程式語言重整理, 金乃傑編撰, 考 15 再次命中! ( 一 ) 最右推倒過程如下 : 1. <assign> 2. <id> = <expr> 3. <id> = (<expr>) 4. <id> = (<expr>*<id>) 5.

5 104 公職地方特考分詳解七請計算下列式子最後的 y 值 :( 每小題 3 分, 共 15 分 ) ( 一 ) int x=3, y=2; y*= ++x + 3; ( 二 ) int x=3, y=2; y /= x++; ( 三 ) int x=10, y=l; y= x y; ( 四 ) int x=10, y=l; y /= ++x + y--; ( 五 ) int y=0; for(int k=0; k < 10; y+=k) { if(++k ==6) continue; k++;} 本題一到四小題為前置加 ( 減 ) 與後繼加 ( 減 ) 的題目, 作答時需掌握後繼會再敘述完成後再改變變數之值另外也需注意 *= 等指定運算子也優先順序比加減乘除還低, 因此必須等右手邊算式做完後才會展開帶入若能掌握這些原則搭配細心作答, 應能得分第五小題為迴圈求值的題目, 其考還是在其中的 if() 每次進迴圈都會判斷, 故 if() 中的 ++k 也會每次進迴圈都做, 故 k 的值都會被先加 1 考命中 1. 程式語言講義第一回, 金乃傑編撰, 頁地方特考題神考前猜題程式語言重整理, 金乃傑編撰, 考 3 再次命中! ( 一 )14 y *= ++x + 3; y *= y *= 7 y = y * 7 y = 2 * 7 y = 14 ( 二 )0 y /= x++ y /= 3 y = y/3 y = 2/3 = 但取整數部分 ( 無條件捨去 ), 故為 0 ( 三 )10 y = x y y = y = 10 ( 四 )-1 y /= ++x + y-- y /= y /= 12 y = y/12 y = 1/12 y = 0 在此敘述執行後, 因前有 y--, 會再將答案減 1, 故為 -1 ( 五 )30 原式可改寫為 : for(k = 0~9){ ++k; if(k == 6) continue; k++; y += k; - 5 -

也優先順序比加減乘除還低, 因此必須等右手邊算式做完後才會展開帶入若能掌握這些原則搭配細心作答, 應能得分第五小題為迴圈求值的題目, 其考還是在其中的 if() 每次進迴圈都會判斷, 故 if() 中的 ++k 也會每次進迴圈都做,

6 104 公職地方特考分詳解 } 每一圈 k 與 y 的值為 : 圈數 0( 初始狀態 ) k ( 下次會跳出迴圈 ) y 八若採取二種不同參數傳遞的方法 :pass by reference pass by value result, 執行下列程式, 則 x 與 y 的值各為多少?(8 分 ) int x=1, y=3; void fun(int a, int b); void main() { int x=2; fun(x, y); printf("x=%d, y=%d", x, y); } void fun(int a, int b) {a=b+x; b=a+y;} 本題為參數傳遞考題, 與 103 考 102 考 99 關務 94 地特相似, 但因有全域變數, 因此在作答時建議使用老師課所教之解題線, 較不會因為粗心而丟失分數另外值得注意的是今年考出多年未考的 pass by value result, 需掌握此法為使用 call by value 模擬 call by reference, 先做 call by value, 等副程式執行完後再將結果寫回, 故若副程式中沒有副作用, 則答案與 call by reference 相同考命中 1. 程式語言講義第二回, 金乃傑編撰, 頁地方特考題神考前猜題程式語言重整理, 金乃傑編撰, 考 7 再次命中! ( 一 )pass by reference 結果為 :x = 4, y = 7 global main fun x y x a b 參考到 main 的 x 運算式 :a = b + x global: y + global: x = 4( 與 main 的 x 同步 ) ( 二 )pass by value result 結果為 :x = 4, y = 7 global main fun x y x a b 數值 2 運算式 :a = b + x 3 + global: x = 4 ( 寫回 main) 參考到 global 的 y 運算式 :b = a + y 4 + global: y = 7( 與 global 的 y 同步 ) 數值 3 運算式 :b = a + y 4 + global: y = 7 ( 寫回 global) 九 ( 一 ) 如果有兩個整數 x,y, 請寫出相對應的副程式碼, 使得這兩數可以做交換 (5 分 ) ( 二 )T c[l0];int m=3, n=2;(t 為某種 type, 可能為 int float double 等 ), 請寫出相對應的副程式碼 swap, 當呼叫形式為 swap(c, m, n), 可讓 c[m] 跟 c[n] 的值做交換, 即使 T 的型態不同, 此程式一樣可以正確處理 (5 分 ) - 6 -

(8 分 ) int x=1, y=3; void fun(int a, int b); void main() { int x=2; fun(x, y); printf("x=%d, y=%d", x, y); } void fun(int a, int b) {a=b+x; b=a+y;} 本題為參數傳遞考題, 與 103 考 102 考 99 關務 94 地特相似,

7 104 公職地方特考分詳解本題為久未出現的 C 語言函數樣板題目, 與 97 年考類似若能掌握 C 語言函數樣板的語法, 並能熟悉 C 語言中陣列傳入函數的寫法, 此題應能迎刃而解考命中程式語言講義第四回, 金乃傑編撰, 頁 ( 一 ) 以 C++ 撰寫如下 : 註 : 此處使用 C++ 的傳參考呼叫, 寫起來最簡潔乾淨 ( 二 ) 以 C++ 撰寫如下 : 執行結果 : n 十利用 template 的概念, 寫出一個函數 power(x, n) 可以計算 x, 不管 x 為實數整數或自然數, - 7 -

115-117 ( 一 ) 以 C++ 撰寫如下 : 註 : 此處使用 C++ 的傳參考呼叫, 寫起來最簡潔乾淨 ( 二 ) 以 C++ 撰寫如下

8 104 公職地方特考分詳解但假設 n 為整數 (10 分 ) 本題配 10 分, 考除了 template 外, 還需實作次方雖 C++ 中有 Math 函式庫中的 pow() 可用, 但若使用了會使答案程式碼沒有內容 (pow() 已經很完整, 有 7 種多載, 也可以接受整數浮數雙倍精度浮數長整數等 ) 因此若要得到滿分, 除了必須自己用迴圈處理次方, 還必須要注意題目中提到的 n 為整數, 故 n 可能為負因此要考慮到 n 次方 n 為負數 0 或 1 的情形考命中程式語言講義第四回, 金乃傑編撰, 頁以 C++ 撰寫如下 : - 8 -

浮數長整數等 ) 因此若要得到滿分, 除了必須自己用迴圈處理次方, 還必須要注意題目中提到的 n 為整數, 故 n 可能為負因

6-1-1極限的概念

6-1-1極限的概念選修數學 (I-4 多項式函數的極限與導數 - 導數與切線斜率定義. f ( 在的導數 : f ( h 對實函數 f ( 若極限存在 h h 則稱 f ( 在點可微分而此極限值稱為 f ( 在的導數以 f ( 表示 f ( f ( 函數 f ( 在的導數也可以表成 f ( 註 : 為了