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

請指出何以下列文法是混淆（ambiguous）的：（20 分） <S> -> <A> <A> -> <A> + <A>| <id> <id> -> a|b|c

程式語言（programming languages）可以用來描述計算（computations）。杜林機 （Turing machine）可以用來描述所有的計算（all computations）；也就是說，杜林 機可以用來撰寫所有可能的程式（programs）。一個程式語言至少需具備那些敘述 （statements）就可以用來撰寫所有可能的程式？（15 分）

UML（Unified Modeling Language）為設計一良好軟體程式所常必須使用之軟體 模型描述工具。請說明以下UML 中常用之靜態圖繪（static diagram）及動態圖繪 （dynamic diagram）在UML 中之功能為何？ class diagram（類別圖繪）object diagram（物件圖繪）deployment diagram （佈建圖繪）Use case diagram（使用狀況圖繪）Sequence diagram（序向圖繪） （25 分）

我們有下列的C/C++語言程序。 void f(n) int n; { if (n==1) printf(“*”); else if (n==2) printf(“***”); else { f(n-1); f(n-2); f(n-2); } } 假設a(n)是f(n)列印出的星號數目。請寫出一個程式，可以算出a(n)。這個程式必須具 有不可高於O(n)的複雜度。此外，請列出a(n)的遞迴方程式（recurrence equation）， 並寫出其解答。（25 分）

下列何種程式語言（可複選）使用變數（variable）：（10 分） 命令語言（imperative language） 函數語言（functional language） 邏輯語言（logic language） 物件導向語言（object-oriented language）

下列是一個Java 程式語言的程式片斷： x = x1 + x2; z = z1 + z2; 這裡x、x1 和x2 是int 變數，而z、z1 和z2 是class Complex 變數。請說明這兩個 設定敘述（assignment）的設定運算（assign operator）在語意（semantics）上有何 不同？（10 分）

void virtualReference ( const Obj &baseRef ) { baseRef.printname( ); cout << “ \n Area =” << baseRef.area( ) << “\n Volume = ” << baseRef.vol( ) << “\n Price = ” << baseRef.Price( ) << “\n\n”; } 假設某公司所處理之物品主要為圓盤物件，液體溶劑，以及長方體磚塊三種，請設 計三個類別（class）Plate，Liquid 及Cube 分別用以代表圓盤物件、液體溶劑、以 及長方體磚塊。並利用Virtual Class 設計類別Obj 以實作polymorphism，使得上面 所定之VirtualReference 可依所傳入之物品為圓盤物件，液體溶劑，或長方體磚塊分 別印出所需之不同資訊。其中baseRef.area( ) 必須印出物件之面積，baseRef.vol( ) 必須印出物件之體積，baseRef.Price( ) 必須印出物件之售價。任何物件若無某一特 質則需印出 0.0 。例如：若無面積，則印出Area = 0.0。在printname( )中，圓盤物 件要印出circular，液體溶劑印出liquid，長方體磚塊印出cubic。此三物品之特性及 必須印出之資訊分別為： Plate 具有半徑大小，其面積為3.14 乘半徑平方。無體積值。其售價（Price）為 5 倍面積大小。 其liquid 具有重量及密度，無面積值。體積為重量除以密度。其售價為2 倍重量 大小。 長方體磚塊具長、寬、高三特性，其面積為表面積大小（即2 倍的（長*寬+ 寬*高+高*長））。體積為長乘寬乘高（長*寬*高）。其售價為2 倍體積大小。 （25 分）

假設我們有一個下列的C/C++語言的資料結構。 struct node_type { int value; struct node_type *next; }; 請用這個資料結構，設計一個queue 的enqueue 與dequeue 程序。 struct node_type *enqueue(struct node_type *q, int v); 這個程序會把v 加到q 指到的queue 的尾端，並且把新的queue 傳回。 struct node_type *dequeue(struct node_type *q, int *vp); 這個程序會把q 指到的queue 頭的值，寫到*vp 中，然後把這個頭去掉，再把新的 queue 傳回。這兩個程序的complexity 都必須是O(1)，而且必須能處理空的queue。 你只能使用一個static pointer 變數。（25 分）

下面Java 程式片段中，寫出一個方法介面（method interface）（10 分）寫出類 別介面（class interface）（10 分）寫出呼叫建構子（constructor）而產生一個物件 叫myCar（5 分）寫出myCar 內的資料欄位（data fields）。（5 分） public class Cars { private String brand; private int engineSize; public Cars( ) {…} public int getEngineSize (int engineSize) {…} public boolean start ( ) {…} } // class Cars

許多語言的變數可能產生別名關係（aliasing）。 請解釋變數的別名關係。（5 分） 請舉一個程式範例說明。（5 分） 變數的別名關係會對程式產生什麼樣的影響？（5 分）

請問operator overloading 的用途為何？假設有X，Y 為2 陣列（array）變數，如果要 使得程式中可以利用此一指令Z=(X+Y)*2 將X 及Y 相加，結果乘以2 放回陣列Z。 請問要設計那些operator overloading 函式方可使Z=(X+Y)*2 正確完成上述功能？ （25 分） 96 年公務人員、關務人員升官等考試試題 類 科： 資訊處理 全一張 （背面）

我們有下列的BNF（Backus Naur Form）文法： S Æ a | S + S | S - S | M M Æ a | M * M | M / M | (S) 請問這個文法，是不是ambiguous。如果是的話，可以舉出一個例子嗎？如果不是 的話，請證明為什麼它不是ambiguous。（25 分）

在物件導向程式中，為何資料欄位通常要宣告為私用（private）？這與封裝 （encapsulation）有何關係？使用程式（user program）要如何取得某一資料 欄位，如上題的engineSize？（20 分）

變數一般有三種儲存方式：靜態（static）儲存方式、動態（dynamic or heap）儲存 方式和堆疊（stack）儲存方式。 請說明那一種儲存方式會產生垃圾（garbage）。（5 分） 請舉一個程式範例說明。（5 分） 請敘述任一個垃圾回收（garbage collection）機制。（10 分）

Memory leakage 所造成之錯誤在程式debug 階段往往無法即時查覺，因此為C++ 程式設計者所需特別留意的問題之一。請說明何謂 memory leakage？其造成的錯誤 原因為何？（13 分）以下程式片斷在數個地方會造成memory leakage，請修正其程 式內容。答案中請寫出被修正過之類別或函式（function）之完整內容，不需修正之 類別或函式無須再謄寫於答案中。（12 分） class Fruit{ private: double weight; char *color; public: Fruit(double, char *); virtual ~Fruit(); }; Fruit::Fruit(double w, char *col) { weight = w; color = new char[strlen(col)+1]; strcpy(color, col); } Fruit::~Fruit(){ delete color; } class Apple:public Fruit{ private: char *variety; public: Apple(double, char *, char *); ~Apple(); }; Apple::Apple(double w, char *col, char *var): Fruit(w,col) { variety = new char[strlen(var)+1]; strcpy(variety, var); } Apple::~Apple(){ delete variety; } main(){ Fruit *basket[20]; int i; double weight; char color[128], variety[128]; for(i=0; i<20; i++) basket[i] = new Apple(weight, color, variety); delete [] basket; }

UML 是Unified Modeling Language 的簡寫。請畫出一個家庭class（類別）的UML class diagram。這一個家庭class，要含有下列的特性（properties）：（25 分） ．家庭姓氏、家長姓名、地址、家庭電話。 ．家庭成員的資訊，包含了其姓名、性別、出生年月日、已婚還是未婚、與家長的關 係。 ．每個家庭成員若是已婚子女，還要有pointer 指到他現在與配偶組成的家庭object。 ．我們要有methods，可以增加家庭成員，可以刪除家庭成員，可以更改家長姓名， 可以改變子女的婚姻狀態。 ．另外，我們還希望有家庭的subclasses（次類別），其中一種是低收入戶家庭，我 們要記載他們每月的政府補貼金額。還有非低收入戶家庭，要記錄他們家的每年平 均稅率。 ．如果是低收入戶家庭，我們希望能夠有methods，可以查詢他們的每月政府補貼金額。 ．如果是非低收入戶家庭，我們也要有methods，可以在經濟不景氣時，申請成為低 收入戶家庭。

請寫出兩個類別D1 及D2，分別使下面的code( )回傳1 及2。（20 分） public abstract class A{ public abstract int code( ) ; public String message( ) {return “The code is” ;} } //class A

多型（polymorphic）函式是一種可以接受多種參數型態的函式。例如，在C++程式 語言，如果我們定義： template <class Type> Type min( Type a, Type b) { return a < b ? a : b; } 我們可以使用 min(10, 20); 及 min(10.0, 20.0); 多型函式有什麼好處？（5 分） 多型函式的定義一般是放在標頭檔（header file, .h）還是程式檔（source file, .cpp）？ （5 分） 為什麼？（10 分） 96 年交通事業公路人員升資考試試題 代號： 級 別： 員級晉高員級 科 別： 資訊管理、資訊處理 全一張 （背面） 10450、11650、 41650 六、請敘述物件導向程式語言（object-oriented programming languages）（如Java 或 Smalltalk）的程式設計模型（programming model）。（10 分） 請敘述函數式程式語言（functional programming languages）（如Lisp 或Scheme） 的程式設計模型。（10 分）