---
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) 許可協議。轉載請標明作者、連結與出處！
Sign in with Wallet
Connect another wallet