加載中. ..
PDF
104年特種考試地方政府公務人員考試試題 代號：43860 全一張
（正面）
等別： 四等考試
類科： 資訊處理
科目： 程式設計概要
考試時間 ： 1 小時 30 分座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、請試述下列名詞之意涵：（每小題 4分，共 24 分）
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，它的 inorder sequence 為“maxengbyc”；它的 preorder sequence 為
“gamexncby”。
請將 T構建出來。（5分）
為何只給 preorder 與postorder 的結果，無法唯一決定出一棵二元樹？（3分）
104年特種考試地方政府公務人員考試試題 代號：43860 全一張
（背面）
等別： 四等考試
類科： 資訊處理
科目： 程式設計概要
九、請依下列程式求出 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 分）