# APCS 觀念題資源分享
APCS筆試歷屆(11106)
https://hackmd.io/@algoseacow/APCS11106-writing
APCS筆試歷屆(11101)
https://hackmd.io/@algoseacow/APCS11101-writing
APCS筆試歷屆(11001)
https://hackmd.io/@rollfatcat/ByEIVsekd
https://hackmd.io/@rollfatcat/H12Z4Qgku
APCS筆試歷屆(10910)
https://hackmd.io/@cthbst/APCS_10910#APCS-1091017
APCS筆試歷屆(11011)
https://hackmd.io/@algoseacow/APCS11011-writing
APCS筆試題目分類
https://hackmd.io/@algoseacow/apps-written
APCS官網制定考試範圍
https://apcs.csie.ntnu.edu.tw/index.php/questionstypes/
(C++ 講義) https://hackmd.io/@Distinguished/HJCZMKM8t
(C++ 講義) https://cp.wiwiho.me/
## 題目種類分析
通常 APCS 的觀念題會用到些許考古題(大概從2023/6月開始變少)跟最新出的題組
新出的題組大部分是較難的程式碼片段(具有特定功能)，或是特殊設計的資料結構題組
新出的最後會拉出來做一個討論(因為比較難)，在此先說比較早期的出題方式(現在還會這樣出)
最後要保證同學**已經學會所有觀念題所需知識**，以免出現不認識名詞或是 function 的問題
還有希望**先自己做過題目**，再看看我介紹的解法有沒有比你得快
### 出題方式/分數說明
出題方式大約分成四種 : Debug(除錯)、不可能的輸出(入)、執行程式碼片段和挖空
目前不可能的輸出比較少出了(考古題還是有)，所以等等會用較少篇幅去介紹
剩下的題目就是一些關於 $C/C++$ 的語法問題
插個感言，最近的 APCS 觀念題有點走火入魔了，我覺得最頂考 $4$ 級分就差不多了
$5$ 級分更多還是看運氣+天賦，技巧甚麼的都不一定能比剛好猜對還強
不過 $3$ 級分我覺得還可以再努力，因為 $4$ 級分是 $70 \sim 89$
range 還是蠻大的，差不多可以錯 $7\sim8$ 題(運氣不好的情況下)
APCS 實際的評分方式是從 $40$ 題裡面挑 $25$ 題，然後一題四分，會根據%數挑題
也就是要讓 $5$ 級分的人數不要太多，所以才說運氣很重要
還有最近題目越來越偏向**計算快速**，**熟悉程式碼運算**的人了，~~師大教授大概心情不好~~
### 解題方法
接下來會依照解題速度由快到慢介紹四種解題方法
1. 直接記住題型
2. 找規律、帶選項
3. 依照程式邏輯推測(省略計算)
4. 大腦計算程式碼片段(直接計算)
通常都是**由這四種方式去做延伸**，在對於各種題型做出**變化的解法**
但我的方法不一定適合你，如果**有幫助再拿去用**
實際遇到題目的時候我會依據下述題目特性去跳過某些難題
* 看題目一分鐘還想不出解法
* 解到一半卡了一分鐘就跳過
* 比較複雜的程式碼(例如題組和某些功能程式碼片段)
直到 $20$ 都 run 過一遍後再依照下面步驟去做，想不出來要適時放棄
1. 先檢查/確認之前會解但有點不確定的
2. 去解卡一半的題目
3. 去解題組
4. 去解複雜的程式碼
5. 去解之前想不出解法的題目
6. 剩一分鐘就把之前沒寫的題目猜一猜
至於如何去標記那些沒有解的題目，我建議考前直接在紙上留一小格空間去寫數字 $1 \sim 20$
然後再用自己記得的符號去標記，比如我都用三角形去做標記
### 題組簡介
題組大部分都是 stack 或是 queue 的變形，通常為了防止你直接看出
會把一些功能做出改變，例如: pop 改成一次取出所有元素並輸出
一次包含 $2\sim3$ 題，所以只要能理解程式碼的核心功能，題組就非常有 CP 值
## 變數(variable)、視域(scope)
變數能考的東西不多，大部分都是很基礎的題目，算是送分題，如果平時有在碰 C++ 應該都能輕鬆過
### type 運算
```cpp=
int a = 7, b = 3 ;
float w = a / 2 / b * 1.0 ;
float x = a / b / 2.0 ;
float y = a / 2 / b ;
float z = 1.0 * a / 2 / b ;
```
問 $w, x, y, z$ 中何者異於其他三者
(A) w
(B) x
(C\) y
(D) z
分析 :
簡單的變數運算，這種直接算就可以了，唯一要注意的就是
有沒有運算優先級，比如先乘除後加減，小括號優先運算等等
### 視域(scope)
所謂的視域就是去看 global 跟 local 的變數
要注意在 function 當中 local 的優先級大於 global
也就是說會優先對 local 執行修改、輸出、運算、回傳等動作
在找不到 local 的情況下才會使用 global
```cpp=
void f(int a, int b) {
a = a + b;
b = a - b;
}
int main() {
int a = ____, b = ___;
f(a, b);
printf("%d %d\n", a, b);
}
```
已知 $a = 31, b = 3$ ，試問輸出為何
(A) 31 28
(B) 34 28
(C\) 31 3
(D) 34 31
分析 :
這題要先考慮 function $f$ 當中的 local，從上面程式碼片段
`void f(int a, int b)` 得知 local 變數是 $a, b$ 兩者
也就是說在 $f$ 內所作的行為不會影響到 main 中的 $a, b$
更不用說 main 中的 $a, b$ 是 local，而 local 不會影響到其他 local
所以答案是 \(C)
```cpp=
int a = 5, b = 3 ;
void f(int a, int b) {
int c = a + b ;
}
int g(int a, int b) {
a = a + b ;
b = a - b ;
int c = a + b ;
return c ;
}
int main() {
int b = 7 ;
int c = g(a, b) ;
f(a, b) ;
int a = 3 ;
printf("%d %d %d\n", a, b, c) ;
}
```
問輸出為何
(A) 3 7 17
(B) 5 7 17
(C\) 3 3 17
(D) 3 7 8
分析 :
這題要先考慮變數使用的優先級，優先級是 global < local
而 local 只能考慮在目前 function 中的變數，也就是說`a == 3` 且 `b == 7`
在 $f$ 沒有回傳值的情況下，$c$ 會被定義為`g(a, b)` 回傳的值，而不是 $f$ 中的`a+b`
所以答案是 (A)
### 布林(bool)運算
已知 `x1 = true, x2 = false, x3 = true`
問 `x1 && (!(x1 && x2) || x3)` 跟下列哪個選項的結果相同
(A) `x2`
(B) `(!(x1 && x3) && (x1||x2))`
(C\) `!(x1) || !(x2 || x3)`
(D) `((!(x1 && x3) || x2) && x3) || x1`
分析 :
這種題目可以先看題目給的值是甚麼，比如這題給 true，那就先做每個選項中的 OR 運算
因為 OR 只要左右邊有一個是 true 就是 true，反之 AND 運算只要左右邊有一個 false 就是 false
所以這題答案是 (D)
## 控制結構、條件判斷(if/switch)
條件判斷單獨拉出來的題目通常就是計算成績等第、debug(刪除或修改)和程式應用(直接)
這些題目大多都不困難，都算是 $0.5 \sim 1$ 分鐘內可以解決的
### if 判斷
```cpp=
int main() {
int x = 89, y = 70 ;
char grade = 'D' ;
if ((x >= 90 && y >= 60) || (y >= 90 && x >= 60)) {
grade = 'A' ;
}
else if ((x >= 80 && y >= 60) || (y >= 80 && x >= 60)) {
grade = 'B' ;
}
else if ((x >= 70 && y >= 60) || (y >= 70 && x >= 60)) {
grade = 'C' ;
}
printf("%c", grade) ;
return 0 ;
}
```
請問輸出為何
(A) A
(B) B
(C\) C
(D) D
分析 :
這種題目直接讀懂分數的分級條件，比如這題就是有一個分數及格
另外一個分數依照 $90$ - $80$ - $70$ 做出區分
所以只要看比較大的分數在哪個級距，還有比較小的分數有沒有及格
較大的分數為 $89$，較小的分數是 $70$，所以答案是 (B)
### if-程式應用
```cpp=
int f(char s[], int n){
char ans[1000] ;
int j = 0;
for (int i=0; i<n; i++, j+=2){
if (s[i] == '0'){
ans[j] = 'w';
ans[j+1] = 'a';
} else if (__1__ || __2__){
ans[j] = 't';
ans[j+1] = 'e';
} else if (s[i] == '3' || s[i] == '5'){
ans[j] = 'd';
ans[j+1] = 'o';
} else if (s[i] == '4' || s[i] == '6'){
ans[j] = 'p';
ans[j+1] = 'u';
} else {
ans[j] = ' ';
j = j-1;
}
}
ans[j] = '\0';
printf("%s", ans);
}
int main(){
char s[] = "0328675";
f(s, 8) ;
}
```
已知最後輸出結果為 "wadote putedo"，(雙引號可省略)
問題目中填入什麼判斷式
(A) `s[i] == '3'`，`s[i] == '7'`
(B) `s[i] == '2'`，`s[i] == '7'`
(C\) `s[i] == '3'`，`s[i] == '8'`
(D) `s[i] == '2'`，`s[i] == '8'`
分析 :
這題可以直接做計算或是找數字對應的字元
在這邊先做總結 $0$ => "wa"，$3,5$ => "do"，$4,6$ => "pu"，$?,?$ => "te"
當然也可以直接看 "te" 對應的兩個數字去作答，會比全部找完快，答案是 (A)
### if-沒有括號的陷阱
```cpp=
int main() {
int x = 4, a = 0 ;
if (x >= 2)
if (x < 6)
a = 1 ;
else
a = 2 ;
else
a = 3 ;
}
```
問 $a$ 最後為多少
(A) 0
(B) 1
(C\) 2
(D) 3
分析 :
因為沒有括號只有縮排，但是**縮排有可能會誤導你思考錯誤**
不過這題並沒有縮排錯誤，所以可以直接看 $a = 1$
答案是 (B)，至於不使用括號的方式，簡單介紹一下
在不使用括號的情況下，if 中可以放任何 if-else if-else 語法(只能接**一句敘述或是 if 家族**)
舉一個下列的程式，縮排是正確的，$a$ 是 $1$
```cpp=
if (x > 3)
if (x > 5)
a = 4 ;
else if (x > 4)
a = 3 ;
else if (x > 6)
a = 2 ;
else
a = 1 ;
else
a = 0 ;
```
### switch
switch 要注意兩個特性
1. 如果 case 中不加入 break 會無限下墜
2. 現階段可以把 default 當作 else
第一個特性可以搭配下面的題目去理解
```cpp=
int main() {
int a = 2 ;
switch(a) {
case 1+1:
printf("A") ;
case 1+2:
printf("B") ;
break;
default:
printf("??") ;
}
return 0;
}
```
問輸出為何
(A) A
(B) B
(C\) AB
(D) ??
分析 :
可以看到最上面的 case 沒有加入 break 且 $1+1=2$
所以進入 switch 後會直接到第一個 case，然後輸出 "A"
但是因為沒有遇到 break，所以會直接到第二個 case，然後輸出 "B"
最後遇到第 $8$ 行的 break，然後跳出 switch，答案為 (C)
### switch-if
給定兩個程式碼片段，問空格填入多少時會有不同輸出
```cpp=
int main(){
int n = __1__ ;
switch(n){
case 90 :
printf("A") ;
case 80 :
printf("B") ;
case 70 :
printf("C") ;
default :
printf("D") ;
}
}
```
```cpp=
int main() {
int n = __1__ ;
if (n >= 90) {
printf("A") ;
}
else if (n >= 80) {
printf("B") ;
}
else if (n >= 70) {
printf("C") ;
}
else {
printf("D") ;
}
return 0 ;
}
```
(A) 69
(B) 71
(C\) 70
(D) 不論填入什麼數字，兩者都有不同輸出
## 迴圈控制(for/while loop)
迴圈控制的題目比較多種，例如三層迴圈、不可能的輸出、迴圈+陣列、輸出星星和程式應用等等
這些題目大多都不困難，都算是 $1$ 分鐘內可以解決的
### while-程式應用
```cpp=
int main() {
int sum = 1, p = 5, a = 2 ;
while (p >= 0) {
sum = sum * a ;
p = p - 1 ;
}
printf("%d", sum) ;
}
```
已知此程式片段想要達到 $a^p$，問下列何種修改正確
(A) 將第 $5$ 行修改成 `p = p - 2 ;`
(B) 將第 $3$ 行修改成 `p > 0`
(C\) 將第 $4$ 行修改成 `sum = sum * p ;`
(D) 無須修改
分析 :
這題只要想清楚迴圈的重複次數即可，因為條件是 `p >= 0`
所以最後迴圈會執行 $p+1$ 次，也就是說最後答案是 $a^{p+1}$
只要修改 while 中的條件式就可以了，答案是 (B)
### for-印出星星
```cpp=
int n = 4 ;
for (int i=0;i<n;i++) {
for (int j=0;j<4;j++) {
if (j<__1__ || j>__2__)
printf('*') ;
else
printf('%d', 2*i+1) ;
}
printf("\n") ;
}
```
已知想達到下敘效果
```
***1
**3*
*5**
7***
```
問挖空處填入
(A) `n-i-1`、`n-i`
(B) `n-i`、`n-i`
(C\) `n-i`、`n-i-1`
(D) `n-i-1`、`n-i-1`
分析 :
這題直接從輸出的第二或第三行找規律，因為數字左右都有星星
從第二行來判斷，此時 $i=1$ 所以 $3$ 所在的位置是 $j = n-i-1 = 4-1-1 = 2$
正好對應到 $0,1,2$ 的格式(兩個星星一個數字)，所以就知道答案是 (D)
### while+if-不可能的輸出
```cpp=
int f(int n) {
if (n > 17)
n += 5 ;
while (n >= 23)
n -= 6 ;
if (n > 17)
n += 2 ;
return n ;
}
```
問下列四個選項，哪個不可能是 $f$ 回傳值
(A) 23
(B) 21
(C\) 19
(D) 17
分析 :
這種題目通常是看 while 結束後 $n$ 值的所有可能
比如這題可以從 $23,24,25,26,27,28$ 去推測最後結果
當 while 結束時(即將執行第 $6$ 行)，會有幾種可能 $17,18,19,20,21,22$
這六個數字只有 $17$ 不會受到第 $6$ 行的 if 影響改變
所以最後的結果可能就是 $17,20,21,22,23,24$
不過也可以利用反推法代入選項，這比較適合**對程式熟悉**又**計算快速**的人
把四個選項反推回去就知道會出現錯誤，所以答案是 (C)
```cpp=
int f(x) {
if (x > 12)
x = x + 5 ;
while (x < 14)
x = x + 3 ;
x = x - 3 ;
return x ;
}
```
問下列四個選項，哪個不可能是 $f$ 回傳值
(A) 12
(B) 14
(C\) 19
(D) 16
分析 :
這題就比較有意思了，因為我塞了兩個選項讓上一題介紹的只看 while 失效
如果只看 while，答案的可能只有 $11,12,13$，剩下三個選項都不確定
所以就用反推法，雖然速度比較慢而且很吃天賦，但是能保整所有情形都能推出來
先推 $16$，第 $6$ 行 $16+3$ => $19$，迴圈跑出來最多是 $15$，所以推出沒過迴圈
最後第 $3$ 行回推 $19-5$ => $14$，第 $2$ 行條件式也成立，最後知道 $x$ 是 $14$
剩下的數字也一樣，都推出來後發現 $14$ 在第 $2$ 行條件式會出現錯誤 => 答案是 (B)
### for迴圈執行次數判斷(偏數學)
```cpp=
int j = 0;
for (int i = 0; i < 128; i = i + j + 1)
j = i + 1 ;
```
問迴圈執行次數
(A) 3
(B) 5
(C\) 7
(D) 9
分析 :
這種題目需要做小測資找規律，所以直接先運算看看
第一次迴圈 $i = 0, j = 0+1, i = i+j+1 = 0+1+1 = 2$
第二次迴圈 $i = 2, j = 2+1, i = 2+3+1 = 6$
從上述這兩個執行過程做刪減可以知道 $i = i+j+1 = i+i+1+1 => 2i+2$
那麼就可以做快速計算 $0,2,6,14,30,62,126$，得知執行次數是 $7$ 次，答案是 (C\)
### for-三層迴圈
```cpp=
int x = -100 ;
for (int i=1;i<=8;i++)
for (int j=1;j<=i;j++)
for (int k=1;k<=j;k++)
x += 1 ;
printf("%d", x) ;
```
問輸出為多少
(A) 19
(B) 20
(C\) 21
(D) 22
分析 :
通常這種題目我會先跳過，除非剛好可以套公式，不過這種題目其實很簡單
都只是找規律然後代公式(或是估算)而已，比如這題我們知道最外層的 $i$ 可以跑 $8$ 次
而中間的 $j$ 會跑 $i$ 次，所以總體來說就是 $1,2,3,...,8$ 次
最內層的 $k$ 會跑 $j$ 次，所以就是 $1,\ 1+2,\ 1+2+3,\ ...+8$
所以只要計算 $k$ 層總共跑幾次 $+x$ 就可以了，直接代公式
\begin{aligned}
\cfrac{n(n+1)(n+2)}{6}
\end{aligned}
代入 $n = 8$ -> $120$，$120-100 = 20$，答案為 (B)
這些公式以後算數學也會用到，直接背起來就好(~~然後我懶得證明，請自己用 $\sum$ 證~~)
### for-程式應用
```cpp=
int main() {
int arr[] = ____ ;
int a = 0 ;
for (int i=0;i<5;i++)
for (int j=0;j<5;j++)
if (arr[i]-arr[j] <= a)
a = arr[i] - arr[j] ;
printf("%d\n", a) ;
int b = 0 ;
for (int i=0;i<5;i++)
for (int j=i;j<5;j++)
if (arr[i]-arr[j] <= b)
b = arr[i] - arr[j] ;
printf("%d\n", b) ;
}
```
試問當陣列 arr 的值為下列何者時，$a$ 和 $b$ 會是不同值
(A) $5, 4, 3, 2, 1$
(B) $1, 2, 3, 4 ,5$
(C\) $4, 1, 5, 3, 2$
(D) $2, 3, 1, 4, 5$
分析 :
通常這種題目會先看四個選項之間有甚麼相同/異處，還有程式片段大致的功能
比如這題由第 $8$ 行、第 $15$ 行得知，$a,\ b$ 大概率跟陣列中兩數的最小差(最小值-最大值)有關
再去看選項當中的差異可以發現，B、C、D 的最小值都在最大值前，所以選 (A)
當然這樣的作法不能保證一定有用，所以我通常會在做完全部題目(按照步驟)之後**優先檢查**
比較保險的答題方法就是去看**兩個 for 迴圈的差異處**，從題目得知，兩迴圈的 $j$ 起始值不一樣
所以 $b$ 會變成是計算數 $x$ 跟數 $x$ 後方的數 $y$ 之差，所以在 (A) 會出現 $a$ 和 $b$ 值不同
### 少見語法 do-while
```cpp=
int f(int x) {
int ans = 0 ;
do{
ans += x ;
} while (ans >=0 && ans <= 10) ;
return ans ;
}
int main(){
int x = _____ ;
while (x <= 40) {
x = x + f(x) ;
}
cout << x << endl ;
}
```
給定上述程式碼片段，問下列填入數值和輸出關係何者正確
(A) $2$、$58$
(B) $1$、$50$
(C\) $5$、$80$
(D) $4$、$62$
分析 :
do-while 語法很少見到，因為要在特殊情況下才會比較好用，只要知道意思即可
這題唯一的解法就是直接計算，不過從 $f(x)$ 還是可以得知兩點
1. 如果傳入的值 $x > 10$，那回傳值就是 $x$ 本身($x$ 直接乘 $2$)
2. 如果傳入的值 $x < 10$，那回傳值就是 $x$ 大於 $10$ 的最小倍數
所以可以對上述的數字進行快速運算，算法如下所述
* $2$ : $2+12+14+26=56$
* $1$ : $1+11+12+24=48$
* $5$ : $5+15+20+40=80$ (答案)
* $4$ : $4+12+16+32=64$
拿數字 $2$ 做解釋，原本的 $2$ 加上 $x$ 大於 $10$ 的最小倍數 $12$
此時 $x$ 是 $14$，所以再 $\times2$，$x\ =\ 28$ --> $x \times 2 = 56$
其他三數應該可以自己推一遍，比直接運算來的快，去找程式片段的邏輯運算
---
最後做個總結，其他題目會混搭其他觀念，所以程式碼片段也能更豐富(更難)
這裡勉強拉了一個最簡單的一維陣列，還是有點離題，因為只有 for 迴圈的應用場景不多
## 陣列(一維/多維)
陣列的題目不外乎就是跟 index 有關，最多再加入 for 迴圈或遞迴讓矩陣產生變化
或是用二維陣列要看 $i,\ j$ 去迷惑你而已，總體來說不難解但是難算
尤其是讓矩陣展生變化的題目，通常只能硬解，而且一步錯步步錯，所以需要更多細心
在陣列的部分也有題目是建議直接跳過的
### 一維陣列
```cpp=
int num[10] ;
for( int i=0;i<10;i=i+1)
scanf("%d", &num[(i+6) % 10]) ;
```
已知輸入為 $10,9,8,...,1$，請問陣列中的數字為下列何者
(A) $6, 5, 4, 3, 2, 1, 10, 9, 8, 7$
(B) $5, 6, 7, 8, 9, 10, 1, 2, 3, 4$
(C\) $4, 5, 6, 7, 8, 9, 10, 1, 2, 3$
(D) $9, 8, 7, 6, 5, 4, 3, 2, 1, 10$
分析 :
這種單純考 index 的題目不難，計算時間也不多，就直接做就可以了
如果硬要說比較快的方式就是直接從選項找答案，計算前三個後直接找選項
輸入 $10$ 會放在 $(0+6)\ \%\ 10$ 的地方，也就是 index $6$ 的地方
然後 $9$ 就放在 $10$ 的下一個，最後答案就是 (A)
### 一維陣列-index
```cpp=
int f(){
int a[5] = {9,2,4,7,3} ;
int b[10] = {0,1,0,1,0,1,0,1,0,1} ;
int c = 0 ;
for (int i=0;i<5;i=i+1) {
c += b[a[i]] ;
}
return c ;
}
```
問回傳值 $c$ 為何
(A) 1
(B) 2
(C\) 3
(D) 5
分析 :
這題的 $c$ 就是讓 $a[/ i/ ]$ 當作 $b$ 的 index
而且陣列 $b$ 只有 index 是奇數的時候才會有 $1$
最後只要看陣列 $a$ 當中有幾個奇數就是答案
答案是 (C\)，不過這題也可以直接計算
因為剛剛的解法考試未必能想到，這題用直接解的方式也可以
### 一維陣列-較複雜
```cpp=
int Q[30] ;
int count = 0 ;
int front = 0 ;
int back = 0 ;
for (int i=1;i<=15;i=i+1) {
Q[back] = i ;
back = back + 1;
}
while (front < back-1) {
int v = Q[front] ;
front = front + 1 ;
count = count + 1 ;
if (count == 3) {
count = 0 ;
Q[back] = v ;
back = back + 1 ;
}
}
printf("%d", Q[front]) ;
```
問輸出為多少
(A) 6
(B) 15
(C\) 9
(D) 12
分析 :
這題比較複雜是因為有一個自訂資料結構的出現
從第 $5$ 行的 for 迴圈可以知道，陣列 $Q$ 是 $1,2,3,...,15$
還有 back 是目前陣列長度，再來就可以看第 $9$ 行的程式
從程式片段可以看出這個部分應該是將數值加入陣列後段
而這個數值會根據 count 去加入，也就是每三個數字加入一個
最後就知道數字會依序加入 $3,6,9,12,15$
但是此時因為新加入的數字所以 while 迴圈不會結束，會再加入 $9$
變成 $12,15,9$ 後會再加入一次 $9$，答案要看最後面的值，所以答案是 (C\)
### 二維陣列
```cpp=
int s1[2][2] = {0, 1, 2, 3} ;
int s2[2][2] = {4, 3, 2, 1} ;
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)
printf("%d ", s1[i][j] * s2[j][i]) ;
```
問輸出為多少
(A) 0 2 3 6
(B) 2 0 6 3
(C\) 2 0 3 6
(D) 0 2 6 3
分析 :
這段程式碼就只是在考對於二維陣列的 index 值，從題目可知 $0\times4、1\times2、2\times3、3\times1$
所以答案就是 $0\ 2\ 3\ 6$，(A)
### 二維陣列-較複雜
```cpp=
int s1[3][3] ;
int s2[3][3] ;
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++) {
s1[i][j] = i*j ;
s2[j][i] = i*j ;
}
}
int sum = 0 ;
for (int i=0;i<3;i++) {
for (int j=0;j<3;j++) {
sum = sum + s1[i][j] * s2[i][j] ;
}
}
printf("%d", sum) ;
```
問最後輸出為何
(A) 0
(B) 15
(C\) 20
(D) 25
分析 :
從第 $3$ 行到第 $8$ 行是陣列的初始化，其實兩者的元素會是一樣的，只要計算後就知道
所以最後只要在紙上寫出兩陣列的值就可以計算陣列元素相乘的總和
答案是 (D)
## 字串
字串最常見的考法就是 ASCII，也因為字串本身跟陣列有些許相同性質，所以會較類似於陣列的題目
基本上有可以直接背起來的，比如迴文(正讀反讀都相同)，因為性質簡單明瞭，等等用題目解說
### 字串-ASCII
```cpp=
char a[] = {'a','b','c','d','e','f','g','h','i'} ;
for (int i=0;i<9;i++)
a[i] = a[i] + i * 2 ;
```
問程式碼片段執行過後，下列何者正確
(A) a[0] == c
(B) a[3] == m
(C\) a[5] == m
(D) a[1] == g
分析 :
這題只要看字元的 ASCII 就可以知道答案，可以直接把前 $4$ 個算出來
`a[0] = 'a' + 0*2, a[1] = 'b' + 1*2, a[3] = 'c' + 2*2, a[4] = 'd' + 3*2`
最後 `a[0] = 'a', a[1] = 'd', a[2] = 'g', a[3] = 'i'`，其實在陣列當中都可以數出來
最後發現答案是 (C\)，因為 (A)、(B)、(D) 都錯
### 字串-ASCII
```cpp=
char s[] = {'a', 'b', 'a', 'b', 'a', 'a'};
void f(char x) {
for (int i=0;i<7;i++) {
if (s[i] == 'a')
_____
else
s[i] = x ;
}
}
int main() {
f('a');
for (int i=0;i<7;i++)
printf("%c", s[i]);
}
```
問瑱入的程式碼跟對應的輸出，下列何者正確
(A) `s[i] = 'a'`，ababab
(B) `s[i] = 'b'`，abbbbb
(C\) `s[i] = 'a'`，abaaaa
(D) `s[i] = 'b'`，bbbbbb
分析 :
這一題可以看 if 跟轉變值的關係，挖空處是在 `if (s[i] == 'a')` 當中，所以如果 `s[i] = a`，等於字串根本沒變
如果 `s[i] = b`，那就是把所有 'a' 的位置換成 'b'，所以答案是 (D)
### 字串-迴文
```cpp=
bool isPal(const char *s) {
int p = 1 ;
int len = strlen(s) ;
for (int i=0;i<len/2-1;i++) {
if (s[i] != s[len-i-1])
p = 0 ;
}
return p ;
}
```
已知此程式片段想要達成判斷迴文的功能，試問需要修改哪一行這個 function 才會正常運作
(A) line 3 改 `for (int i=0;i<len/2;i++) {`
(B) line 3 改 `for (int i=0;i<len/2+1;i++) {`
(C\) 程式沒有任何錯誤
(D) line 6 改成 `p = 1 ;`
分析 :
迴文的基本概念是從頭尾讀起來都相同，所以當在判斷迴文時判斷從頭和從尾數來第 $i$ 個值相同
基本上這段可以直接背起來(因為常考)，如果判斷兩值不同就 return 0
因為如果以題目給定的 for 迴圈去跑字串會讓中間的兩個字元被忽略
比如: "112111" 應該是錯誤的，但是因為迴圈範圍 $[\ 0,6/2-1\ )$ => $[\ 0\sim2\ )$
最後會沒有判斷到中間的 "21"，導致錯誤產生，所以答案是 (A)
### 字串-程式應用
```cpp=
void f(char s[], char k[], char out[]) {
int i = 0 ;
while (i < 8) {
if (s[__1__] == k[__2__])
out[i] = '0' ;
else
out[i] = '1' ;
i++ ;
}
}
int main() {
char x[] = "000011110" ;
char y[] = "100110001" ;
char z[] = "000000000" ;
f(x, y, z) ;
f(z, y, x) ;
printf("%s", z) ;
}
```
已知輸出為 “100001100”，問兩格填空分別為
(A) $i$ 、 $i$
(B) $i-1$ 、 $i+1$
(C\) $i+1$ 、 $i$
(D) $i$ 、 $i+1$
分析 :
這題要先看懂 function 的功能，因為字串在 function 當中會被直接改變(原因可以去複習指標)
所以在執行第 $15$ 行的時候，$x$ 字串和 $y$ 字串是用來被判斷的，$z$ 字串是被修改的
因為題目最後只有輸出字串 $z$，所以第 $16$ 行(修改 $x$ 字串)可以忽略
最後只要看題目輸出的 $z$ 字串帶入選項哪個對，或是用 $x$ 和 $y$ 去推也可以，時間差不多，答案是 (C\)
### 字串-ASCII進階變化
```cpp=
void func(char *s) {
char mp[] = "IEFGHDJKLMNOPCRSTUVWXYZABQ" ;
int len = strlen(s) ;
for (int i=0;i<len;i++) {
int c = s[i] - 'A' ;
printf("%c", mp[c]) ;
}
}
```
已知輸出結果為 `FIHVIU`，問 $s$ 陣列可能為下列何者
(A) DBFTBS
(B) CBESBR
(C\) FIHVIU
(D) CAESAR
分析 :
這題是用 ASCII 進行字串加密，題目中用字元跟 'A' 之間的距離當作 index
然後從 mp 當中找對應的值，建議可以在紙上寫一個如下述的對應表
```
IEFGHDJKLMNOPCRSTUVWXYZABQ
01234567890123456789012345
ABCDEFGHIJKLMNOPQRSTUVWXYZ
```
從對應表可以快速知道 `FIHVIU` 對應的值是 `CAESAR`，所以答案是 (D)
中間有一行數字是因為不是每個人都可以直接寫出字母對應表，但是可以先找出 $c$ 的值
## 函式/遞迴
遞迴是考試當中比較花費時間的部分，因為大部分遞迴題目比較麻煩
不能透過找規律等快速方法得知答案，只能用大腦計算程式碼片段的方式
不過即使是直接計算，同樣有更好的辦法去解題，也就是圖
因為遞迴用圖表示可以明顯**突出先後關係**，而且遞迴的**本質就是 stack**，所以也是結構
後面的東西都太理論了，等等會用題目分析去解釋如何使用圖解
### 函式-多個函式呼叫
```cpp=
int op3(int i, int j){
return i * j ;
}
int op2(int g, int h){
return g * op3(g, h) ;
}
int op1(int e, int f){
return op2(e, f) ;
}
int a = 1, b = 2, c = 1, d = 2 ;
```
問下列四個有幾種不同的值
```
op1(op2(op3(b, d), c), a) ;
op2(op3(op1(d, c), a), b) ;
op3(op1(op2(c, a), d), b) ;
op3(1, op1(op2(b, c), d)) ;
```
(A) 1
(B) 2
(C\) 3
(D) 4
分析 :
遇到這種題目都先**簡化邏輯**，比如 op2 `return g * op3(g, h)` => `return g * g * h`
所以 op1 => `return op2(e, f)` => `return e * e * f`
最後只要帶入題目給定的程式碼就可以得知下述的值
```
op1(op2(op3(b, d), c), a) => 256
op2(op3(op1(d, c), a), b) => 32
op3(op1(op2(c, a), d), b) => 4
op3(1, op1(op2(b, c), d)) => 32
```
有三種不同的值，答案是 (C\)
### 遞迴-debug
```cpp=
int sum(int n) {
if (n == 1)
return 1 ;
return n * (n-1) + sum(n-1) ;
}
int main() {
sum(10) ;
}
```
已知題目想要達到 $1\times 2+2\times 3+3\times 4+...+9\times 10$ 的效果，請問下列何者正確
(A) 第 $3$ 行要改成 `return 0 ;`
(B) 第 $4$ 行要改成 `return (n-1) * n + sum(n - 1) ;`
(C\) 第 $2$ 行要改成 `if (n == 2)`
(D) 程式碼沒有錯
分析 :
遞迴當中有兩個東西特別重要
1. 終止條件(base case)
2. 遞迴式
比如這題程式片段當中的遞迴式就是 `return n * (n-1) + sum(n-1) ;`
如果將 $n$ 帶入一個數字就知道遞迴式沒錯，題目想要的效果就是 $n\times n-1$
這時候就可以看終止條件有沒有問題，可以從接近 $n$ 的地方去判斷
如果 $n=2$， `return 2 * (2-1) + sum(2-1) ;`
再處理` sum(2-1)` => `sum(1)` => $1$
最後發現結果是 $2\times1+1$，比題目預期的 $1\times2+2\times3+...$ 多了一個 $1$
這是因為終止條件沒有寫好，所以找到錯誤是 $n == 1$ 時的 return 值
如果改成 `return 0` 就可以避免多出一個數字，所以答案是 (A\)
### 遞迴-執行前後關係
```cpp=
void f1(int) ;
void f2(int) ;
void f1(int i) {
if (i < 10) {
f2(i - 2) ;
printf("%d ", i) ;
}
}
void f2(int i) {
if (i > 0) {
printf("%d ", i) ;
f1(i - 1) ;
}
}
int main() {
f2(9) ;
}
```
問輸出結果為何
(A) $9\ 8\ 6\ 5\ 3\ 2$
(B) $2\ 3\ 5\ 6\ 8\ 9$
(C\) $3\ 2\ 5\ 6\ 8\ 9$
(D) $9\ 6\ 3\ 2\ 5\ 8$
分析 :
這種分析遞迴之間關係的通常畫圖解最快
### 遞迴-普通
```cpp=
int f(int i) {
if (i%3 != 0) {
if (i == 1 || i>50)
return 5 ;
else
return i + f(i+1) ;
} else
return f(i+2) ;
}
```
問 $f(3)$ 回傳值為多少
(A) 445
分析 :
### 遞迴-帕斯卡三角形
```cpp=
int p(int n, int k) {
if (k == 0)
return 1 ;
else if (k == 1)
return n ;
else
return n * p(n - 1, k - 1) ;
}
p(5, 4) ;
```
問回傳值為多少
(D) 120
分析 :
## 數學
程式和數學有很多分不開的地方，在 APCS 中通常會放入比較典型的例子
費式數列、質數、帕斯卡三角形和等比(差)數列等等，其中有些公式可以背起來
之後在寫題目或式數學都可以用到，公式放在最下面的考前建議
### 最大公因數-gcd
```cpp=
int f1(int a, int b){
if (b == 0)
return a ;
return f1(b, a % b) ;
}
int f2(int a, int b) {
if (b == 0)
return a ;
int c = a % b ;
a = b ;
b = c ;
return f2(a, b) ;
}
int f3(int a, int b) {
int t = 1 ;
while(t != 0) {
t = a % b ;
a = b ;
b = t ;
}
return a ;
}
int f4(int a, int b) {
if (a <= 0 && b <= 0)
return b-a ;
return f4(a - b, a) ;
}
```
問下列三個側資$(18,36)$、$(42,18)$、$(16,32)$，有可能在下列哪個函式當中回傳值與其他函式回傳值不同
(A) f1
(B) f2
(C\) f4
(D) 四個函式回傳值都相同
分析 :
這題直接帶選項，因為用推理的方式去找答案太慢了，直接把數字帶進去算就可以
最後算出來應該是 $(42,18)$ 這組測資在 f4 會出現錯誤值，答案是 (C\)
## 其他
其他題目都是一些現在通常只出 $0\sim1$ 題，而且通常都是考古題
建議直接把解法背起來，反正平常也很少用到題目的用法
### 巨集(define marco)
```cpp=
#define add(a, b) a+b
int main() {
printf("%d\n", add(3, 5) * add(3, 5)) ;
}
```
問輸出結果為多少
(A) 23
(B) 64
(C\) 34
(D) 程式碼發生錯誤
分析 :
通常很少人會用這種方式，不過實際上就是把數字替換出來就可以了
比如這題就會替換成 $3 + 5 \times 3 + 5$，所以答案是 (A)
### 指標
```cpp=
void f(int *arr) {
// ...
}
int main() {
int arr[10] = {1} ;
f(arr) ;
}
```
問傳入函式 $f()$ 的是下列何者
(A) 0
(B) 1
(C\) 陣列的所有數字
(D) 陣列的位址
分析 :
關於指標更詳細知識不在這裡講解，這題只是考陣列傳入函式的問題而已
傳入的方式是用指標，也就是只有儲存陣列的地址，所以答案是 (D)
比較容易不懂得問題大概就是陣列為什麼可以直接傳入
而不需要另外一個指標，原因是陣列名稱本身就是指標
其指向陣列的第一個元素
### struct
```cpp=
struct A {
int x, y ;
char name[20] ;
}P, Q, B[10] ;
```
問下列何者會出現編譯錯誤
(A) `P.x = Q.y ;`
(B) `B.name[5] = 'a' ;`
(C\) `B[3].name = B[5].name ;`
(D) `Q.name[3] = '1' ;`
分析 :
這題就是考 struct 的基本用法而已，因為選項 B 是一個陣列
所以選項 (B) 應該表示成 `B[i].name[5] = 'a' ;` 才對
## 考前建議
有些題目感覺要花超過 $5$ 分鐘就可以放棄了，因為不值得，而且運氣好可能會過
刷一遍我整理的考古題，然後記住下面的數學公式
Sign in with Wallet
Connect another wallet