---
# System prepended metadata

title: 【APCS】2016-03-05 觀念題
tags: [APCS, 面試刷題]

---

---
title: 【APCS】2016-03-05 觀念題
date: 2019-01-09
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "APCS"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}

<br>

[APCS](https://apcs.csie.ntnu.edu.tw) 是個大學程式設計先修檢測，是個針對高中職學生的測驗，那天發現這個想說來試著寫寫看，今天寫的考題是官網上所提供 2016-03-05 的考古題。
<!--more-->



## 題目與作答
1 . **( A )** 右側程式正確的輸出應該如下：
```
    *
   ***
  *****
 *******
*********
```

在不修改程式之第 4 行及第 7 行程式碼的前提下，最少需修改幾行程式碼以得到正確輸出？ ( A ) 1 ( B ) 2 ( C ) 3 ( D ) 4 
```cpp
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**


<br><br>
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 
```cpp
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。 


<br><br>

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

```c
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。


<br></br>
4 . **( D )** 經過運算後，右側程式的輸出為何？( A ) 1275  ( B ) 20  ( C ) 1000 ( D ) 810
```c
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。

<br></br>
5 . **( B )** 函數 f 定義如下，如果呼叫 f(1000)，指令 sum=sum+i 被執行的次數最接近下列何者？( A ) 1000 ( B ) 3000 ( C ) 5000 ( D ) 10000
```c
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 。


<br></br>
6 . **( B )**  List 是一個陣列，裡面的元素是 element， 它的定義如右。List 中的每一個 element 利用 next 這個整數變數來記錄下一個 element 在陣列中的位置，如果沒有下一個 element， next 就會記錄 -1。所有的 element 串成了一 個串列 (linked list)。
```
例如在 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 後，串列應為
```
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 ;

```c
struct element { 
   char data; int next; 
} 
void RemoveNextElement (element list[], int current) { 
   if (list[current].next != -1) { 
      /*移除 current 的下一個 element*/ 
      ______________________________
   } 
}
``` 

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

<br></br>
7 . **( B )**  請問以 a(13,15) 呼叫右側 a() 函式，函式執行完後其回傳值為何？  ( A ) 90 ( B )  103 ( C )  93 ( D )  60
```c
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$

<br></br>
8 . **( C )** 一個費式數列定義第一個數為 0 第二個數為 1 之後的每個數都等於前兩個數相加，如下所示: 0、1、1、2、3、5、8、13、21、34、55、89…。
```c
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]

<br></br>
9 . **(  B )** 請問右側程式輸出為何？  ( A ) 1 ( B ) 4 ( C ) 3 ( D ) 33
```c
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}
$$

<br></br>
10 . **( C )** 給定右側 g() 函式，g(13) 回傳值為何？  ( A ) 16 ( B ) 18 ( C ) 19 ( D ) 22
```c
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
$$

<br></br>
11 . **( D )** 定義 a[n] 為一陣列(array)，陣列元素的指標為 0 至 n-1。若要將陣列中 a[0] 的元素移到 a[n-1]，右側程式片段空白處該填入何運算式？( A ) n+1 ( B ) n ( C ) n-1 ( D ) n-2
```c
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 的位置了。

<br></br>
12 . **( C )**  給定右側函式 f1() 及 f2()。f1(1)運算過程中，以下敘述何者為錯？
( A ) 印出的數字最大的是 4 
( B ) f1 一共被呼叫二次
( C ) f2 一共被呼叫三次
( D ) 數字 2 被印出兩次
```c
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)，回去對一下選項就能得到答案了。


<br></br>
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;
```c
i = 76; 
j = 48; 
while ((i % j) != 0) {
    ________________ 
    ________________ 
    ________________ 
 } 
 printf ("%d\n", j);
```
[解] 輾轉相除法原理是**兩個整數的最大公因數等於其中較小的數和兩數的差的最大公因數** <-- 取自維基百科，按照這個原理取出相對應的程式。

<br></br>
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
```c
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) 時停下。

<br></br>
15 . **( A )**  若以 f(22)呼叫右側 f()函式，總共會印出多少數字？ ( A ) 16 ( B ) 22 ( C ) 11 ( D ) 15 
```c
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 個數字。

<br></br>
16 . **( D )** 右側程式執行過後所輸出數值為何？ ( A ) 11 ( B ) 13 ( C ) 15 ( D ) 16
```c
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。

<br></br>
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
```c
#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 中斷迴圈了。

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

<br></br>
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] 不用算。

<br></br>
20 . **( B )** 右側為一個計算 n 階層的函式，請問該如何修改才會得到正確的結果？
```c
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 了。

<br></br>
21 . **(  A  )** 右側程式碼，執行時的輸出為何？
```c
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。

<br></br>
22 . **(  D  )**  右側 f()函式執行後所回傳的值為何？( A ) 1023 ( B ) 1024 ( C ) 2047 ( D ) 2048
```c
int f() { 
   int p = 2; 
   while (p < 2000) { 
      p = 2 * p; 
   } 
   return p; 
}
```
[解] 觀察一下，會發現它的 p 其實是 2的 n 次方結果，所以找到大於 2000 的最小 2 的次方數就好，最小的是 $2^{11} = 2048$ 。

<br></br>
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
```c
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 。
 
<br></br>
24 . **( C )** 右側 g(4)函式呼叫執行後，回傳值為何？ ( A ) 6 ( B ) 11 ( C ) 13 ( D ) 14
```c
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。


<br></br>
25 . **(  D  )** 右側 Mystery()函式 else 部分運算式應為何，才能使得 Mystery(9) 的回傳值為 34。
```c
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_觀念題_試題下載](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1050305APCSconcept.pdf) 
 
<br><br> 

> **本文作者**： 辛西亞．Cynthia  
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/APCS-2016-03-05) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/APCS-2016-03-05)   
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！
