試題評析

Size: px

Start display at page:

Download "試題評析"

奚连邱
4 years ago
Views:

1 程式語言一請說明 early binding( 如 C 語言 ) 及 late binding( 如 Perl 語言 ) 之間最大的差異, 並列出兩者主要的優點 (10 分 ) 考點命中高點此題中的 late binding 相似於 100 檢事官 97 高考與 95 地特的考古題, 為實作, 屬於物件導向三大特性中多型的方法 ; 而 early binding 雖然單就名詞為第一次出現在國考中, 但因考古題中仍有不少比較, 應不難推斷出為編譯時期的繫節此題若有充分準備, 應可獲得不錯的分數高上程式語言第四回, 金乃傑編撰, 頁高上程式語言第三回, 金乃傑編撰, 頁高上程式語言總複習, 金乃傑編撰, 考點 19, 頁在程式語言中, 繫節 (Binding) 指的是將程式名稱與功能連結的動作, 而 Early Binding 即為早期繫結, 意指在編譯階段 (Compilation Phase) 進行繫節 ;Late Binding 則是在執行時期 (Runtime Phase) 才能進行繫節, 故最大差異為繫節時間因此如同 C 語言,Early Binding 在編譯階段即將函數的名稱與執行內容連結, 除了可以方便預測函數傳回的資料執行的結果外, 還可以讓編譯器對函數進行最佳化, 例如 : 將迴圈優化或配置適當的暫存器供函數使用而如 Perl 等語言,Late Binding 提供了多型 (Polymorphism), 在執行時期才會依照物件真實的型態決定要呼叫的函數實體例如 : 使用父類別容器裝入父類別物件與子類別物件, 透過容器執行則父類別物件時, 會呼叫父類別裡的方法 ; 執行子類別物件時則會執行子類別中的方法 ( 如下以 Java 展示, 假設 Triangle 繼承自 Shape) Shape s[] = new Shape[2]; s[0] = new Shape(); s[1] = new Triangle(); 使用 s[0].height() 與 s[1].height() 呼叫到不同的方法如此可以增加程式的彈性與可維護性, 使相同程式碼依照執行時真實物件提供不同操作模式, 也可以在需要時透過多型概念替換傳入物件, 在增加新功能時可以不會影響原始程式碼執行以表格比較差異如下 : 高上Early Binding Late Binding 繫節時間編譯時期執行時期主要優點 1. 提供編譯器極大的最佳化空間, 優化程式碼與暫存器配置 2. 可進行完整的檢查, 避免執行時期發生錯誤 3. 執行時期因不用再尋找定義因此效率較高 1. 提供多型 2. 增加程式彈性, 可以依照實際需求進行呼叫, 減少程式碼撰寫 3. 增加可維護性, 透過模組化抽換功能元件, 更新部分功能時不影響原有系統架構二參考下述 BNF grammar S S + S S - S S 版權所有 * S S / S,( S 重製必究 ) a! 請回答總共有幾個不同的剖析樹 (parse tree) 可得到下列結果本題不需畫出剖析樹, 但請說明 ( 每小題 5 分, 共 20 分 ) ( 一 )a + a * a ( 二 )a + a * a / a ( 三 )a + a + a + a ( 四 )(a + (a + a) ) + a

2 此題亦為考古題, 相似於 101 高考與 100 關務 4 等, 考驗同學畫出剖析樹的數量惟與前述兩題不同的是此題不必畫出所有剖析樹, 只要列出數量即可, 就難度與時間花費度而言應更為簡單若同學結合資料結構, 以樹型判斷能畫出樹有幾棵的概念, 小心謹慎作答, 應可獲得滿分考點命中高上程式語言第六回, 金乃傑編撰, 頁高上程式語言總複習, 金乃傑編撰, 考點 27, 頁高點剖析樹的數量是依照樹的形狀來判斷由於題目中 BNF 規則運算子符號為二元運算子, 且沒有優先順序, 因此可將 2 個節點視為 1 組, 剖析樹數量如下 : ( 一 ) 左斜右斜 = 2 棵 ( 二 ) 左斜左斜左斜右斜左右對稱右斜右斜右斜左斜 = 5 棵 ( 三 ) 左斜左斜左斜右斜左右對稱右斜右斜右斜左斜 = 5 棵 ( 四 ) 左斜 = 1 棵此題可以從樹的形狀切入, 第二三小題可以想成四個樹葉節點的樹有幾種形狀第四小題因為使用括號限制能夠展開的方向, 故只有一棵剖析樹三參考右圖類 C 語言的程式, 請依下列小題所述參數傳遞方式, 寫出執行程式 B 後之輸出結果 ( 每小題 10 分, 共 20 分 ) ( 一 )Y is passed by value. ( 二 )Y is passed by reference. 高上Program B ( ) { function A (X: integer) { X := X + 1; write (X, Y); var Y : integer; Y := 1; A (Y); write (Y); 考點命中參數傳遞方式同為考古題, 就題目結構使用 Pascal 語法, 在函數中宣告函數, 相似於 93 高考, 但只要掌握各參數傳遞方法及領域 (Scope) 的概念即可輕鬆作答, 謹慎的同學要拿到這 20 分應勢在必得 1. 高上程式語言第二回, 金乃傑編撰, 頁 7, 版權所有重製必究! 2. 高上程式語言第三回, 金乃傑編撰, 頁高上程式語言總複習, 金乃傑編撰, 考點 10, 頁假設 write() 印出資料內容後會換行 ( 一 ) passed by value 輸出結果如下 : 2, 1 1 ( 二 ) passed by reference 輸出結果如下 :

3 2, 1 2 四請用 Scheme 或 Lisp 等 Functional Programming Language 寫一個符合下述規範的遞迴函數 calculate 所寫的遞迴函數應該越簡潔越好 (20 分 ) (calculate A B C):A 是某函數 (function),b 是一整數 (integer),c 是任一數值 (va1ue), 由傳滿足 N >= B 且 (A N) = C 的最小整數 N 例如 (calculate list 0 (3)) 應回傳 3. (calculate (lambda (X) (> X 10)) 0 T) 應回傳 11. (ca1culate (lambda (X) (* X X)) 0 100) 應回傳 10. 高點本題要求用 Scheme 或 Lisp 寫出程式, 若沒有對函數型程式語言運作邏輯有充分的了解, 寫出符合題意的答案實屬困難但此題實為 93 高考相似題, 若能記得講義中 Scheme 介紹的常用函數如 define cond equv?... 的使用方法, 配合講義後之補充練習題的解題經驗, 應能仍從題目說明的回傳找到規則, 以遞迴概念處理回傳答案, 一樣可以寫出接近標準答案的結果考點命中 1. 高上程式語言第五回, 金乃傑編撰, 頁高上程式語言總複習, 金乃傑編撰, 考點 22, 頁以 Scheme 撰寫如下 : (define (calculate A B C) (cond ((equal? (A B) C) B) (else (calculate A (+ B 1) C)) ) ) 此程式以仿 C 語言撰寫如下 : calculate(a, B, C){ if(a(b) == C) return B; else return calculate(a, B+1, C); 切入點 : 依照題意要滿足 A(X) = C, 如 : 函數 A 結果 C 函數輸入 X list(x) (3) 3 lambda(x){ return (X > 10)?true:false true 最小 X 必須為 11 高上版權所有, 重製必究! lambda(x){ return X*X 因題目又提示輸入的 X 必須要大於等於 B, 所以我們可以用 B 每次加 1, 代到符合結果 C 為止再將此想法先以仿 C 語言遞迴呈現, 最後轉為 Scheme 語言可將上述 Scheme 程式至網站執行, 依序帶入察看結果 (calculate list 0 '(3)) (calculate (lambda (X) (> X 10)) 0 #T) (calculate (lambda (X) (* X X)) 0 100) 五請參考以下的 Java classes, 解釋下列各小題的語法是否正確, 如不正確請說明原因 ( 每小

4 題 5 分, 共 15 分 ) class X { public void x ( ) { class Y extends X { public void y ( ) { class Z extends Y { public void z ( ) { ( 一 )int count (Set<Y> s) { count (new TreeSet<Z> ( )); ( 二 )int count (Set<? extends Y> s) { count (new TreeSet<Z> ( )); ( 三 )lint count (Set<? super Z> s) {for (X a : s) a.x( );. ; 高點此題為 Java 的泛型 (Generics), 接近於 C++ 的樣板 (Template), 為新出現的題型, 若缺乏充分實務 Java 經驗, 應很難對泛型的使用方法及特性了解, 因此較難作答但課本第四回中有不少地方有提到相關的概念, 如 P.3 的資料結構介紹了 List 型態 Map 型態, 都有使用到泛型傳入 ;Java 與 UML 圖的 P 亦實際操作 LinkedList;P.85 C++ 的函數樣板課堂中亦有補充泛型之概念若能結合上述概念, 再配合函數參數傳遞與多型運作的知識, 充分準備的考生應有拿分機會考點命中高上程式語言第四回, 金乃傑編撰, 頁 3 85 高上 ( 一 ) 不正確在 count 中, 形式參數型態為 Set<Y>, 但實際參數型態為 TreeSet<Z>, 故可將問題簡化為 : Set<Y> s = new TreeSet<Z>(); 其中 <Y> 代表傳入型態必須要為 Y, 雖然 Z 繼承自 Y, 但 Z 仍與 Y 不同, 故不符合條件 ( 二 ) 正確在 count 中, 形式參數型態為 Set<? extends Y>, 但實際參數型態為 TreeSet<Z>, 故可將問題簡化為 : Set<? extends Y> s = new TreeSet<Z>(); 其中 <? extends Y> 代表傳入的型態必須要是 Y 的子類別, 而 Z 繼承自 Y,Z 是 Y 的子類別, 故符合條件 ( 三 ) 不正確在 Java 的泛型 (Generics) 中, 若沒有確切指定變數型態, 則必須要用 Object 作為變數型態, 故題目中函數將內 a 型態以 X 表示為錯誤的, 應改為 :for(object a: s) ((X) a).x(); 此題使用 Set 結構, 與課堂中介紹的 LinkedList 有異曲同工之妙由於 TreeSet 繼承自 Set, 用課文中相近語法比擬為 : TreeSet<X> s = new TreeSet<X>(); // 課文中 LinkedList 相近語法結合多型概念可改寫為 : Set<X> s = new TreeSet<X>(); // 考題中形式參數與實際參數對應另外題目類別中的函數若為建構函數, 則名稱必須與類別名稱大小寫相同且不須加上回傳型態六下述 Prolog 程式可推論圖形中 A 點到 B 點的可行性, 但是無法知道路徑請改寫該程式使其可以用 Prolog list 來記錄 A 點到版權所有 B 點的路徑若, A 點到不了重製必究 B 點,! 則回應 fail(false) 即可 (15 分 ) get_to (A, B) :- path (A, B). get_to (A, B) :- path (A, C), get_to (C, B). 本題為本試卷難度最高的一題, 要以 Prolog 撰寫程式, 並且還要操作串列型態, 若沒有 Prolog 的實戰經驗, 要寫出標準答案實屬困難但實際上解答所使用的元素亦在講義中介紹, 如 93 高考選擇題中的 append 函數 [H X] 的用法, 都可以在考古題中找到線索, 就高點學生而言, 若充分練習講義練習題, 仍可得到分數考點命中高上程式語言第五回, 金乃傑編撰, 頁

5 以 Prolog 撰寫, 將規則子句改寫如下 : get_to(a, B, P) :- path(a, B), append([a], [B], P). get_to(a, B, [A P]) :- path(a, C), get_to(c, B, P). 並加入以下規則子句 : append([], Y, Y). append([h X], Y, [H Z]) :- append(x, Y, Z). 若事實子句如下 : path(a, b). path(b, c). path(c, d). 則執行結果以下表展示 : 詢問回傳?- get_to(a, c, P). P = [a, b, c]?- get_to(c, a, P) false 高點高上題目中原始規則搭配解答中事實, 只會回傳 true 和 false 但題目要求必須要回傳路徑, 因此搭配 93 年高考的 append 方法, 將經過的原子串起來第一個敘述改寫為 : get_to(a, B, P) :- path(a, B), append([a], [B], P). 目的是將經過的路徑存在 P 中, 而 P 是由 append 將 A 與 B 連在一起產生的值得注意的是, 由於 A 與 B 都是原子, 不是串列但 append 是將兩個串列相連, 因此傳入 append 時, 必須先用中括號將 A 與 B 包起來變成原子如此 append 會將結果儲存在 P 中, 可再由 get_to 中的 P 去讀取傳回第二個敘述改寫為 : get_to(a, B, [A P]) :- path(a, C), get_to(c, B, P). 由於 get_to 已經被改寫為三個參數, 因此後面呼叫時也要把 P 傳入但值得注意的是形式參數的地方, 由於路徑必須要包括開始的原子, 所以將 [A P] 傳入, 如此 Prolog 會自動將 A 串在 P 串列的前面, 達到將首元素 A 也加入串列的功能版權所有, 重製必究!

運算子多載 Operator Overloading

運算子多載 Operator Overloading 多型 Polymorphism 講師 : 洪安 1 多型編譯時期多型 ( 靜態多型 ) function overloading 如何正確呼叫同名的函數? 利用參數個數與型態 operator overloading 其實同 function overloading 執行時期多型 ( 或動態多型 ) 如何正確呼叫不同物件的相同名稱的成員函數利用繼承與多型 2 子類別與父類別物件間的指定 (assignment)