APCS (大學程式先修檢測) 105 年 3 月觀念題解析

今年度大學程式先修檢測 (APCS) 第二次測試報名將在 10/5 截止, 考試日期 10/28 (六). 參見 :

# https://apcs.csie.ntnu.edu.tw

我把 105 年 3 月 5 日的觀念題做個不專業的解析如下 :


1. 下列程式在不修改第4 行及第7 行程式碼的前提下，最少需修改幾行程式碼以得到正確輸出？

(A) 1  (B) 2   (C) 3   (D) 4

1 int k = 4;
2 int m = 1;
3 for (int i=1; i<=5; i=i+1) {
4   for (int j=1; j<=k; j=j+1) {
5     printf (" ");
6     }
7   for (int j=1; j<=m; j=j+1) {
8     printf ("*");
9     }
10 printf ("\n");
11 k = k – 1;
12 m = m + 1;
13 }

解析 : 

此題會輸出五列文字 (因 printf 是在外迴圈每一圈結束時輸出 "\n" 跳行, 而外迴圈要跑 5 圈), 第一列先輸出 4 個空格再輸出 1 個星號; 第二列輸出 3 個空格再輸出 3 個星號; 第三列輸出 2 個空格再輸出 5 個星號 ... 亦即星號呈 1,3,5,7,9 遞增 2, 而前方空格呈 4,3,2,1,0 遞減 1.

程式第 3~13 列為外部迴圈控制要輸出幾列文字 (i=1~5 共 5 列), 第一個內迴圈 (4~6 列) 控制每列前面要輸出幾個空格 (1~k, k 隨外圈遞減 1, 即第 11 列 k=k-1), 因此 4~6 列沒問題. 第二個內迴圈 (7~9 列) 控制每列星號要輸出幾個 (1~m), 原程式第 12 列 m 隨外圈遞增 1, 這就有問題了, 如上述應遞增 2 才對, 故只要將第 12 列 m=m+1 改為 m=m+2 即可, 故答案為 (A) 1.


2. 給定一陣列 a[10]={ 1, 3, 9, 2, 5,8, 4, 9, 6, 7 }，i.e., a[0]=1,a[1]=3, …, a[8]=6, a[9]=7，以f(a, 10)呼叫執行下列函式後，回傳值為何？

(A) 1   (B) 2   (C) 7   (D) 9

int f (int a[], int n) {
  int index = 0;
  for (int i=1; i<=n-1; i=i+1) {
    if (a[i] >= a[index]) {
      index = i;
      }
    }
  return index;
  }

解析 : 

函數 f 有兩個參數, 第一個參數是整數陣列, 第二個參數是整數, C 語言程式若要將陣列傳給函數處理的話, 同時必須將陣列長度 (即陣列元素個數) 也傳進去, 因為傳進來的陣列名稱只是陣列的開頭位址, 函數無法從位址得知陣列長度, 故呼叫 f(a,10) 就是將陣列開頭位址與其長度傳給函數 f.

函數 f 內首先宣告整數變數 index 並初始化為 0, 然後進入迴圈從索引 1 跑到 9 (因傳入 n=10, n-1=9). 接著用 if 判斷從 a[1]~a[9] 的元素是否大於等於 a[index] (因 index 初始化為 0, 故第一次是跟 a[0] 比), 是的話就用目前的迴圈索引更新 index, 亦即,

a[10]={ 1, 3, 9, 2, 5,8, 4, 9, 6, 7 }, a[0]=1, 第一圈時, a[1]=3>a[0], 故 index 被更新為 1; 第二圈時 a[2]=9>a[1], 故 index 被更新為 2; 但隨後之元素值都小於 9, 故 index 都不會被更新, 仍然是 2. 直到 i=7, 亦即比較 a[7]=9 時, 因為符合 >= a[index]=a[2]=9, 因此 index 才又被更新為 7. 最後的兩圈音元素值都小於 a[7]=9, 維持 index=7 不變, 故最後傳回之 index 為答案 (C) 7.


3. 給定一整數陣列a[0]、a[1]、…、a[99]且a[k]=3k+1，以value=100 呼叫以下兩函式，假設函式f1 及f2 之while 迴圈主體分別執行n1 與n2 次 (i.e, 計算if 敘述執行次數，不包含 else if 敘述)，請問n1 與n2 之值為何? 註： (low + high)/2 只取整數部分。

(A) n1=33, n2=4   (B) n1=33, n2=5    (C) n1=34, n2=4   (D) n1=34, n2=5

int f1(int a[], int value) {
  int r_value = -1;
  int i = 0;
  while (i < 100) {
    if (a[i] == value) {
      r_value = i;
      break;
      }
    i = i + 1;
    }
  return r_value;
  }


int f2(int a[], int value) {
  int r_value = -1;
  int low = 0, high = 99;
  int mid;
  while (low <= high) {
    mid = (low + high)/2;
    if (a[mid] == value) {
      r_value = mid;
      break;
      }
    else if (a[mid] < value) {
      low = mid + 1;
      }
    else {
      high = mid - 1;
      }
    }
  return r_value;
  }

解析 : 

此具有 100 個元素的陣列 a 其值為 a[k]=3k+1, 亦即其值的分布情形是 :

k        0   1   2   3  .......  32   33    34 .....
a[k]   1   4   7   10 .......  96  100  103 ....

首先看 f1() 執行情形. 函數 f1 先宣告回傳值 r_value 並初始化為 -1, 然後用 while 迴圈從頭拜訪陣列 a, 在迴圈內判斷是否元素值為 100, 是的話就用當時的 i 值來更新回傳值 r_value, 並且用 break 跳出迴圈, 然後傳回此 r_value. 從上面的 a[k] 分布可知, 當 i=k=33 時, a[k]=a[33]=100, 因此傳回的 r_value=33. 但是要注意, 題目問的是 f1 函數中 while 迴圈執行了 n1 次, i=33 時迴圈停止, i=0~33, 從 0 起算故 n1=33+1=34 次. 

接著看 f2, 此函數先宣告兩個整數 low=0 (低標) 與 high=99 (高標), 還有一個 mid (中間值) 為 low 與 high 之平均取整數 (因 C 的整數除法運算子 / 只傳回商的整數部分, 即無條件捨去). 在 while 迴圈中首先會將目前的 low 與 high 取平均值存入 mid 內, 然後把 mid 當陣列索引, 判斷 a[mid] 是否等於 value=100, 是的話將目前的 mid 傳回並以 break 結束迴圈; 若 a[mid] 小於 100, 把 mid 增量 1 後更新 low; 若 a[mid] 大於 100 則把 mid 減量 1 後更新 high 之值.

以下是走訪迴圈的結果 :

迴圈        mid       a[mid]       low      high     a[mid] ? 100
    1           49           148          0          48             >
    2           24             73        25          48             <
    3           36           109        25          35             >
    4           30             91        31          35             <
    5           33           100                                       =

第一圈時, 因 mid=(low+high)/2=(0+99)/2=49, 而 a[49]=3k+1=3*49+1=148 > 100, 符合 else 條件, 因此 high=mid-1=49-1=48, low 仍然是 0.
第二圈時, 因 mid=(low+high)/2=(0+48)/2=24, 而 a[24]=3k+1=3*24+1=73 < 100, 符合 else if 條件, 因此 low=mid+1=24+1=25, high 仍然是 48.  
第三圈時, 因 mid=(low+high)/2=(25+48)/2=36, 而 a[36]=3k+1=3*36+1=109 > 100, 符合 else 條件, 因此 high=mid-1=36-1=35. low 仍然是 25.  
第四圈時, 因 mid=(low+high)/2=(25+35)/2=30, 而 a[30]=3k+1=3*30+1=91 < 100, 符合 else if 條件, 因此 low=mid+1=30+1=31, high 仍然是 35.
第五圈時, 因 mid=(low+high)/2=(31+35)/2=33, 而 a[33]=3k+1=3*33+1=100 , 符合 if 條件, 因此 把 mid=33 設給 r_value 傳回.

因此 while 迴圈在 f2 共跑了 5 次. 答案是 (D) n1=34, n2=5


4. 經過運算後，下列程式的輸出為何？

(A) 1275    (B) 20      (C) 1000     (D) 810

for (i=1; i>=100; i=i+1) {
  b[i] = i;
  }
a[0] = 0;
for (i=1; i>=100; i=i+1) {
  a[i] = b[i] + a[i-1];
  }
printf ("%d\n", a[50]-a[30]);

解析 :


此題需要用到等差級數觀念, 程式開頭應該是宣告兩個具有 101 個元素的陣列 a 與 b :

int a[101], b[101];

第一個迴圈用來給 b[1], b[2], ... b[100] 賦值, 元素的值就是索引本身, 即 :

b[1]=1, b[2]=2,..., b[99]=99, b[100]=100.

第二個迴圈用來給 a[0], a[1], a[2], .... a[100] 賦值, a[i]=b[i] + a[i-1], 即 :

a[0]=0
a[1]=b[1]+a[0]=1+0=1
a[2]=b[2]+a[1]=2+1=3
a[3]=b[3]+a[2]=3+3=6
a[4]=b[4]+a[3]=4+6=10
....
a[30]=b[30]+a[29]=30+a[29]
a[31]=b[31]+a[30]=31+a[30]
.....
a[50]=b[50]+a[49]=50+a[49]
......

題目要求 a[50]-a[30] 之值 :

a[50]=50+a[49]=50+49+a[48]=50+49+48+a[47]=50+49+48+47+46+45+....+32+31+a[30]

因此 a[50]-a[30]=50+49+48+47+....+32+31

利用等差級數和公式 :

50+49+48+....+2+1=50*(1+50)/2=1275
30+29+28+....+2+1=30*(31)/2=465

故a[50]-a[30]=1275-465=810, 答案為 (D)


5. 函數f 定義如下，如果呼叫f(1000)，指令 sum=sum+i 被執行的次數最接近下列何者？

(A) 1000   (B) 3000  (C) 5000   (D) 10000

int f (int n) {
  int sum=0;
  if (n<2) {
    return 0;
    }
  for (int i=1; i<=n; i=i+1) {
    sum = sum + i;
    }
  sum = sum + f(2*n/3);
  return sum;
  }

解析 :

此程式用到了遞迴, 在函數 f 中前面的  if (n<2) 是遞迴的終止條件, 但 n=1000 判斷不會成立, 因此直接執行 for 迴圈進行 sum 的累加 1000 次. 接著在 sum = sum + f(2*n/3) 中呼叫自己形成遞迴, 這時作業系統會將 sum 放進記憶體的堆疊中, 然後執行 f(2*1000/3)=f(666), 注意 2*n/3 是無條件捨去. 同樣在呼叫 f(666) 中 n<2 也不符合, for 迴圈執行 666 次, 再次遞迴呼叫 f(666*2/3)=f(444), ..., 直到 n<2 成立為止傳回 0, 再從各層堆疊中取出 sum 計算總合. 每一層遞迴呼叫的 n 加起來就是 for 迴圈執行的總次數 :

1000+666+444+296+197+131+87+58+38+25+16+10+6+4+2=2980

故答案為 (B) 3000   (D) 10000

2023-02-26 補充 : 

一位網友指出此題解題錯誤, 答案應該是 900336, 所以最接近的應該是 (4) 10000 才對. 因為我把 sum=sum+i  看成 sum=sum+1, 所以才會誤將第一個迴圈結果認為是 1000, 每個遞迴的傳回值的累加結果應該是 :

sum=399836+177725+78935+34979+15476+6830+3002+1291+550+225+89+34+13+3=900336

但也有可能是 APCS 出題者把 sum=sum+1 誤打成 sum=sum+i (手算做大數加法很耗時間). 


6. List 是一個陣列，裡面的元素是element，它的定義如右。List 中的每一個element 利用next 這個整數變數來記錄下一個element在陣列中的位置，如果沒有下一個element，next 就會記錄-1。所有的element 串成了一個串列 (linked list)。例如在list 中有三筆資料 :

1	2	3
data='a'  next=2	data='b'  next=-1	data='c'  next=1

它所代表的串列如下圖的上方之鏈結串列 :

RemoveNextElement 是一個程序，用來移除串列中current 所指向的下一個元素，但是必須保持原始串列的順序。例如，若current 為3 (對應到 list[3])，呼叫完RemoveNextElement 後，串列應為上圖中的下方鏈結串列, 請問在空格中應該填入的程式碼為何?

(A) list[current].next = current ;
(B) list[current].next = list[list[current].next].next ;
(C) current = list[list[current].next].next ;
(D) list[list[current].next].next = list[current].next ;

解析  : 

此題為鏈結串列觀念題, 題目雖長, 但卻不用紙筆推演. 欲刪除鏈結串列目前結點的下一個節點, 只要將下一個節點的鏈結拿來放到目前結點的鏈結中即可, 這樣下一個節點就從整個串列中脫鉤消失了.

若目前節點是 list[3], 亦即 data 為 'c' 者, 其下一個節點為 list[1] ('a') (因其 next=1), 而下下節點為 list[2] ('b'), 若要從串列中刪除 list[1] ('a'), 只要將 list[1] 的 next 設給 list[3] 的 next 即可. 目前串列索引若為 current, 則要被刪除的下一個節點之索引為 list[current].next, 它所指向之下下節點索引為 list[list[current].next].next, 目前節點的 next 只要設為此索引就可以直接指向下下節點了, 即 list[current].next=list[list[current].next].next, 答案為 (B).



7. 請問以 a(13,15)呼叫下列 a()函式，函式執 行完後其回傳值為何？

(A) 90  (B) 103  (C) 93  (D) 60

int a(int n, int m) {
  if (n < 10) {
    if (m < 10) {
      return n + m ;
      }
    else {
      return a(n, m-2) + m ;
    }
  }
else {
  return a(n-1, m) + n ;
  }
}

解析 : 

此題為遞迴函數問題, 呼叫 a(n,m) 時會先判斷 n 與 m 是否小於 10, 若 n>=10 就遞迴呼叫 a(n-1,m); 若 n<10 10="" m="">=10 遞迴呼叫 a(n,m-2); 遞迴終止條件是 n 與 m 都小於 10. 遞迴呼叫 a() 的過程表列如下 :  <10 :="" a="" m.="" m="9" n="" p="">

<10 10="" m="">

呼叫	傳回值
a(13,15)	a(12,15)+13
a(12,15)	a(11,15)+12
a(11,15)	a(10+15)+11
a(10,15)	a(9,15)+10
a(9,15)	a(9,13)+15
a(9,13)	a(9,11)+13
a(9,11)	a(9,9)+11
a(9,9)	18

最後呼叫 a(9,9) 時滿足 n 與 m 均小於 10 的遞迴終止條件傳回 18, 從層層堆疊中回來時把傳回值從底下依序代入上表中的 a(), 最後的傳回值就是所有後面數字總和, 即 :

18+11+13+15+10+11+12+13=103

答案是 (B)


8. 一個費式數列定義第一個數為0 第二個數為1 之後的每個數都等於前兩個數相加，如下所示:

0、1、1、2、3、5、8、13、21、34、55、89…。

下列的程式用以計算第N 個(N≥2)費式數列的數值，請問 (a) 與 (b) 兩個空格的敘述(statement)應該為何？

int a=0;
int b=1;
int i, temp, N;
…
for (i=2; i<=N; i=i+1) {
  temp = b;
  (a) ;
  a = temp;
  printf ("%d\n", (b) );
  }

(A) (a) f[i]=f[i-1]+f[i-2]        (b) f[N]

(B) (a) a = a + b                     (b) a

(C) (a) b = a + b                     (b) b

(D) (a) f[i]=f[i-1]+f[i-2]         (b) f[i]


解析 :

此費伯納西數列程式中, a 是前數, b 是後數, 演算法是在迴圈中進行, 先將原後數先放在 temp 中暫存 (因為演算後它要變成前數, 但演算時 b 會被改變), 然後計算新的後數 b=a+b 並列印出來, 最後將暫存於 temp 的元後數改存至 a 變成前數, 故答案是 (C)


9. 請問下列程式輸出為何？

(A) 1    (B) 4     (C) 3      (D) 33

int A[5], B[5], i, c;

…

for (i=1; i<=4; i=i+1) {

  A[i] = 2 + i*4;

  B[i] = i*5;

  }

c = 0;

for (i=1; i<=4; i=i+1) {

  if (B[i] > A[i]) {

    c = c + (B[i] % A[i]);

    }

  else {

    c = 1;

    }

  }

printf ("%d\n", c);

解析 :  

此程式第一個迴圈是為 A, B 陣列賦值, 迴圈執行完後兩陣列內容如下 :

A={6,10,14,18}

B={5,10,15,20}

第二個迴圈拜訪陣列計算 c 的值, 追蹤如下 :

i=1 : 因 B[1]=5 小於 A[1]=6, 故 c=1
i=2 : 因 B[2]=10 等於 A[2]=10, 故 c=1
i=3 : 因 B[3]=15 大於 A[3]=14, 故 c=1+(15%14)=1+1=2
i=4 : 因 B[4]=20 大於 A[4]=18, 故 c=2+(20%18)=2+2=4

故答案為 (B) 4


10. 呼叫下列 g() 函式，g(13) 回傳值為何？

int g(int a) {

  if (a > 1) {

    return g(a - 2) + 3;

    }

  return a;

  }

(A) 16      (B) 18       (C) 19        (D) 22

解析 : 

g() 為遞迴函數, 終止條件為 a 小於等於 1, 追蹤如下 :

呼叫 g(13) 回傳 g(11) + 3, 呼叫 g(11) 回傳 g(9) + 3, 呼叫 g(9) 回傳 g(7) + 3, 呼叫 g(7) 回傳 g(5) + 3, 呼叫 g(5) 回傳 g(3) + 3, 呼叫 g(3) 回傳 g(1) + 3, 呼叫 g(1) 回傳 1 結束遞迴, 回傳結果為 :

g(13)=1+3+3+3+3+3+3=1+3*6=19, 答案為 (C).


11. 定義 a[n] 為一陣列(array)，陣列元素的指標為0 至n-1。若要將陣列中a[0]的元素移到a[n-1]，下列程式片段空白處該填入何運算式？

int i, hold, n;

…

for (i=0; i<=      ; i=i+1) {

  hold = a[i];

  a[i] = a[i+1];

  a[i+1] = hold;

  }

(A) n+1   (B) n    (C) n-1    (D) n-2

解析 : 

此題意思是要將陣列頭元素 a[0] 一步一步往後移到陣列尾 a[n-1] 位置, 其他元素往前移一格. 程式使用迴圈來逐一搬移元素, 當 i=n-2 時, a[0] 已來到 a[n-2] 位置, 只要跟 a[n-2] 交換就來到陣列尾了, 故答案為 (D) n-2.

n 元素陣列只要 n-1 次就可以將陣列頭移到陣列尾, 因為從 0 起算, 故迴圈最後索引為 n-2.


12. 給定下列函式 f1() 及 f2()。f1(1)運算過程中，以下敘述何者為錯？

void f1 (int m) {

  if (m > 3) {

    printf ("%d\n", m);

    return;

    }

  else {

    printf ("%d\n", m);

    f2(m+2);

    printf ("%d\n", m);

    }

  }

void f2 (int n) {

  if (n > 3) {

    printf ("%d\n", n);

    return;

    }

  else {

    printf ("%d\n", n);

    f1(n-1);

    printf ("%d\n", n);

    }

  }

(A) 印出的數字最大的是4
(B) f1 一共被呼叫二次
(C) f2 一共被呼叫三次
(D) 數字2 被印出兩次

解析 : 

追蹤如下 :
呼叫 f1(1), 輸出 1, 呼叫 f2(3), 輸出 3, 呼叫 f1(2), 輸出 2, 呼叫 f2(4), 輸出 4, 返回 f1(), 輸出 2, 返回 f2() 輸出 3, 返回 f1() 輸出 1. 故 (A) 印出最大數字是 4 正確, (B) f1 被呼叫二次也正確, (C) f2 被呼叫 3 次錯誤, 應為 2 次, (D) 數字 2 被印出 2 次正確. 故答案是 (C).


13. 右側程式片段擬以輾轉除法求 i 與 j 的最大公因數。請問while 迴圈內容何者正確？

i = 76;

j = 48;

while ((i % j) != 0) {

  ________________

  ________________

  ________________

  }

printf ("%d\n", j);

(A) k = i % j;
       i = j;
       j = k;
(B) i = j;
      j = k;
      k = i % j;
(C) i = j;
      j = i % k;
     k = i;
(D) k = i;
      i = j;
      j = i % k;

解析 : 

輾轉相除法作法是以較大的數當被除數, 較小的數當除數, 相除後將原來的除數當被除數, 餘數當除數繼續相除, 直到餘數為 0 時, 最後的除數就是最大公因數 (GCD), 故答案為 (A).

其中 k 是 % 運算而得的餘數, i=j 就是把原除數當被除數, 而 j=k 就是把餘數當新的除數.


14. 下列程式輸出為何？

void foo (int i) {

  if (i <= 5) {

    printf ("foo: %d\n", i);

    }

  else {

    bar(i - 10);

    }

  }

void bar (int i) {

  if (i <= 10) {

    printf ("bar: %d\n", i);

    }

  else {

    foo(i - 5);

    }

  }

void main() {

  foo(15106);

  bar(3091);

  foo(6693);

  }

(A) bar: 6
       bar: 1
       bar: 8
(B) bar: 6
      foo: 1
      bar: 3
(C) bar: 1
      foo: 1
      bar: 8
(D) bar: 6
      foo: 1
     foo: 3

解析 : 

此題為兩個函數 foo(i) 與 bar(i) 互相呼叫, 在 foo() 中當 i 大於 5 時 呼叫 bar(i-10), 否則印出 "foo" 與 i 值; 在 bar() 中當 i 大於 10 時 呼叫 foo(i-5), 否則印出 "bar" 與 i 值, 因此 i 會在互相呼叫中遞減 5 或 10, 呼叫 foo(i) 時 i 每隔 15 又會呼叫 foo(i); 同理, 呼叫 bar(i) 時 i 每隔 15 又會呼叫 bar(i); 因此可用 i%15 來推測傳入大數值 i 的執行結果, 因為若 i 很大時要一步步追蹤執行結果是很花時間的. 不過由於判斷的門檻是 5 與 10, 因此求 i%15 時不要除盡, 要讓餘數大於 15 做最後判斷:

呼叫 foo(15106) :
15106/15=1006 餘 16, 故下一步是呼叫 foo(16), 因大於 5, 故呼叫 bar(16-10)=bar(6), 因 i 小於 10 故停止交互呼叫而輸出 bar:6.
呼叫 bar(3091) :
3091/15=205 餘 16, 故下一步是呼叫 bar(16), 因大於 10, 故呼叫 foo(16-5)=foo(11), 因 i 大於 5 故呼叫 bar(11-10)=bar(1), 因 i 小於 10 故停止交互呼叫而輸出 bar:1.
呼叫 foo(6693) :
6693/15=445 餘 18, 故下一步是呼叫 foo(18), 因大於 5, 故呼叫 bar(18-10)=bar(8), 因 i 小於 10 故停止交互呼叫而輸出 bar:8.

故答案是 (A). bar: 6     bar: 1    bar: 8


15. 若以f(22)呼叫右側f()函式，總共會印出多少數字？ 

(A) 16     (B) 22      (C) 11     (D) 15


void f(int n) {
  printf ("%d\n", n);
  while (n != 1) {
    if ((n%2)==1) {
      n = 3*n + 1;
      }
    else {
    n = n / 2;
    }
  printf ("%d\n", n);
  }
}

解析 : 

此題之 f() 內有一個無窮迴圈, 終止條件為 n=1, 呼叫 f(22) 過程追蹤如下 :

呼叫 f(22)  ->    印出 22
進入迴圈
迴圈   n    n%2   印出        
  1    22    0    n=n/2=11  
  2    11    1    n=3*n+1=34
  3    34    0    n=n/2=17
  4    17    1    n=3*n+1=52
  5    52    0    n=n/2=26
  6    26    0    n=n/2=13
  7    13    1    n=3*n+1=40
  8    40    0    n=n/2=20
  9    20    0    n=n/2=10
 10    10    0    n=n/2=5
 11     5    1    n=3*n+1=16
 12    16    0    n=n/2=8
 13     8    0    n=n/2=4
 14     4    0    n=n/2=2
 15     2    0    n=n/2=1

迴圈跑了 15 次印出 15 個數字, 加上進函數時印出的 20, 加起來一共 16 個, 故答案是 (A).


16. 下列程式執行過後所輸出數值為何？

(A) 11      (B) 13       (C) 15        (D) 16


void main () {
  int count = 10;
  if (count > 0) {
    count = 11;
    }
  if (count > 10) {
    count = 12;
    if (count % 3 == 4) {
      count = 1;
      }
    else {
      count = 0;
      }
    }
  else if (count > 11) {
    count = 13;
    }
  else {
    count = 14;
    }
  if (count) {
    count = 15;
    }
  else {
    count = 16;
    }
  printf ("%d\n", count);
  }

解析 :  

此程式第一個 if 成立, count 被改為 11; 故第二個 if 也成立, count 被改為 12, 但 count%3 為 0, count 被改為 0, 最後一個 if 不成立, count 被改為 16, 故答案為 (D) 16.


17. 右側程式片段主要功能為：輸入六個整數，檢測並印出最後一個數字是否為六個數字中最小的值。然而，這個程式是錯誤的。請問以下哪一組測試資料可以測試出程式有誤？

(A) 11 12 13 14 15 3
(B) 11 12 13 14 25 20
(C) 23 15 18 20 11 12
(D) 18 17 19 24 15 16

#define TRUE 1
#define FALSE 0
int d[6], val, allBig;
…
for (int i=1; i<=5; i=i+1) {
  scanf ("%d", &d[i]);
  }
scanf ("%d", &val);
allBig = TRUE;
for (int i=1; i<=5; i=i+1) {
  if (d[i] > val) {
    allBig = TRUE;
    }
  else {
    allBig = FALSE;
    }
  }
if (allBig == TRUE) {
  printf ("%d is the smallest.\n", val);
  }
else {
  printf ("%d is not the smallest.\n", val);
  }
}

解析 : 

此題程式錯誤處在於比較結果旗標 allBig 的最後狀態取決於陣列的最後元素 d[6] 與 val 比較之結果, 與 d[1]~d[5] 無關, 這四組輸入之 allBig 結果如下 :

(A) 11 12 13 14 15 3    allBig=TRUE
(B) 11 12 13 14 25 20  allBig=TRUE
(C) 23 15 18 20 11 12  allBig=FALSE
(D) 18 17 19 24 15 16 allBig=FALSE

(A) 的最後 1 個數 3 確實是 6 個中最小的, 程式執行結果正確; (B) 的 20 並非最小, 但卻被 d[5]=25 大於 20 改成 TRUE, 執行結果錯誤, 故答案為 (B).  (C) 的 12 因為大於 d[5]=11 使得 allBig 被改為 FALSE, 執行結果正確, 但檢測不出程式是錯的, (D) 也是如此.

正確的寫法應該將下列錯誤程式碼 :

  if (d[i] > val) {
    allBig = TRUE;
    }
  else {
    allBig = FALSE;
    }

改為如下 :

  if (d[i] <= val) {
    allBig = FALSE;
    }

即預先假定 val 是最小的, 但拜訪陣列過程中, 只要 d[1]~d[5] 中有任何一個不大於 val, 就把旗標 allBig 改為 FLASE.


18. 程式編譯器可以發現下列哪種錯誤?

(A) 語法錯誤   (B) 語意錯誤    (C) 邏輯錯誤     (D) 以上皆是

解析 :

編譯器只能找出語法錯誤, 無法查知語意與邏輯錯誤, 答案為 (A).


19. 大部分程式語言都是以列為主的方式儲存陣列。在一個8x4 的陣列(array) A 裡，若每個元素需要兩單位的記憶體大小，且若A[0][0]的記憶體位址為 108 (十進制表示)，則
A[1][2]的記憶體位址為何？

(A) 120    (B) 124     (C) 128      (D) 以上皆非

解析 :

陣列在記憶體中為連續排列, A[8][4] 的二維陣列

A[0][0]  + 0
A[0][1]  + 1
A[0][2]  + 2
A[0][3]  + 3
A[1][0]  + 4
A[1][1]  + 5
A[1][2]  + 6
A[1][3]  + 7
........

因此 A[1][2] 是從 A[0][0] 開始算 + 6 個元素, 若每個元素占 2 個記憶單位, 則差距是 2*6=12 個記憶單位, 故 A[1][2] 的位址是 108+12=120, 答案為 (A).


20. 下列為一個計算n 階層的函式，請問該如何修改才會得到正確的結果？

1. int fun (int n) {

2.   int fac = 1;

3.   if (n >= 0) {

4.     fac = n * fun(n - 1);

5.     }

6.   return fac;

7.   }

(A) 第2 行，改為 int fac = n;
(B) 第3 行，改為if (n > 0) {
(C) 第4 行，改為fac = n * fun(n+1);
(D) 第4 行，改為fac = fac * fun(n-1);

解析 :

此題程式不管第二列 fac 是 1 還是 n, 呼叫 fun() 結果都是 0, 原因是遞迴的最後呼叫 fun(1-1)=fun(0) 時, fac=n*fun(n-1)=0*fun(-1)=0, 層層回傳的結果, 最後 fac 必定為 0, 關鍵是第 3 列的判斷式 if (n >= 0) 中含有等於 0, 只要去掉 = 就可以了, 答案是 (B). (C) 不可能, 因為 n+1 會越來越大, 不可能收斂. (D) 也不行, 因為 if (n >= 0) 還是會讓它最後傳回 0.


21. 下列程式碼，執行時的輸出為何？

void main() {

  for (int i=0; i<=10; i=i+1) {

    printf ("%d ", i);

    i = i + 1;

    }

  printf ("\n");

  }

(A) 0 2 4 6 8 10
(B) 0 1 2 3 4 5 6 7 8 9 10
(C) 0 1 3 5 7 9
(D) 0 1 3 5 7 9 11

解析 :

由於迴圈內有兩個 i=i+1, 因此每次迴圈 i 會增量 2, 即從 0 開始, 2, 4, 6, ... 10, 故答案是 (A).

22. 下列 f() 函式執行後所回傳的值為何？

int f() {
  int p = 2;
  while (p < 2000) {
    p = 2 * p;
    }
  return p;
  }

(A) 1023
(B) 1024
(C) 2047
(D) 2048

解析 :

追蹤此函數執行結果 :

迴圈     p
   0        2
   1        2*2
   2        2*2*2
   3        2*2*2*2
  .....      .....
1000     2*2*2*2......*2  (共 1001 項)

這裡最後的 p 有 1001 個 2 相乘, 因為當 p=1000 時, 2*p=2000 剛好跳出無窮迴圈, 因此加上初始的 p=2 總共是 1001 個 2 相乘=2**1001=2048, 答案是 (D).


23. 下列 f() 函式 (a), (b), (c) 處需分別填入哪些數字，方能使得 f(4) 輸出 2468 的結果？

int f(int n) {

  int p = 0;

  int i = n;

  while (i >=  (a)   ) {

    p = 10 –  (b)  * i;

    printf ("%d", p);

    i = i -   (c)   ;

    }

  }

(A) 1, 2, 1     

(B) 0, 1, 2      

(C) 0, 2, 1
(D) 1, 1, 1

解析 :

解此種題目看起來似乎無捷徑, 就是將 A,B,C,D 四個選項一一代進去驗證結果, 不過若先觀察程式特徵, 可以快速剔除錯誤選項, 用排除法迅速找出正確答案. 此程式中 p=10-b*i 決定 p 值, 當呼叫 f(4), 在第一次迴圈裡 p=10-b*4, 若要輸出 p=2, 則 b 須為 2, 四個選項中僅 (A) 與 (C) 符合, (B) 與 (D) 就出局了.

(A) 與 (C) 僅 a 不同, 亦即迴圈的終止條件不同, (A) 是 i >=1 而 (C) 是 i>=0, 每次迴圈 i 會遞減 1, 因此 (A) 會輸出 4 個數字 (對應 i=4,3,2,1); 而 (C) 則會輸出 5 個數字 (對應 i=4,3,2,1,0), 最後輸出的數字是 10 (因最後一圈 i=0, 故 p=10-2*0=10), 題目要的是 2468 四個數字, 故答案是 (A).

追蹤 (A) 輸出結果為 2468, 而 (C) 則是 246810.


24. 右側g(4)函式呼叫執行後，回傳值為何？

(A) 6     (B) 11      (C) 13       (D) 14
int f (int n) {
  if (n > 3) {
    return 1;
    }
  else if (n == 2) {
    return (3 + f(n+1));
    }
  else {
    return (1 + f(n+1));
    }
  }

int g(int n) {
  int j = 0;
  for (int i=1; i<=n-1; i=i+1) {
    j = j + f(i);
    }
  return j;
  }

解析 :

此為遞迴函數題目, 追蹤如下 :

呼叫 g(4) :
進入 for 迴圈跑三圈, i=1~3, j=j+f(i)
i=1 時 : j=0+f(1)
呼叫 f(1) 回傳 1+f(2), 呼叫 f(2) 回傳 3+f(3), 呼叫 f(3) 回傳 1+f(4), 呼叫 f(4) 回傳 1, 遞迴結果 j=f(1)=1+3+1+1=6;
i=2 時 : j=6+f(2)
呼叫 f(2) 回傳 3+f(3), 呼叫 f(3) 回傳 1+f(4), 呼叫 f(4) 回傳 1, 遞迴結果 j=6+f(2)=6+3+1+1=11;
i=3 時 : j=11+f(3)
呼叫 f(3) 回傳 1+f(4), 呼叫 f(4) 回傳 1, 遞迴結果 j=11+f(3)=11+1+1=13;

答案是 (C) 13.


25. 下列Mystery()函式else 部分運算式應為何，才能使得 Mystery(9) 的回傳值為34。

int Mystery (int x) {

  if (x <= 1) {

  return x;

  }

else {

  return ____________ ;

  }

}

(A) x + Mystery(x-1)
(B) x * Mystery(x-1)
(C) Mystery(x-2) + Mystery(x+2)
(D) Mystery(x-2) + Mystery(x-1)

解析 :

這也是遞迴題目, 終止條件為 x <= 1, 四個選項中的 (C) 呼叫了 Mystery(x+2), x 會持續增加無法收斂, 故先排除. 另外 (B) 為乘法, 遞迴第一層為 9*Mystery(8), 最後一層為 2*Mystery(1)=2, 這兩項乘積為 18, 再乘以中間層 (都是整數) 最後等於 34 是不可能的, 因此也排除, 剩下 (A) 與 (D).

追蹤 (A) :
呼叫 Mystery(9), 回傳 9+Mystery(8), 呼叫 Mystery(8), 回傳 8+Mystery(7), 呼叫 Mystery(7), 回傳 7+Mystery(6), ... , 呼叫 Mystery(2), 回傳 2+Mystery(1), 呼叫 Mystery(1), 回傳 1, 故最後回傳結果是 9+8+7+6+.....+2+1=(9+1)*9/2=45, 不是 34, 故排除 (A), 答案應是 (D).

追蹤 (D) :
呼叫 Mystery(9), 回傳 Mystery(7)+Mystery(8), 呼叫 Mystery(8), 回傳 Mystery(6)+Mystery(7), 呼叫 Mystery(7), 回傳 Mystery(5)+Mystery(6), ... , 呼叫 Mystery(3), 回傳 Mystery(1)+Mystery(2), 呼叫 Mystery(2), 回傳 Mystery(0)+Mystery(1), 呼叫 Mystery(1) 回傳 1, 呼叫 Mystery(0) 回傳 0. 故呼叫 Mystery(2) 與 Mystery(1) 結果均為 1, 分兩段計算 :
Mystery(9)=Mystery(7)+Mystery(8)=Mystery(5)+Mystery(6)+Mystery(6)+Mystery(7)=Mystery(5)+Mystery(6)+Mystery(6)+Mystery(5)+Mystery(6)=2*Mystery(5)+3*Mystery(6)
Mystery(5)=Mystery(3)+Mystery(4)=Mystery(1)+Mystery(2)+Mystery(2)+Mystery(3)=Mystery(1)+Mystery(2)+Mystery(2)+Mystery(1)+Mystery(2)=5
Mystery(6)=Mystery(4)+Mystery(5)=Mystery(2)+Mystery(3)+Mystery(5)=Mystery(2)+Mystery(1)+Mystery(2)+Mystery(5)=3+Mystery(5)=8
故 Mystery(9)=2*Mystery(5)+3*Mystery(6)=2*5+3*8=34

呵呵, 花了四天時間斷斷續續終於解完 25 題了, 發現遞迴函數考蠻多的哩! 其次是迴圈運算, 而且有些題目需要用到基礎數學概念如級數和與最大公因數等等. 另外像第 14 題則需要一點小小的求餘數技巧, 總之, 不只是考程式而已, 也考一些數學觀念.