APCS 筆試題目分類

關於 APCS 筆試的題型細節

你可以在 APCS 官網：評量架構裡面找到下面這段關於考試筆試題型的介紹

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

根據最近幾次考試的實際經驗，我們可以整理成下面的分類

基本語法 / 流程控制
- 變數
  - scope: 全域變數 v.s. 區域變數
  - int 五則運算 (+ ,- ,* ,/ ,%)
  - 浮點數(float, double)運算
  - 布林(bool)運算
- 條件判斷
  - if, else if, else
  - switch
- 迴圈控制
  - while 迴圈
  - for 迴圈
- 一維陣列 / 多維陣列
- 字串處理
  - char 型別轉換
  - 迴文判斷
- 進階語法
  - 結構(struct)
  - 指標與陣列(pointer)
  - 巨集(macro)
- 函式
- 遞迴函式
數學
- 最大公因數(gcd)
- 等差級數、等比級數
- 帕斯卡三角形
- 費氏數列
- 質數篩法
- $a^{n}$
演算法概念
- $O (n^{2})$ 排序法
- 二分搜尋法
- 複雜度分析
資料結構概念
- stack
- queue
其它（計算機概論知識、不宜出在 apcs 的題目）

出題方式

填空題

題目：函式

下段程式碼為檢查一個 array 內的數字是否連續, 例如 {5, 3, 4, 2, 6} 完美覆蓋 2 ~ 6，而 {3, 5, 2, 6, 7} 缺 4
























const int MAXN = 1e5;
int f(int a[], int n) {
    int iMax = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > iMax)
            iMax = a[i];
    int iMin = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > iMin)
            iMin = a[i];
    
    int ok = 1;
    if (iMax - iMin == n) {
        int cnt[MAXN] = {};
        for (int i = 0; i < n; i++) {
            if (cnt[a[i]] == 1)
                __1__; 
            cnt[a[i]] = 1;
        }
        if (ok)
            __2__;
    }
    __3__;
}

(A)
ok = 0,
return 1,
return 0

(B)
return 1,
ok = 0,
return 0

(D)
return 1,
return 0,
ok = 0

Debug 題

題目：a 的 p 次方






int sum = 1;
while (p >= 0) {
  sum = sum * a;
  p = p - 1;
}
printf("%d\n", sum);

沒有正確輸出 a 的 p 次方，問哪裡錯

題目： if-else










char f(int x) {
  if (x <= 100 && x >= 90)
    return 'A';
  else if (x >= 80)
    return 'B';
  else if (x >= 70)
    return 'C';
  else 
    return 'D';
}

等地期望是

90 ~ 100: A
80 ~ 89: B
70 ~ 79: C
60 ~ 69: D
問上面程式哪裡寫錯

陷阱題

題目：巢狀 if 沒有配對問題










int main() {
    int x = 4;
    if (x >= 2)
        if (x < 6)
            a = 1;
        else
            a = 2;
    else
        a = 3;
}

問輸出

Tracing Code

題目： log16


for (int i = 0; i < 16; i++)
    i = i * 2

問 i = i * 2 執行幾次

基本語法 / 流程控制

變數

scope: 全域變數 v.s. 區域變數
int 五則運算 (+ ,- ,* ,/ ,%)
浮點數(float, double)運算
布林(bool)運算

題目： float / int 運算





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 哪些相同

題目：變數 scope









int a = 30;
void b() {
    int a = 20;
}
int main() {
    int a = 10;
    b();
    printf ("%d ", a);
}

詢問輸出結果

題目：變數 scope









void swap(int i, int j) {
    i = i + j;
    
}
int main(){
    int i = 10, j = 5;
    swap(i, j);
    printf("%d %d\n", i, j);
}

詢問輸出結果

題目：布林變數運算

如果 !x1 && !x2 && !x3 為 True 且 x1 為 False, 問 x2 和 x3 應該為多少

題目：變數型別








void func() {
    int b = 10, i;
    float a = 47;
    for (i = 0; i < 10; i++) {
        b = a / b;
        printf("%d", b);
    }
}

(a) i 偶數輸出 4
(b) i 奇數輸出 11

(A) 兩個都對
(B) 兩個都錯
(C) 只對 (a)
(D) 只對 (b)

條件判斷

if, else if, else
switch

題目：switch










int a = 2;
switch(a) {
    case 1+1:
        printf("A");
    case 1+2:
        printf("B");
        break;
    default:
        printf("??");
}

問輸出

題目：switch













int main(){
    char c = 'a';
    switch(c){
        case 'a':
            printf("a");
        case 'b':
            printf("b");
        case 'c':
            printf("c");
        default:
            printf("d");
    }
}

求輸出結果

題目：找到正確的判斷式




























int f(char s[], int n) {
    char t[1000];
    int j = 0;
    for (int i = 0; i < n; i++, j += 2) {
        if (s[i] == '0') {
            t[j] = 'w';
            t[j + 1] = 'a';
        } else if (??? || ???){
            t[j] = 't';
            t[j + 1] = 'e';
        } else if (s[i] == '3' || s[i] == '5') {
            t[j] = 'd';
            t[j + 1] = 'o';
        } else if (s[i] == '4' || s[i] == '6') {
            t[j] = 'p';
            t[j + 1] = 'u';
        } else {
            t[j] = ' ';
            j = j - 1;
        }
    }
    t[j] = '\0';
    printf("%s ", t);
}
int main() {
    char s[] = "0328675";
    f(s, 8);
}

已知輸出結果為 "wadote putedo"，求兩個 ??? 分別應該是什麼？

迴圈控制

while 迴圈
for 迴圈

題目：多層迴圈、星星

希望程式輸出入下，請填空程式碼

***1*****
**3******
*5*******
7********










int n = 4;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < 10; j++) {
        if (j < n - i - 1 || j > ____) {
            printf("*")
        } else {
            printf("%d", 2 * i + 1)
        }
    }
}

填空程式碼

題目：多層迴圈、星星





for (int i = 0; i < 8; i++) {
  for (int j = 0; ??; j++)
      printf("%d ", (i + j) % 2);
  printf("\n");
}

1
0 1
1 0 1
0 1 0 1
1 0 1 0 1
0 1 0 1 0 1
1 0 1 0 1 0 1

詢問 ?? 分別要填入啥
A. j <= i
B. j < i
C. j >= i
D. j > i

題目：判斷不可能的輸出









int func(int n) {
    if (n > 10)
        n = n + 5;
    while (n < 12)
        n = n + 1;
    if (n == 14)
        n = 5;
    return n;
}

詢問 func(n) 不可能會回傳什麼數值
(A) 15
(B) 16
(C) 17
(D) 18

題目：判斷不可能的輸出






int f(int n){
    if (n>17) n += 5;
    while (n>=23) n -= 6;
    if (n > 17) n += 2;
    return n;
}

一維陣列 / 多維陣列

題目：陣列基本觀念




int arr[] = {2, 5, 4};
int i = 1;
printf("%d\n", arr[i + 1]);
printf("%d\n", arr[i] + 1);

問輸出

題目：多維陣列初始化、內外層存取順序







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]);
    printf("\n");
}

詢問輸出結果

題目：矩陣翻轉














int a[3][3] = {};
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        if (i == j)
            a[i][j] = i + j;
        else
            a[i][j] = 0;
    }
}
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++)
        printf("%d ", a[j][i]);
    printf("\n");
}

詢問輸出結果

字串處理

char 型別轉換
迴文判斷

題目：ASCII 觀念



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[2] = 'd'
(B) a[4] = 'm'
(C) a[6] = 't'
(D) a[8] = 'x'

題目：字串傳入函式
















char z[10] = {};
void f(char *a, char *b) {
    for (int i = 0; i < 9; i++) {
        if (a[??] == b[??])
            z[i] = '0';
        else
            z[i] = '1';
    }
}
int main() {
    char x[] = "000111110";
    char y[] = "110001011";
    f(x, y);
    f(z, y);
    printf("%s\n", z);
}

問 ?? 填入哪些輸出是 "000111110"
A. i, i
B. i, 8 - i
C. 8 - i, i
D. 三個選項都對

題目：凱薩加密









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 應該是什麼？

進階語法

結構(struct)
指標與陣列(pointer)
巨集(macro)

題目：struct and array




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';

題目：pointer







void func(int *arr) {
	// ...
}
int main() {
    int arr[10] = {1};
    func(arr);
}

問傳進 func 的參數是什麼
A) 0
B) 1
C) 陣列的所有數字
D) 陣列的位址

題目：pointer





















int f(int *a, int *b);
int g(int *a, int *b);

int main(){
    int a = 2, b = 5;
    int x = f(&a, &b);
    printf("%d %d %d", x, a, b);
}
int f(int *a, int *b){
    int c = 10;
    *a = *a + *b / 5; 
    int p = g(b, a) % 2;
    if (p % 2 == 0){
        return *b - p;
    } else {
        return *b + p;
    }
}
int g(int *a, int *b){
    return (*a - *b) * 5 + 2;
}

求輸出結果

題目：macro 陷阱





#define add(a, b) a + b

int main() {
    printf("%d\n", add(3, 5) * add(3, 5));
}

問輸出結果

函式

題目：多層函式呼叫、scope
























int f(int a) {
    return -a;
}
int g(int a, int b) {
    return a + 2 * b; 
}
int h(int a, int b) {
    return (!a) * b;
}

int main() {
    int out_a = 1, out_b = 1;
    if (!f(g(h(out_b, out_a), out_a)))
        out_a = 1;
    else
        out_b = 1;

    if (out_b == 1)
        out_a = 3;
    else
        out_b = 3;
    printf("%d %d", out_a, out_b);
    return 0;
}

詢問輸出結果

遞迴函式

題目：遞迴算 1+2+3+ . . . +n






int sum(int n){
    if (???){
        return ???;
    }
    return n + sum(n-1);
}

(1) n<=1, n
(2) n<0, n+1
(3) n==0, 0
答案是三個都可以

題目：遞迴算 a 的 n 次方





int f(int x, int y) {
  if (x == y)
    return 1;
  return f(x, y - 1) * x;
}

問 f(2, 5) 回傳多少

題目：遞迴、2進制







void func(int n) {
    if (n > 0) {
        printf ("%d", n % 2);
        func(n / 2);
    }
}
func(21)

詢問回傳結果

題目：遞迴（先遞迴、後遞迴）







void func(int n) {
    printf("%d ", 2 * n);
    if (n < 4)
        func(n + 1);
    printf("%d ", 2 * n - 1);
}
func(2)

詢問輸出結果

題目：遞迴、數學








void f(int x, int y) {
    if (x == 0) return y;
    else return f(x - 1, x + y)
}

int main() {
    printf("%d\n", f(100, 10));
}

詢問輸出結果

題目：遞迴、數學




int f(int n){
    if (n>=101) return n - 10;
    return f(f(n + 11));
}

求出 f(5) 與 f(99)

題目：遞迴 trace code











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);

詢問輸出結果

題目：遞迴 trace code








int f(int n){
    if (n<2) retur n;
    if (n / 2 % 2 == 0){
        return -n * f(n-2);
    } else {
        return n * f(n-2);
    }
}

求 f(8)

題目：遞迴 trace code








int f(int n) {
    if (n == 0)
        return 0;
    printf("%d\n", n);
    int tmp = n % 10 + f(n / 10);
    printf("%d\n", tmp);
    return tmp;
}

問 f(123) 輸出結果

題目：遞迴、switch 條件控制












int k(int n) {
    switch(n) {
        case 0: return n;
        case 1: return n + k(n / 2);
        default: return n + k(n / 4);
    }
    return n;
}

int main() {
    printf("%d\n", k(30));
}

詢問輸出結果

題目：遞迴、判斷回文

判斷一個字串是不是回文







int isPal(char *s, int i, int len) {
    if (len == 0 || len == 1)
        return 1;
    if (s[i] != s[s + len - 1])
        return 0;
    return ???
}

問 ??? 要填入啥
A) isPal(s, i, len - 1)
B) isPal(s, i + 1, len - 1)
C) isPal(s, i + 1, len - 2)
D) isPal(s, i, len - 2)

數學

最大公因數(gcd)

題目：gcd 遞迴式






int f(int a, int b) {
    if (b == 0) {
        return a;
    }
    return ???
}

問 ??? 填什麼 f 才會回傳 a, b 的最大公因數？
A. f(a, b%a)
B. f(a%b, a)
C. f(b, a%b)
D. f(a%b, b)

題目：gcd / lcm 相關














int g(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}
int f(int a, int b) {
    return a * b / g(a, b);
}
int main() {
    printf("%d", f(10, 20));
}

詢問輸出結果

等差級數、等比級數

題目：數學、級數






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)

詢問輸出結果

題目：巢狀迴圈、數學











int f(int n){
    int a = 0;
    for (int i=0; i<n; i++){
        for (int j=1; j<=n; j = j*2){
            for (int k=i; k<n; k++){
                a++;
            }
        }
    }
    return a;
}

求 f(n) 的結果

帕斯卡三角形

題目：帕斯卡三角形相關









int pas[6] = {1};
for (int i = 0; i < 6; i++) {
    int prev = 0;
    for (int j = 0; __1__; j++) {
        tmp = pas[j];
        pas[j] = __2__ + tmp;
        prev = tmp;
    }
}

填空
(A) j < i - 1, pas[j]
(B) j < i + 1, pas[j - 1];
(C) j < i - 1, pas[j - 1];
(D) j < i + 1, pas[j]

題目：遞迴、帕斯卡三角形










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);

詢問輸出結果

費氏數列

題目：迴圈版費氏數列

迴圈版本費氏數列










int a = 1, b = 1;
int s = a + b;
int n = 8;
while (i < n) {
	a = b;
	b = s;
	s = a + b;
	i++;
}
printf("%d\n", s);

問輸出結果

質數篩法

題目：迴圈、質數篩法











int a[21] = {0};
for (int i=0; i<=20; i++){
    a[i] = 0;
}
for (int i=3; i<=20; i++){
    if (a[i] == 0){
        for (int j=i*i; j<=20; j+=i){
            a[j] = 1;
        }
    }
}

求 a 最後有幾項是 1

演算法概念

$O (n^{2})$ 排序法

題目：Bubble Sort 小變化

















int main(){
    int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = 9;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");   
}

詢問輸出結果

題目：Bubble Sort 小變化











int F(int seed) {
    int a[10] = {...};
    for (int i=0 ;i<9; i++){
        if (a[i+1] >= a[i] && a[i+1] <= seed){
            int temp = a[i+1];
            a[i+1] = a[i];
            a[i] = temp;
        }
    }
    printf("%d", a[seed-3]);
}

給定 seed = 7
求輸出結果

題目：Bubble Sort 小變化












int F() {
    int a[8] = {8, 7, 6, 5, 1, 2, 3, 4}
    for (int i=0; i<7; i++){
        for (int j=i; j<7; j++){
            if (a[i+1] >= a[i]){
                int temp = a[i+1];
                a[i+1] = a[i];
                a[i] = temp;
            }
        }
    }
}

求出最後 a 的內容

題目：Bubble Sort 交換次數問題






int n = 8;
int a[] = {???};
for (int i = 0; i < n; i++)
    for (int j = 0; j < n - 1; j++)
        if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);

給 4 個陣列問交換次數最多的是哪一個
A) {1, 2, 3, 4, 5, 6, 7, 8}
B) {8, 7, 6, 1, 2, 4, 3, 5}
C) {7, 3, 1, 6, 4, 2, 5, 8}
D) {6, 3, 8, 7, 4, 1, 2, 5}

題目：Bubble Sort 交換次數問題






int n = 5;
int a[] = {???};
for (int i = 0; i < n; i++)
    for (int j = 0; j < n - 1; j++)
        if (a[j] > a[j + 1])
            swap(a[j], a[j + 1]);

問一個陣列 {5, 3, 3, 2, 1} 交換幾次

題目：Selection Sort

由大到小排










void func(int a[], int n) {
    int t;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (___) {
                ___
            }
        }
    }
}

(A)
a[i] < a[j]

t = a[i];
a[i] = a[j];
a[j] = t;
(B)
a[i] > a[j]

t = a[i];
a[i] = a[j];
a[j] = t;
(C)
a[i] < a[j]

t = a[i];
a[j] = a[i];
a[i] = t;
(D)
a[i] > a[j]

t = a[i];
a[j] = a[i];
a[i] = t;

二分搜尋法

題目：二分搜尋法












void func(int x) {
    int a[] = {0, 2, 15, 20, 25, 30}, i = 0, j = 6;
    do {
        int m = (i + j) / 2;
        if (a[m] == x)
            break;
        if (a[m] < x)
            i = m;
        else
            j = m;
    } while (i + 1 < j);
}

問 func(3), func(15), func(4) int m = (i + j) / 2 執行了幾次

題目：二分搜尋法













int a[] = {2, 6, 10, 13, 66};
int bs(int l, int r, int key) {
    // 遞迴二分艘
    if (l == r) return a[l];
    int m = l + (r - l) / 2;
    if (a[m] < key)
        return bs(m + 1, r, key);
    else if (a[m] > key)
        return bs(l, m, key);
    else if (a[m] == key)
        return a[m];
    return -1;
}

問下咧哪個 function call 會出錯輸出結果
A) 1
B) 2
C) 10
D) 66

題目：二分搜尋法
















int binary_search(int *a, int s, int e, int key) {
    while (s < e) {
        int M = L + (R - L) / 2;
        if (a[M] < key)
            s = __1___
        else if (a[M] > key)
            e = __2___
        else
            e = __3___;
    }
    return ____;
}
int main() {
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    binary_search(a, 0, 9, 5);
}

最後的輸出是 5
問 mid + 1 應該要填入哪個 ____

複雜度分析

題目：複雜度

\sum_{i = 1}^{n} \frac{1}{i!}

兩種寫法哪種比較快
程式1








double f(int n) {
    double acc = 1, ret = 0;
    for (int i = 1; i <= n; i++) {
        acc = acc * i;
        ret += 1 / acc;
    }
    return ret;
}

程式2














double q(int n) {
    double ret = 1;
    for (int i = 1; i <= n; i++)
        ret = ret * i;
    return ret;
}

double g(int n) {
    double ret = 0;;
    for (int i = 1; i <= n; i++) {
        ret += q(i);
    }
    return ret;
}

哪一個跑比較快
A) f()
B) g()
C) 一樣快
D) n 很小的時候 g 比較快, 反之 f 比較快

題目：估計迴圈次數











void F(int n) {
    int ans = 0;
    for (int i = 1; i <= n; i = i * 2) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < j; k++) {
                ans++;
            }
        }
    }
    printf("%d\n", ans);
}

請問呼叫 F(100) 的輸出最接近下面哪個選項？
(A) 100000000
(B) 5000000
(C) 30000
(D) 10000

資料結構概念

stack
queue

題目：queue















int main() {
    int Q[5];
    int i, j, loc = 0;
    scanf("%d%d", &i, &j);
    if (i == 1) {
        for (int i = loc; i > 0; i--)
            Q[i] = Q[i - 1];
        Q[0] = j;
    } else if (i == 2) {
        Q[loc - 1] = 0;
        loc = loc - 1;
    }
    for (int i = 0; i < 5; i++)
        printf("%d ", Q[i]);
}

若輸入為 1 1 1 2 1 4 1 1 1 2 2 3 2 1，輸出為何
(A) 4 1 2 0 0

題目：random stack

已經給定一個 stack 的實做程式法，支援 empty, push(x), pop(), top()


















int level = 1;
for (int i=0; i<6; i++){
    if (empty()){
        push(level);
        level = level + 1;
    } else if (rand() % 2 == 0){ 
        printf("%d ", top());
        pop();
        level = level - 1;
    } else {
        push(level);
        level = level + 1;
    }
}
while (!empty()){
    printf("%d ", top());
    pop();
}

找出不可能的輸出結果

其它（計算機概論知識、不宜出在 apcs 的題目)

題目：考名詞














int isPal(char *s, int len) {
	Init(&X);
	for (int i = 0; i < len; i++)
		add(X, s[i]);
	
	int n = len;
	while (n > 1) {
		if (getFirst(X) != getLast(X)))
			return 0;
		n = n - 2;
	}
	Clear(&X);
	return 1;
}

有以下函數可以用

Init(&X): 初始化資料結構 X
Clear(&X): 清除資料結構 X
add(X, d): 將資料 d 放入 X 內
getFirst(X): 將 X 目前第一個資料 pop 出來
getLast(X): 將 X 目前最後一個資料 pop 出來

問 X 是什麼資料結構
A) 堆疊
B) 佇列
C) 雙向佇列
D) heap

題目：後序運算式 parser

給一個運算式 "3*5/6+2-1"，求它的後序運算式

CC 姓名標示─非商業性─相同方式分享

APCS 筆試題目分類

關於 APCS 筆試的題型細節

出題方式

填空題

Debug 題

陷阱題

Tracing Code

基本語法 / 流程控制

變數

條件判斷

迴圈控制

一維陣列 / 多維陣列

字串處理

進階語法

函式

遞迴函式

數學

最大公因數(gcd)

等差級數、等比級數

帕斯卡三角形

費氏數列

質數篩法

演算法概念

O(n2) 排序法

二分搜尋法

複雜度分析

資料結構概念

其它（計算機概論知識、不宜出在 apcs 的題目)

Read more

APCS 11106 筆試

apcs 11201

APCS 11110 (實作題)

APCS 11101 筆試

$O (n^{2})$ 排序法