104年 - 104年地方四等-程式設計概要#35322

科目：程式設計 | 年份：104年 | 選擇題數：0 | 申論題數：16

試卷資訊

所屬科目：程式設計

選擇題 (0)

申論題 (16)

⑴ AVL tree

⑵ Merge Sort

⑶ BNF Grammar

⑷ Dynamic Scope

⑸ Dynamic Linker

⑹ Heap-dynamic Variable

二、int a; 則變數 a 最小值與最大值分別為何？（3 分）

三、定義一個函數如下：

int f(int n) { if( n==0) return 0; if( n== 1) return 1; if( n==2) return 2;
return f(n-1)+f(n-2)+f(n-3); }
請問計算 f(6)時，共呼叫 f(n)幾次？（8 分）

四、有 C 程式如下，請寫出函數 add()正確的函數定義，輸入為一個二維 array，輸出為一整數值。（8 分） void main() { int a[12][15], sum; sum=add(a, 12, 15); }

五、若有 N 個資料，每次做資料處理時都需選最大，請依下列資料結構：unordered linked list、sorted array 及 heap，分別寫出這些資料作 insert 及 delete 時的時間複雜度。（12 分）

六、假設有一個演算法，它的計算量可寫成如下的遞迴式 T(n)= T(n-1)+ 1/ n，T(1)=1，請問此演算法的時間複雜度為何？（8 分）

七、請用非遞迴的方式，寫出一副程式 gcd(int m, int n)，藉以求出兩整數 m 與 n 之間的最大公因數。（8 分）

⑴請將 T 構建出來。（5 分）

⑵為何只給 preorder 與 postorder 的結果，無法唯一決定出一棵二元樹？（3 分）

九、請依下列程式求出 x 與 y 的值。（9 分）
int x=0, y=0;
for(int i=0;i＜100;i++)
for(int j=i+1;j＜100;j++)
{ x++;
for(int z=j+1; z＜=100;z++) y++;
}

十、請用遞迴的方式，寫出 quicksort(int *A, 0, n-1)的副程式，利用 quicksort 的演算法，將 A 陣列裡的 n 筆資料，從小排到大。（12 分）