96年 - 96 高等考試_三級_資訊處理：程式語言#34463

科目：程式語言 | 年份：96年 | 選擇題數：0 | 申論題數：4

試卷資訊

所屬科目：程式語言

選擇題 (0)

申論題 (4)

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