# APCS觀念題2016年3月
> 日期：2023年2月2日
> 作者：王一哲
1. 下列程式正確的輸出應該如下：
```
*
***
*****
*******
*********
```
在不修改下列程式之第 4 行及第 7 行程式碼的前提下，最少需修改幾行程式碼以得到正確輸出？
(A) 1 (B) 2 \(C\) 3 (D) 4
```c=
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;
}
```
<br />
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：將第12行改成 m = 2\*i + 1 或是 m += 2 即可。以下是測試用的程式碼：
```c=
#include <stdio.h>
int main() {
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 = 2*i + 1;
// m += 2;
}
return 0;
}
```
<br /><br />
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
```c
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;
}
```
<br />
<span style="font-weight:bold">答案</span>：C
<span style="color:blue">詳解</span>：若陣列中索引值為i的元素大於等於第i個元素，則將i的值指定給index，最後的回傳值就是陣列中最大且位於最後面的元素索引值。以下是測試用的程式碼：
```c=
#include <stdio.h>
int f (int a[], int n);
int main() {
int a[10] = {1, 3, 9, 2, 5, 8, 4, 9, 6, 7};
printf("%d\n", f(a, 10));
return 0;
}
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;
}
```
<br /><br />
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
```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;
}
```
```c
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;
}
```
<br />
<span style="font-weight:bold">答案</span>：D
<span style="color:blue">詳解</span>：依照題目敘述，陣列 a[100] = {1, 4, 7, ..., 298}，呼叫 f1(a, 100) 及 f2(a, 100) 會回傳元素100於陣列中的索引值33。f1 為循序搜尋，依照索引值由小到大一個一個搜尋，因此要運作34次。f2 為二分搜尋法，可以依照程式碼，用紙筆列出運作過程中變數 low、high、mid、a[mid] 分別對應的數值，我在以下的程式碼加上一些輸出變數值的部分，應該會比較容易理解程式的運作流程。
```c=
#include <stdio.h>
int f1(int a[], int n);
int f2(int a[], int n);
int main() {
int a[100], val1, val2;
for(int k = 0; k < 100; k++) {
a[k] = 3*k + 1;
}
val1 = f1(a, 100);
val2 = f2(a, 100);
printf("f1(a, 100) = %d\tf2(a, 100) = %d\n", val1, val2);
return 0;
}
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;
int tmp, count = 0;
while (low <= high) {
count++;
mid = (low + high)/2;
printf("執行前：count = %d, low = %d, high = %d, mid = %d\n", count, low, high, mid);
tmp = a[mid];
if (a[mid] == value) {
r_value = mid;
break;
}
else if (a[mid] < value) {
low = mid + 1;
}
else {
high = mid - 1;
}
printf("執行後：a[mid] = %d, low = %d, high = %d\n", tmp, low, high);
}
return r_value;
}
```
輸出結果
```c
執行前：count = 1, low = 0, high = 99, mid = 49
執行後：a[mid] = 148, low = 0, high = 48
執行前：count = 2, low = 0, high = 48, mid = 24
執行後：a[mid] = 73, low = 25, high = 48
執行前：count = 3, low = 25, high = 48, mid = 36
執行後：a[mid] = 109, low = 25, high = 35
執行前：count = 4, low = 25, high = 35, mid = 30
執行後：a[mid] = 91, low = 31, high = 35
執行前：count = 5, low = 31, high = 35, mid = 33
f1(a, 100) = 33 f2(a, 100) = 33
```
<br /><br />
4. 經過運算後，下列程式的輸出為何？
(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]);
```
<br />
<span style="font-weight:bold">答案</span>：D
<span style="color:blue">詳解</span>：從前3行程式碼可以看出陣列 b[0] 沒有被指定值，不過預設值通常會是0，其它的值則是依序填入1、2、3、...、100。從第4到7行程式碼可以看出，a[i] 為 0 + 1 + 2 + ... + i，或是將前幾個值列出來就可以看出規律，a[0] = 0，a[1] = 0 + 1，a[2] = 0 + 1 + 2，a[3] = 0 + 1 + 2 + 3，因此
$$
a[50] = 0 + 1 + 2 + \dots + 50 = \frac{(1+50) \times 50}{2} = 1275
$$
$$
a[30] = 0 + 1 + 2 + \dots + 30 = \frac{(1+30) \times 30}{2} = 465
$$
$$
a[50] - a[30] = 1275 - 465 = 810
$$
以下是測試用的程式碼
```c=
#include <stdio.h>
int main() {
int a[101], b[101];
for (int i=1; i<=100; i=i+1) {
b[i] = i;
printf("b[%d] = %d\n", i, b[i]);
}
a[0] = 0;
for (int i=1; i<=100; i=i+1) {
a[i] = b[i] + a[i-1];
printf("a[%d] = %d\n", i, a[i]);
}
printf ("%d\n", a[50]-a[30]);
return 0;
}
```
<br /><br />
5. 函式 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;
}
```
<br />
<span style="font-weight:bold">答案</span>：B
<span style="color:blue">詳解</span>：本題需要用到函式的遞迴 (recursion)，這裡是在函式 f 當中呼叫函式 f，這是 APCS 觀念題中特別愛考的內容，解題時最好先找出函式的出口，也就是停止運作的條件，通常是回傳某個常數值，再用紙筆列出幾次運算過程，應該可以找出運作規律。以本題的而言，函式出口為 n < 2 時，回傳值為 0；當 n > 2 時，sum = sum + 1 會被運作 n 次；呼叫 f(1000) 時，會接著依序呼叫f(666)、f(444)、f(296)、f(197)、f(131)、f(87)、f(58)、f(38)、f(25)、f(16)、f(10)、f(6)、f(4)、f(2)，因此 sum = sum + 1 會被運作 2980 次。以下是測試用的程式碼
```c=
#include <stdio.h>
int f (int n);
int sum = 0, count = 0;
int main() {
sum, count = f(1000);
printf("sum = %d count = %d\n", sum, count);
return 0;
}
int f (int n) {
if (n < 2) {
return 0;
}
printf("n = %d\n", n);
for (int i=1; i<=n; i=i+1) {
sum = sum + i;
count++;
}
sum = sum + f(2*n/3);
return sum, count;
}
```
<br /><br />
6. List 是一個陣列，裡面的元素是 element，它的定義如右。List 中的每一個 element 利用 next 這個整數變數來記錄下一個 element 在陣列中的位置，如果沒有下一個 element，next 就會記錄-1。所有的 element 串成了一個串列 (linked list)。例如在 list 中有三筆資料
<img height="50%" width="50%" src="https://imgur.com/GJ6CCJj.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />
它所代表的串列如下圖
<img height="30%" width="30%" src="https://imgur.com/VbJxxAg.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />
RemoveNextElement 是一個程序，用來移除串列中 current 所指向的下一個元素，但是必須
保持原始串列的順序。例如，若 current 為 3 (對應到 list[3])，呼叫 RemoveNextElement 後，串列應為
<img height="20%" width="20%" src="https://imgur.com/SnzckZq.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />
請問在空格中應該填入的程式碼為何?
```c
struct element {
char data;
int next;
}
void RemoveNextElement (elementlist[], int current) {
if (list[current].next != -1) {
/*移除 current 的下一個 element*/
/*此行為要填入的程式碼*/
}
}
```
(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;
<br />
<span style="font-weight:bold">答案</span>：B
<span style="color:blue">詳解</span>：本題考的是鏈結串列 (linked list)，不是指 Python 資料格式之一的串列 (list)。如果 current 為 3，代表 RemoveNextElement 要跳過4號元素，連結到5號元素，因此答案為B。
<br /><br />
7. 請問以 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 ;
}
}
```
<br />
<span style="font-weight:bold">答案</span>：B
<span style="color:blue">詳解</span>：本題考函式的遞迴 (recursion)，直接列出運作過程
$$
\begin{align*}
a(13, 15) &= a(12, 15) + 13\\
&= a(11, 15) + 12 + 13\\
&= a(10, 15) + 11 + 12 + 13\\
&= a(9, 15) + 10 + 11 + 12 + 13\\
&= a(9, 13) + 46 + 15\\
&= a(9, 11) + 46 + 13 + 15\\
&= a(9, 9) + 46 + 11+ 13 + 15\\
&= 9 + 9 + 46 + 39\\
&= 103
\end{align*}
$$
<br /><br />
8. 一個費式數列定義第一個數為 0 第二個數為 1 之後的每個數都等於前兩個數相加，如下所示:0、 1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89…。右列的程式用以計算第 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]
```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)____ );
}
```
<br />
<span style="font-weight:bold">答案</span>：C
<span style="color:blue">詳解</span>：於 for 迴圈中，先將 b 的值指定給 temp，再將 b 更新為 b + a，最後將 temp 的值指定給 a，也就是把 b 原來的值指定給 a，由此可知當迴圈運作時，b 的值依序為 1、1 + 1 = 2、2 + 1 = 3、3 + 2 = 5、5 + 3 = 8、8 + 5 = 13、...，答案為C。
<br /><br />
9. 請問下列程式輸出為何？
(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);
```
<br />
<span style="font-weight:bold">答案</span>：B
<span style="color:blue">詳解</span>：由程式碼第3到6行可以看出陣列 A = {0, 6, 10, 14, 18}、B = {0, 5, 10, 15, 20}。程式碼第8到15行回迴圈運作時，第1次為 A[1] > B[1]、6 > 5，輸出 c = 1；第2次為 A[2] = B[2]、10 = 10，輸出 c = 1；第3次為 A[3] < B[3]、14 < 15，輸出 c = 1 + (15%14) = 2；第4次為 A[4] < B[4]、18 < 20，輸出 c = 2 + (20%18) = 4，答案為B。
<br /><br />
10. 給定下列 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;
}
```
<br />
<span style="font-weight:bold">答案</span>：C
<span style="color:blue">詳解</span>：本題考函式的遞迴 (recursion)，直接列出運作流程
$$
\begin{align*}
g(13) &= g(11) + 3\\
&= g(9) + 3 + 3\\
&= g(7) + 3 + 3 + 3\\
&= g(5) + 3 + 3 + 3 + 3\\
&= g(3) + 3 + 3 + 3 + 3 + 3\\
&= g(1) + 3 + 3 + 3 + 3 + 3 + 3\\
&= 1 + 3 + 3 + 3 + 3 + 3 + 3\\
&= 19
\end{align*}
$$
<br /><br />
11. 定義 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;
}
```
<br />
<span style="font-weight:bold">答案</span>：D
<span style="color:blue">詳解</span>：for 迴圈中的程式碼會將 a[i] 與 a[i+1] 的元素交換，若要使 a[0] 最後被換到 a[n-1]，最後一次運作時 i = n-2，因此答案為D。
<br /><br />
12. 給定下列函式 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);
}
}
```
<br />
<span style="font-weight:bold">答案</span>：C
<span style="color:blue">詳解</span>：本題考函式的遞迴 (recursion)，呼叫f1(1)之後運作流程如下：
1. 第1層：印出1，呼叫 f2(3)
2. 第2層：印出3，呼叫 f1(2)
3. 第3層：印出2，呼叫 f2(4)
4. 第4層：印出4，遇到 return，結束遞迴，往上層移動
5. 回到第3層：印出2
6. 回到第2層：印出3
7. 回到第1層：印出1，結束程式
C錯誤，f2 被呼叫2次。
<br /><br />
13. 下列程式片段擬以輾轉相除法求 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 />
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：輾轉相除法是以這次計算時的除數作為下次計算時的被除數，這次計算時得到的餘數作為下次計算時的除數，重複這個過程直到餘數為0時，此時的除數就是最大公因數，因此答案為A。
<br /><br />
14. 下列程式輸出為何？
(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);
}
```
<br />
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：本題考函式的遞迴 (recursion)。由於代入的數值很大，要先找出運作規律，例如foo(100) = bar(90) = foo(85) 或是 bar(100) = foo(95) = bar(85)，如果經過 foo 及 bar 各1次，代入的數值減15，當代入的數值小於、等於20可能會結束遞迴。
1. 由於 15106 ％ 15 ＝ 1，因此 foo(15106) = foo(16) = bar(6)，6 <= 10，印出 bar: 6，結束遞迴。
2. 由於 3091 ％ 15 ＝ 1，因此 bar(3091) = bar(16) = foo(11) = bar(1)，1 <= 10，印出 bar: 1，結束遞迴。
3. 由於 6693 ％ 15 ＝ 3，因此 foo(6693) = foo(18) = bar(8)，8 <= 10，印出 bar: 8，結束遞迴。
答案為A。
<br /><br />
15. 若以 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);
}
}
```
<br />
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：直接列出運作過程，一開始先印出輸入的參數值22，接下來在 n != 1 的條件不成立之前不會離開 while 迴圈，印出的 n 值依序為 11、34、17、52、26、13、40、20、10、5、16、8、4、2、1，共16個數字。
<br /><br />
16. 下列程式執行過後所輸出數值為何？
(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);
}
```
<br />
<span style="font-weight:bold">答案</span>：D
<span style="color:blue">詳解</span>：程式分為以下5個步驟
1. count 初始值為10，符合第1個 if 的條件 count > 0，count 被重設為11。
2. 進到第2個 if，符合條件 count > 10，count 被重設為12。
3. 進到內層的 if，由於 12%3 = 0，不符合條件 count % 3 == 4，進到內層的 else，count 被重設為0。
4. 進到第3個 if，if(count) 代表 count 大於1時成立，由於 count = 0，進到 else，count 被重設為16。
5. 印出16。
<br /><br />
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
```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);
}
```
<br />
<span style="font-weight:bold">答案</span>：B
<span style="color:blue">詳解</span>：第10到17行的程式碼，只能夠依序檢測第1到5個數值是否大於第6個數值，而且只會留下最後一次的檢測結果，若執行程式時依序輸入 11 12 13 14 25 20，最後 allBig 為 TRUE，但是20並不是這6個數字中最小的值。
<br /><br />
18. 程式編譯器可以發現下列哪種錯誤？
(A) 語法錯誤 (B) 語意錯誤 \(C\) 邏輯錯誤 (D) 以上皆是
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：編譯器只能發現語法錯誤，例如少了逗號、分號、括號之類的錯誤，通常還會提示出錯處的行號。編譯式或直譯式語言皆有可能發生語意錯誤（邏輯錯誤, logic error），編譯或直譯時無法被發現，可能會回傳預料之外的執行結果。
<br /><br />
19. 大部分程式語言都是以列為主的方式儲存陣列。在一個8x4的陣列(array) A裡，若每個元素需要兩單位的記憶體大小，且若A[0][0]的記憶體位址為 108 (十進制表示)，則 A[1][2]的記憶體位址為何？
(A) 120 (B) 124 \(C\) 128 (D) 以上皆非
<br />
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：A[0][0] 之後依序為 A[0][1]、A[0][2]、A[0][3]、A[1][0]、A[1][1]、A[1][2]，A[1][2] 為 A[0][0] 之後第6個元素，因此記憶體位址為
$$
108 + 6 \times 2 = 120
$$
若二維陣列 A 為 $m$ 列、$n$ 欄（$m \times n$），每個元素使用 $d$ 個位元的記憶體，A[0][0] 的記憶體位址為 $loc_0$，則 A[i][j] 的記憶體位址為
$$
loc = loc_0 + (i \times n + j) \times d
$$
<br /><br />
20. 下列為一個計算 n 階乘 (factorial) 的函式，請問該如何修改才會得到正確的結果？
(A) 第 2 行，改為 int fac = n;
(B) 第 3 行，改為 if (n > 0) {
\(C\) 第 4 行，改為 fac = n * fun(n+1);
(D) 第 4 行，改為 fac = fac * fun(n-1);
```c=
int fun (int n) {
int fac = 1;
if (n >= 0) {
fac = n * fun(n - 1);
}
return fac;
}
```
<br />
<span style="font-weight:bold">答案</span>：B
<span style="color:blue">詳解</span>：本題考函式的遞迴 (recursion)，重點在於第4行執行的規律，按照階乘的定義 $n! = 1 \times 2 \times 3 \times \dots \times (n-1) \times n$，列出幾次運算過程應該就能看出答案，例如
1. fun(0) = 1
2. fun(1) = 1 * fun(0) = 1
3. fun(2) = 2 * fun(1) = 1 * 2 = 2
4. fun(3) = 3 * fun(2) = 1 * 2 * 3 = 6
5. fun(4) = 4 * fun(3) = 1 * 2 * 3 * 4 = 24
6. fun(n) = n * fun(n-1) = n!
因此答案為B。
<br /><br />
21. 下列程式碼，執行時的輸出為何？
(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
```c
void main() {
for (int i=0; i<=10; i=i+1) {
printf ("%d ", i);
i = i + 1;
}
printf ("\n");
}
```
<br />
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：for 迴圈每次運作時，會先印出i的值再將i加1，但是 for 迴圈的增量又會再將i加1，因此印出的值依序為0、2、4、6、8、10。
<br /><br />
22. 下列 f()函式執行後所回傳的值為何？
(A) 1023 (B) 1024 \(C\) 2047 (D) 2048
```c
int f() {
int p = 2;
while (p < 2000) {
p = 2 * p;
}
return p;
}
```
<br />
<span style="font-weight:bold">答案</span>：D
<span style="color:blue">詳解</span>：f() 當中的 while 迴圈每次運作時會將p的值變為2倍，最後一次運作時，p的輸入值為1024，輸出值為2048，因此答案為D。
<br /><br />
23. 下列 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)____ ;
}
}
```
<br />
<span style="font-weight:bold">答案</span>：A
<span style="color:blue">詳解</span>：將選項代入對應的位置，看輸出值是否符合題目的要求，選項A對應的p值分別為2、4、6、8，為正確答案；選項B對應的p值分別為6、8、10，選項C對應的p值分別為2、4、6、8、10，選項D對應的p值分別為6、7、8、9。
<br /><br />
24. 下列 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;
}
```
<br />
<span style="font-weight:bold">答案</span>：C
<span style="color:blue">詳解</span>：本題考函式的遞迴 (recursion)。由於呼叫 g(4) 回傳值為 j = 0 ＋ f(1) + f(2) + f(3)，因此先列出 f(1)、f(2)、f(3) 的運作流程會比較簡單。
$$
\begin{align*}
f(1) &= 1 + f(2) = 1 + 3 + f(3) = 1 + 3 + 1 + f(4) = 1 + 3 + 1 + 1 = 6
\\
f(2) &= 3 + f(3) = 3 + 1 + f(4) = 3 + 1 + 1 = 5\\
f(3) &= 1 + f(4) = 1 + 1 = 2\\
g(4) &= 0 ＋ f(1) + f(2) + f(3) = 0 + 6 + 5 + 2 = 13
\end{align*}
$$
<br /><br />
25. 下列 Mystery()函式 else 部分運算式應為何，才能使得 Mystery(9) 的回傳值為 34。
(A) x + Mystery(x-1) (B) x * Mystery(x-1)
\(C\) Mystery(x-2) + Mystery(x+2) (D) Mystery(x-2) + Mystery(x-1)
```c
int Mystery (int x) {
if (x <= 1) {
return x;
}
else {
return ____________ ;
}
}
```
<br />
<span style="font-weight:bold">答案</span>：D
<span style="color:blue">詳解</span>：最方便的作法是將選項代入程式碼中看輸出結果，為了簡化算式，以下將 Mystery() 簡寫為 M()，選項A計算公差為1的等差級數
$$
M(9) = 9 + M(8) = 9 + 8 + M(7) = \dots = 9 + 8 + 7 + \dots + 1 = 45
$$
選項B計算階乘
$$
M(9) = 9 \times M(8) = 9 \times 8 \times M(7) = \dots = 9 \times 8 \times 7 \times \dots \times 1 = 9! = 362880
$$
選項C不會收斂
$$
M(9) = M(7) + M(11) = [M(5) + M(9)] + [M(9) + M(13)] = \dots
$$
選項D計算費氏數列（費波那契數列, Fibonacci numbers），依序列出 M(0) 到 M(9)
$$
\begin{align*}
M(0) &= 0\\
M(1) &= 1 \\
M(2) &= M(0) + M(1) = 1\\
M(3) &= M(1) + M(2) = 1 + 1 = 2\\
M(4) &= M(2) + M(3) = 1 + 2 = 3\\
M(5) &= M(3) + M(4) = 2 + 3 = 5\\
M(6) &= M(4) + M(5) = 3 + 5 = 8\\
M(7) &= M(5) + M(6) = 5 + 8 = 13\\
M(8) &= M(6) + M(7) = 8 + 13 = 21\\
M(9) &= M(7) + M(8) = 13 + 21 = 34
\end{align*}
$$
因此答案為D。
<br /><br />
---
###### tags:`APCS`、`C`、`C++`
Sign in with Wallet
Connect another wallet