阿摩線上測驗
登入
首頁
>
程式設計
> 104年 - 104年地方四等-程式設計概要#35322
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 分)