阿摩線上測驗
登入
首頁
>
程式語言
> 96年 - 96 高等考試_三級_資訊處理:程式語言#34463
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,可以在經濟不景氣時,申請成為低 收入戶家庭。