102年 - 金門縣102 學年度國民中學正式教師暨代理代課教師甄試26~50#10579

科目：教甄◆電腦科專業 | 年份：102年 | 選擇題數：25 | 申論題數：0

試卷資訊

所屬科目：教甄◆電腦科專業

選擇題 (25)

26. 下列C 語言程式片段執行結果為何?
void fun2(int a , int *b)
{
if(a<=1) return;
else {
*b *= 2;
fun2(a-1,*b);
}
}
int main(void)
{
int a=5,b=6;
fun2(a, &b);
printf(“%d\n”,b);
}
(A)6 (B)12 (C)24 (D)48
27. 設有N 筆不同的數被建立成一個包含N 個節點的二元搜尋樹(Binary search tree)，則尋找特定一筆特定的數最多需做幾次數值比較？ (A)1 次 (B)logN 次 (C)N 次 (D)NlogN 次
28. 下別C 程式碼的輸出為何？
int i, j, temp, a[10]={1,2,3,4,9,8,7,6,5};
for(i = 0; i < 10; i++)
for(j = i; j < 10; j++)
if(a[i]>a[j]){
temp=a[i]; a[i]=a[j]; a[j]=temp;
}
for(i = 0; i < 10; i++)
printf("%d ",a[i]);
(A) 9 8 7 6 5 4 3 2 1 0 (B) 0 1 2 3 4 5 6 7 8 9 (C) 1 2 3 4 9 8 7 6 5 (D)以上皆非
29. 有10 個點P1,...,P10 座標如下： P1=(0,0), P2=(0,10), P3=(10,0), P4=(11,11), P5=(1,3), P6=(2,5), P7=(4,6), P8=(5,7), P9=(7,8),P10=(8,9).請問這些包含這些點且以其中一些點為頂點形成的最小凸多邊形有幾個邊？ (A)3 (B)4 (C)5 (D)6
30. 一個高度為h的完整二元樹(complete binary tree)有幾個內部節點？ (A)2^h (B)2^ (h-1) (C)2^h +1 (D)2^h -1
31. 執行下列程式片段，其結果為何？
solution(6);
float solution(int n)
{
if (n == 0)
return 1;
else if (n == 1)
return (2 * solution(n-1));
else if (n == 2)
return (3 * solution(n-2));
else
return (n * solution(n-1));
}
(A)720 (B)1080 (C)1440 (D)2160
32. 給一二元樹(binary tree)，已知這樹的preorder(前序)traversal為A, B, C, D, E。inorder(中序) traversal為B, A, D, C, E。請問它的postoder(後序)traversal為何? (A)B, C, E, D, A (B)B, E, D, C, A (C)B, D, E, C, A (D)B, C, D, E, A
33. 以下程式印出的結果為何?
#include <stdio.h>
void swap(int a, int b){
int temp;
temp = a; a=b; b=a;
}
int main(){
int a=5, b=10;
swap(a,b);
printf("%d,%d\n",a,b);
}
(A)5,10 (B)10,5 (C)10,10 (D)5,5
34. 在一個只使用{1, 2, 3, 4, 5, 6}這六個數字的算術運算中，若此運算式的後序表示法(postfix expression)為2 6 * 1 +3 4 * - 5 2 * +，請問其值為何？ (A)10 (B)11 (C)17 (D)30
35. 有一個函式 Compute 定義如下:
int Compute (int x )
{
if (x<1)
return (1);
else if (x=1)
return (3);
else
return (5*Compute(x-1)-6*Compute(x-2));
}
當執行Compute(4)時，其結果為何？
(A)9 (B)81 (C)195 (D)211
36. 下列有關程式設計語言的描述何者正確？ (A)對於同樣的程式，通常以高階語言撰寫其執行效率比以低階語言撰寫之執行效率高 (B)對於同樣的程式，通常以低階語言撰寫其執行效率比以高階語言撰寫之執行效率高 (C)低階語言程式語法與一般英文相似，因此也稱之為命令稿語言(scripting language) (D)命令稿語言是用來撰寫網頁的語言
37. 泡沫排序法(Bubble sort)在最佳狀態(best case)下的時間複雜度為何？ (A)O(1) (B)O(logN) (C)O(N) (D)O(NlogN)
38. 將1, 2, 3, 4, 5依序加入一棵原先空的二元搜尋樹(binary search tree)後，對該樹進行後序拜訪(postorder traversal)得到的順序為何？ (A)1 2 3 4 5 (B)5 4 3 2 1 (C)1 2 4 3 5 (D)3 5 1 2 4
39. 將一個 binary heap (二元堆) 以 array (矩陣) A 表示如下：[3, 8, 4, 13, 23, 12, 24, 43, 38]。一開始先將23 減少為1，然後再把最小的數刪除，最後插入7。請問最後13 的高度在第幾層？(假設樹根為第1 層) (A)1 (B)2 (C)3 (D)4
40. 假設有一個postfix運算式A B + C / C D + A * – ，而其起始值為A=3，B=6，C=3，D=2。該運算式執行之結果為何？ (A)-6 (B)-9 (C)-12 (D)-15
41. 下列何者為遞迴關係式T(n) = T(9n/10)+T(n/10)+ Θ(n)之漸近解？ (A)Θ (n) (B)Θ (n^2) (C)Θ (lgn) (D)Θ (nlgn)
42. 假設A[1…5, 1…6, 1…6]為三維陣列(3-dimensional array)，其中每個元素是以列為優先(row-major)的排列方式儲存在電腦的記憶體中。若A 的每個元素佔1 個記憶體位置，且已知A[4,6,6]儲存位址為300，請問此陣列中的元素A[2,5,3]會被存在放那個位址？ (A)157 (B)177 (C)219 (D)244
43. 以下我們假設a 是任一大於1 的正整數並以符號 " **" 代表指數運算，計算a**8 的值須要3 次乘法，即先算出T=a*a然後再計算T*T*T 就可以得到a^8 的值。試問計算a**29 至少須要做幾次乘法運算才能算出答案？ (A)5 (B)6 (C)7 (D)8
44. 依據下列C 語言程式碼，執行cat(12)所需要的乘法次數是多少？
int cat ( int num )
{
int k = 0;
int temp = 0;
if ( ( num == 0 ) || ( num == 2 ) ) {
return 1;
}
else {
for( k ; k < num ; k+=2 ) {
temp += cat( k ) * cat( num - k – 2 );
}
return temp;
}
}
(A)192 (B)186 (C)202 (D)196
45. 若每次呼叫亂數函數Random_Bit()均可取得一個位元的亂數值，此值為1 的機率為p (0 < p < 1/2)，則以下函數Random_Bit_Plus()輸出1 的機率為何？ Procedure Random_Bit_Plus() Begin While (True) do { X Random_Bit() Y Random_Bit() If (X Y) Then return X} End (A)p (B)1-p (C)p(1-p) (D)1/2
46. 假設有63個數用快速排序法 (quick sort) 排序，那麼在最好的情形下要做幾次比較(比較次數最少為幾次)： (A)62 (B)258 (C)63×62/2 (D)6
47. 已知矩陣X 有s 個欄r 個列，矩陣Y 有t 個欄s 個列，則在矩陣乘法中，XY 的執行時間為 rst ；現有另一個矩陣 Z，其共有u 個欄與t 個列，則下列哪一個關係滿足時，可以確保 (XY)Z 運算的執行時間會比 X(YZ) 快？ (A)1/s + 1/u < 1/r + 1/t (B)s > t (C)1/r + 1/s < 1/t + 1/u (D)r + s > t + u
【已刪除】48. 假設要排序 n 個數字，且每個數字的範圍介於 1 到 n 之間，請問下列何者敘述不正確？ (A)使用 Heap Sort 可在 O(n log n) 的時間複雜度完成 (B)使用 Radix Sort 可在 O(n) 的時間複雜度完成 (C)使用 Merge Sort 最壞的情況下需要 O(n log n) 的時間複雜度，但根據輸入的不同，有可能在某些情況下達到更快的時間複雜度 (D)使用 Quick Sort 在最壞的情況下會需要 Θ (n^2) 的時間複雜度
49.一個穩定(stable)排序法是指當資料中有兩筆資料d1 及d2 在排序的屬性具有相同的值時，若在排序進行前，d1 的位置出現在d2 之前，則進行該排序演算法進行後d1 的位置必出現在d2 之前。請問下列何者不是穩定排序法? (A)插入排序法(insertion sort) (B)選擇排序法(selection sort) (C)泡沫排序法(bubble sort) (D)合併排序法(merge sort)
50. 有一堆疊 (stack) 存放七筆資料，依序為G、F、E、D、C、B、A，堆疊頂端的資料為A。令X(S) 表示將資料S 存入該堆疊，Y 表示從該堆疊取出一筆資料，則依序執行Y、Y、X(S)、X(S)、X(S)、Y、Y、X(S)、Y 後、該堆疊頂端的資料為何？ (A) C (B) D (C) E (D) S

申論題 (0)