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

二、假設我們有一個下列的 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 分）

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

五、請描述何謂白箱測試（white-box testing）和黑箱測試（black-box testing） 。 （10 分）

四、請問下列 C 語言程式執行後的輸出為何？

8. student_func(&stu1);

7. stu1.last_name = "Donald";

6. if (stu1 == stu2) printf("Same Structure");

5. if (stu1.grade == stu2.grade) printf("Same Grade");

4. stu1 = stu2;

114年 - 114 公務升官等考試_薦任_資訊處理：程式語言#133261

114年 - 114 司法特種考試_三等_檢察事務官電子資訊組：程式語言#129571

113年 - 113 司法特種考試_三等_檢察事務官電子資訊組：程式語言#122108

112年 - 112 公務升官等考試_薦任_資訊處理：程式語言#117323

112年 - 112 司法特種考試_三等_檢察事務官電子資訊組：程式語言#116208

111年 - 111 司法特種考試_三等_檢察事務官電子資訊組：程式語言#110333

111年 - 111 身心障礙特種考試_三等_資訊處理：程式語言#107554

110年 - 110 公務升官等考試_薦任_資訊處理：程式語言#103744

110年 - 110 司法特種考試_三等_檢察事務官電子資訊組：程式語言#103229

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