申論 1我們有下列的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 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2假設我們有一個下列的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 分）
申論 3我們有下列的BNF（Backus Naur Form）文法：S Æ a | S + S | S - S | MM Æ a | M * M | M / M | (S)請問這個文法，是不是ambiguous。如果是的話，可以舉出一個例子嗎？如果不是的話，請證明為什麼它不是ambiguous。（25 分）
申論 4UML 是Unified Modeling Language 的簡寫。請畫出一個家庭class（類別）的UMLclass diagram。這一個家庭class，要含有下列的特性（properties）：（25 分）．家庭姓氏、家長姓名、地址、家庭電話。．家庭成員的資訊，包含了其姓名、性別、出生年月日、已婚還是未婚、與家長的關係。．每個家庭成員若是已婚子女，還要有pointer 指到他現在與配偶組成的家庭object。．我們要有methods，可以增加家庭成員，可以刪除家庭成員，可以更改家長姓名，可以改變子女的婚姻狀態。．另外，我們還希望有家庭的subclasses（次類別），其中一種是低收入戶家庭，我們要記載他們每月的政府補貼金額。還有非低收入戶家庭，要記錄他們家的每年平均稅率。．如果是低收入戶家庭，我們希望能夠有methods，可以查詢他們的每月政府補貼金額。．如果是非低收入戶家庭，我們也要有methods，可以在經濟不景氣時，申請成為低收入戶家庭。