【APCS】2016-03-05 觀念題

| | |

APCS 是個大學程式設計先修檢測，是個針對高中職學生的測驗，那天發現這個想說來試著寫寫看，今天寫的考題官是ˋ\網上所提供 2016-03-05 的考古題。

題目與作答

1 . ( A ) 右側程式正確的輸出應該如下：

1
2
3
4
5
    *
   ***
  *****
 *******
*********

在不修改程式之第 4 行及第 7 行程式碼的前提下，最少需修改幾行程式碼以得到正確輸出？ ( A ) 1 ( B ) 2 ( C ) 3 ( D ) 4

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

   for(int j=1  ; j<=m ; j=j+1){
      printf("*");
   }

   printf("\n");

   k = k-1;
   m = m+1;  
}

[解] 這程式碼跑出來的結果，很明顯是 * 的輸出個數不對，在不能改 for 迴圈的條件下，可以將 m=m+1 這行改成 m=2*i+1


2 . ( C ) 給定一陣列 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

1
2
3
4
5
6
7
8
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;

[解] 這隻程式碼主要是在記錄陣列 a[:n] 中最大值的 index，若有相同值則記錄最大的 index。在 a[:10] 中最大的值為 9，而所對應的 index 為 7。


3 . ( D ) 給定一整數陣列 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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; 
   }

[解] fl 的執行次數計算，先找一下是否有 a[k] == 100 ，可算出 k = 33 ，指標 i 從 0 到 33，共執行 34 次。 f2 一樣是要找出 k = 33 時執行了幾次，不過 f2 是用二分搜尋演算法在找 k ，手算一下需要執行 5 次，mid 的值分別會是：49、24、27、30、33。


4 . ( D ) 經過運算後，右側程式的輸出為何？( A ) 1275 ( B ) 20 ( C ) 1000 ( D ) 810

1
2
3
4
5
6
7
8
9
10
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]);

[解] 稍微歸納一下會發現 a[i] 總和可寫成 $\sum_{n=1}^{i}n$，用梯形公式計算 a[50] = 1275、 a[30] = 465，兩數相減得差為 810。


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

1
2
3
4
5
6
7
8
9
10
11
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; 
}

[解] 先不看遞迴的部分，基本 n 為多少該式就會被執行多少，最後遞迴部分會更新 n 進入再次呼叫 f ，所以該行的執行次為所有n 的總和，為 n 依次 1000、666、444、296、197、131、87、58、38、25、16、10、6、4，最後在 n = 2 時會停止遞迴開始回傳，因此 n 的總和為（不用加最後的 2，最後的 2 在 if 判斷式時就會被回傳）2978，最接近的答案為 3000 。


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

1
2
3
4
5
6
7
8
9
例如在 list 中有三筆資料 :
      1             2            3
------------------------------------------
| data = ‘a’ |  data = ‘b’  | data = ‘c’ | 
| next = 2   |  next = -1   | next = 1   | 
------------------------------------------

它所代表的串列如下圖
c -> a -> b ->

RemoveNextElement 是一個程式，用來移除串列中 current 所指向的下一個元素，但是必須保持原始串列的順序。例如，若 current 為 3（對應到 list[3]）， 呼叫完 RemoveNextElement 後，串列應為

1
c -> b ->

請問在空格中應該填入的程式碼為何? ( 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 ;

1
2
3
4
5
6
7
8
9
struct element { 
   char data; int next; 
} 
void RemoveNextElement (element list[], int current) { 
   if (list[current].next != -1) { 
      /*移除 current 的下一個 element*/ 
      ______________________________
   } 
}

[解] current 為 index，而移除 current 所指向的下一個元素，因此將原先只向下一個元素的指標，指向下下個元素


7 . ( B ) 請問以 a(13,15) 呼叫右側 a() 函式，函式執行完後其回傳值為何？ ( A ) 90 ( B ) 103 ( C ) 93 ( D ) 60

1
2
3
4
5
6
7
8
9
10
11
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 ; 
   } 
}

[解] 整理一下，因 n > 10 ，所以會先產生 $13 + 12 + 11 + 10$ 和，接下來 m 的部分會產生 $15 + 13 + 11$，最後當 m , n 皆小於 10 ， 所以計算 $m + n = 9 + 9$，將所有的值相加 $13 + 12 + 11 + 10 + 15 + 13 + 11 + 9 + 9 = 103$


8 . ( C ) 一個費式數列定義第一個數為 0 第二個數為 1 之後的每個數都等於前兩個數相加，如下所示: 0、1、1、2、3、5、8、13、21、34、55、89…。

1
2
3
4
5
6
7
8
9
10
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) ); 
}

右列的程式用以計算第 N 個(N≥2)費式數列的數值，請問 (a) 與 (b) 兩個空格的敘述(statement)應該為何？ ( 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]


9 . ( B ) 請問右側程式輸出為何？ ( A ) 1 ( B ) 4 ( C ) 3 ( D ) 33

1
2
3
4
5
6
7
8
9
10
11
12
13
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 = {None, 6, 10, 14, 18}、 B = {None, 5, 10, 15, 20}，兩個迴圈都是從 i = 1 開始，所以我將指標為 0 的位置先以 None 來表示，不過等等完全用不到他們就是，純粹就只是習慣從 0 開始寫…。觀察兩數列運算結果，會發現從 i > 2 開始才會開始符合 if 判斷式，在此之前 c 皆為 1 ，因此可以計算： \(\begin{aligned} c &=1 + B[3]\ \%\ A[3] + B[4]\ \%\ A[4] \\ &= 1 + 15\ \%\ 14 + 20\ \%\ 18 \\ &= 1 + 1 + 2 \\ &= 4 \end{aligned}\)


10 . ( C ) 給定右側 g() 函式，g(13) 回傳值為何？ ( A ) 16 ( B ) 18 ( C ) 19 ( D ) 22

1
2
3
4
5
6
int g(int a) { 
   if (a > 1) { 
      return g(a - 2) + 3; 
   } 
   return a; 
}

[解] 每次執行遞迴，a 值會減 2，因此算一下會執行次數遞迴。 \(13 \div 2 = 6 ... 1 \\ 6 \times 3 + 1 = 19\)


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

1
2
3
4
5
6
int i, hold, n; 
for (i=0; i<= ___; i=i+1) { 
   hold = a[i];
   a[i] = a[i+1]; 
   a[i+1] = hold; 
}

[解] 觀察一下程式，會發現它把原先在 i 的元素換到 i+1 的位置，所以如果要把 0 的元素換到 n-1，就必須執行 i 從 0 到 n-2，在 i = n-2 時候，它會把 n-2 與 n-1 交換，最終原先 0 的元素就會在 n-1 的位置了。


12 . ( C ) 給定右側函式 f1() 及 f2()。f1(1)運算過程中，以下敘述何者為錯？ ( A ) 印出的數字最大的是 4 ( B ) f1 一共被呼叫二次 ( C ) f2 一共被呼叫三次 ( D ) 數字 2 被印出兩次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
   } 
}

[解] 當個人工 compiler 跑一下，會得到數字的輸出序為：1、3、2、4、2、3、1 並可得知 function 的呼叫序為 f1(1)、f2(3)、f1(2)、f2(4)，回去對一下選項就能得到答案了。


13 . ( A ) 右側程式片段擬以輾轉除法求 i 與 j 的最大公 因數。請問 while 迴圈內容何者正確？ ( 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;

1
2
3
4
5
6
7
8
i = 76; 
j = 48; 
while ((i % j) != 0) {
    ________________ 
    ________________ 
    ________________ 
 } 
 printf ("%d\n", j);

[解] 輾轉相除法原理是兩個整數的最大公因數等於其中較小的數和兩數的差的最大公因數 <– 取自維基百科，按照這個原理取出相對應的程式。


14 . ( A ) 右側程式輸出為何？ ( 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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); 
}

[解] 我這題的解題方式稍微有點 tricky 不太好解釋。

  1. 第一個答案： 15010 / 15 = 1007 … 1 ，它是由 foo 開始呼叫，因此不考慮中止條件，反推最後 3 個呼叫應為： foo(15) , bar(6), foo(1) ，按中止條件會在 bar(6) 時停下。 　

  2. 第二個答案同理： 3091 / 15 = 206 … 1 ，它是由 bar 開始呼叫，不考慮中止條件反推最後 3 個呼叫應為： bar(16), foo(11), bar(1), ，按中止條件會在 bar(1) 時停下。 　

  3. 第三個答案： 6693 / 15 = 446 … 3 ，它是由 foo 開始呼叫，不考慮中止條件反推最後 3 個呼叫應為： foo(18) , bar(8), foo(3) ，，按中止條件會在 foo(3) 時停下。


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

1
2
3
4
5
6
7
8
9
10
11
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); 
   }
}

[解] 計算一下 while 迴圈會被呼叫 15 次，加上最外面的 print ，總共會印出 16 個數字。


16 . ( D ) 右側程式執行過後所輸出數值為何？ ( A ) 11 ( B ) 13 ( C ) 15 ( D ) 16

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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) 的部分，這邊的判斷式可以表示成 if (count!=0) ，所以最後會得到 count 為 16。


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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);
}

[解] 按照著程式其實不論前面的比較結果如何，都會被第 5 數字的比較給蓋過去，所以如果要找的話，就找到第 5 數字比最後一個還大，且第 1 到第 4 個數字中有存在比最後一個還小的數值。這題程式如果要改的話，就是當碰到 allBig = FALSE 就要 break 中斷迴圈了。


18 . ( A ) 程式編譯器可以發現下列哪種錯誤? ( A ) 語法錯誤 ( B ) 語意錯誤 ( C ) 邏輯錯誤 ( D ) 以上皆是


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

[解] 題目說每個元素需要 2 單位，而陣列的第二維度大小是 4 ，所以 A[1][2] 的記憶體為 108 + (4-1 + 3) * 2 = 120 ，減 1 是因為 A[0][0] 不用算。


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

1
2
3
4
5
6
7
int fun (int n) { 
   int fac = 1; 
   if (n >= 0) { 
      fac = n * fun(n - 1); 
   } 
   return fac; 
}

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

[解] 依照數學階層 n!= 1×2×3×…×n，故第三行的判斷式，不應該出現 n 等於 0 的 case，而且 n 如果等於 0 的話，階層的乘積都會為 0 了。


21 . ( A ) 右側程式碼，執行時的輸出為何？

1
2
3
4
5
6
7
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

[解] 在迴圈的範圍內，每次執行一次會加 1 ，而迴圈本身（ for ）又會在每次結束時加 1，所以每一個 step 實際上是加了 2。


22 . ( D ) 右側 f()函式執行後所回傳的值為何？( A ) 1023 ( B ) 1024 ( C ) 2047 ( D ) 2048

1
2
3
4
5
6
7
int f() { 
   int p = 2; 
   while (p < 2000) { 
      p = 2 * p; 
   } 
   return p; 
}

[解] 觀察一下，會發現它的 p 其實是 2的 n 次方結果，所以找到大於 2000 的最小 2 的次方數就好，最小的是 $2^{11} = 2048$ 。


23 . ( A ) 右側 f()函式 (a), (b), (c) 處需分別填入哪些數字，方能使得 f(4) 輸出 2468 的結果？( A ) 1, 2, 1 ( B ) 0, 1, 2 ( C ) 0, 2, 1 ( D ) 1, 1, 1

1
2
3
4
5
6
7
8
9
int f(int n) { 
   int p = 0; 
   int i = n; 
   while (i >= (a) ) {
      p = 10 – (b) * i; 
      printf ("%d", p);
      i = i - (c) ; 
   } 
}

[解] 先處理 ( a ) 與 ( c ) 的位置，按照答案需要進入迴圈 4 次，因為輸出了四的數值，而 (0, 2) 與 (0,1) 會分別進入迴圈 2 次與 5 次，因此 ( a ) 與 ( c ) 為 (1,1) ，接下 (b) 的位置就解方成就可以了當 i 等於 4 時，其輸出為 2，所以可得 $10-b\times 4 = 2$，b 等於 2 。


24 . ( C ) 右側 g(4)函式呼叫執行後，回傳值為何？ ( A ) 6 ( B ) 11 ( C ) 13 ( D ) 14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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; 
}

[解] 先算一下 ( f(1) , f(2) ,f(3) ,f(4) ) = (6, 5, 2, 1) ，再算 g(4) = f(1) + f(2) + f(3) = 6 + 5 + 2 = 13。


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

1
2
3
4
5
6
7
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)

[解] 這題用消去法來解。34 這個數字不包含因數 9 ，所以可以刪除 B；而且 34 也不是以 1 為頂以 9 為底的梯形公式的結果，所以刪除 A；而選項 C 的部分，它對 x 加 2 ，但這題的中止條件為 x <= 1，如果上加會達不到中止條件，會變成無窮遞迴，所以刪除 C。

感想

其實不太難，都還滿基礎了，這份卷子真要說最難的就第一題吧。如果真個不會寫，當個人工 compiler 跑個幾次，也能選出答案。不過鑑於這份卷子是給高中生寫的難度應該算還好？有點搞不太清楚現在高中生的實力，人老了阿…

是說，APCS 公開的考古題有三份，短時間內應該不會再做第二份，把它打成網誌真的有夠麻煩的，比我寫這份卷子的時間還久。除非…我沒素材發網誌了 XD

考古題下載

2016-03-05_觀念題_試題下載