APCS 11106 筆試

筆試第一場

if

grade

char result;
if (x >= 90) {
    result = 'A';
} else if (x >= 80) {
    result = 'B';
} else if (x >= 70) {
    result = 'C';
} else {
    result = 'D';
}

char result;
if (x >= 90)
    result = 'A';
switch(x) {
    case 90:
        result = 'A';
        break;
    case 80:
        result = 'B';
        break;
    case 70:
        result = 'C';
        break;
    case 60:
        result = 'D';
}

90 ~ 100 => 'A'
80 ~ 89 => 'B'
70 ~ 79 => 'C';
其他 => 'D';

(A) 程式 1 不一定會輸出正確解答
(B) 程式 2 不一定會輸出正確解答
(C) 程式 1 和程式 2 都不一定會輸出正確解答
(D) 程式 1 和程式 2 都會輸出正確解答

wrong*

void f(int x) {
    if (x > 0) {
        printf("positive*");
    }
    if (x < 0 && x >= -100) {
        printf("small negative*");
    } else if (x < -100) {
        printf("large negative*");
    } else {
        printf("wrong*");
    }
}

問 f(3) 的輸出
(A) positive*
(B) positive*wrong*
(C) large negative*
(D) wrong*

x <= z

問 x, y, z 要填哪些數值才能讓 以下 boolean expression 是 true

(!(x >= y || y >= z) || x <= z)

(A) x = 1, y = 0, z = 0
(B) x = 7, y = 3, z = 5
(C) x = 5, y = 7, z = 3
(D) x = 3, y = 5, z = 7

解題技巧

直接找 x <= z 的選項就是答案

for

迴圈執行次數

int j = 0;
for (int i = 0; i < 128; i = i + j + 1)
    j = i + 1;

問迴圈執行的次數

(A) 4
(B) 5
(C) 6
(D) 7

min - max

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

問下列四輸入哪一個會使得 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

counting

int main() {
    int a[10] = {3, 2, 3, 4, 5, 4, 7, 1, 3, 2};
    int b[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    for (int i = 0; i < 10; i++)
        b[a[i] - 1]++;
    printf("%d", b[5]);
}

求程式執行的輸出結果
(A) 0
(B) 1
(C) 2
(D) 3

哪一行一定不會被執行到

void f(int a) {
    if (a < 8)
        a = a - 2;
    if (a > 11)
        a = a + 3;
    while (a < 12)
        a = a + 2;
    if (a < 10)
        a = a * 5;
}

哪一行一定不會被執行到？
(A) a = a - 2;
(B) a = a + 3;
(C) a = a + 2;
(D) a = a * 5;

字串

回文

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 5 改成 p = 1

scope

pass by value 1

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 和 b 要填多少才會輸出 10 5

(A) 5, 5
(B) 10, 5
(C) 5, 10
(D) 10, 10

解題技巧

f 不會改變 main 裡面的 a, b
因此可以知道一開始的 a, b 和輸出的 10 5 是一樣的

pass by value 2 + int / int

void f(int x, int y) {
    int tmp = x;
    x = y;
    y = tmp;
}
int main() {
    int x = 3, y = 4;
    f(x, y);
    int v = (x - y) * (x + y) / 2;
    printf("%d\n", v);
}

求程式執行的輸出結果

(A) -4
(B) -3
(C) 3
(D) 4

解題技巧

f 不會改變 main 裡面的 x, y
因此 v = (3 - 4) * (3 + 4) / 2;

pass by value 3

int x = 1;
int f() {
    x = x + 3;
    printf("%d ", x);
}
int main() {
    int x = 5;
    f();
    f();
    printf("%d ", x);
}

問最後一個輸出的數字是什麼
(A) 5
(B) 8
(C) 4
(D) 7

函式與遞迴

多個 function trace code

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

前後置 recursion

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

後置 recursion

int f(int i) {
    if (i < 8) {
        i = i + 2;
        f(i);
        printf("%d\n", i);
    }
}

int main() {
    f(4);
}

求程式執行的輸出結果

(A) 8 6
(B) 6 8
(C) 4 6 8
(D) 8 6 4

數學

base10->base2

6 從 10 進制轉換成 2 進制

int x = 6, result = 0, index = 1;
int base2 = 2, base10 = 10;
while (x > 0) {
    int reminder = x % base2;
    result = ____ + reminder * index;
    index = index * _____;
    x = x / base2;
}

(A) result, base10;
(B) base2, base10;
(C) base10, result
(D) base2, base10

f91

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

找出以下正確的選項

(A) f(4) = 91, f(89) = 91
(B) f(94) = 94, f(101) = 91
(C) f(4) = 101, f(89) = 89
(D) f(91) = 91, f(35) = 35

排序觀念

cmp function

int h(int x) {
    return x;
}

int f(int x, int y) {
    return h(y) - h(x);
}
int main() {
    int n = 10;
    int a[] = {6, 3, 1, 5, 8, 4, 0, 7, 2, 9};
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (f(a[j], a[j + 1]) > 0) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = a[j];
            }
}

問 a 的結果
(A) {6, 3, 1, 5, 8, 4, 0, 7, 2, 9}
(B) {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}
(C) {8, 7, 6, 5, 4, 3, 2, 1, 0, 9}
(D) {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}

資料結構概念

2 stack 的 queue

f = push, g = pop;

int iSA[10];
int iSB[10];
int iA = 0, iB = 0;
void f(int i) {
    iSA[iA] = i;
    iA = iA + 1;
}
void g() {
    if (iB == 0) {
        while (iA > 0) {
            iA = iA - 1;
            iSB[iB] = iSA[iA];
            iB = iB + 1;
        }
    }
    iB = iB - 1;
    printf("%d", iSB[iB]);
}

依序執行 f(2), f(3), g(), f(1), g()，問輸出結果
(A) 2 3
(B) 3 2
(C) 2 3 1
(D) 2 1

筆試第二場

數學

可樂

每五瓶可以換一個可樂，下面是一個回傳最少要買幾瓶可樂才可以喝到至少 n 罐的的程式碼，除錯

  int func(int n) {
    for (int i = 1;; i++) {
        int total = i;    // 總共有幾罐
        int current = i;  // 目前手上有幾罐
        while (total < n) {
            total = total + current % 5;
            current = current - current / 5 + current / 5;
        }
        if (total >= n) return i;
    }
}

(A) 第 4 行錯
(B) 第 5 行錯
(C) 第 6 行錯
(D) 沒有錯

fib

int f(int n) {
    if (n <= 2)
        return 1;
    return f(n - 1) + f(n - 2);
}

問 f(6) 為多少

(A) 3
(B) 5
(C) 8
(D) 13

n!/2

已知 f(4) = 12, f(5) = 60, 下列框框要填多少

int f(int n) {
    if (____)
        return n * f(n - 1);
    return 1;
}

(A) n > 2
(B) n >= 2
(C) n == 0
(D) n == 1

!(A or B) = !A and !B

#define NUM 13
int i = 0, sum = 0;
while (i < NUM) {
    i = i + 1;
    if (i % 6 == 0)
        continue;
    sum = sum + i;
}
printf("%d\n", sum);

#define NUM 13
int i = 0, sum = 0;
do {
    i = i + 1;
    if (!(i == 2 || i == 3))
        continue;
    sum = sum + i;
} while (i < NUM);
printf("%d\n", sum);

#define NUM 13
int i = 0, sum = 0;
while (i < NUM) {
    i = i + 1;
    if (!(i == 2) && !(i == 3))
        continue;
    sum = sum + i;
}
printf("%d\n", sum);

問下列四個選項哪一個正確

(A) 程式碼1 和程式碼2 輸出一樣
(B) 程式碼1 和程式碼3 輸出一樣
(C) 程式碼2 和程式碼 3 輸出一樣
(D) 三個程式碼輸出都不一樣

function

pass by pointer

int f(int *x, int *y) {
    return (*y) * 3 - (*x) * 2; // 忘記了但不重要
}
int g() {
    // 沒用到, 忘記了不重要
}
int h(int n) {
    int a = n;
    int b = a % 2;
    f(&a, &b);
    printf("%d %d\n", a, b);
}

問 h(20) 輸出

(A) 20 0
(B) 18 2
(C) 2 18
(D) 15 2

10 ~ 50 的 % 3 == 0有幾個

int f(int n) {
    int count = 0;
    for (int i = 10; i < n; i += 3)
        count = count + 1;
    return count;
}

問 f(50) 的回傳值

(A) 13
(B) 14
(C) 15
(D) 16

1 * 2 + 2 * 3 + ..

想要計算 1 * 2 + 2 * 3 + 3 * 4 + … + 9 * 10, 但下列程式碼有錯, 除錯

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

int main() {
    sum(10);
}

(A) 第 2 行要改成 return 0;
(B) 第 3 行要改成 return (n - 1) * n + sum(n - 1);
(C) 第 1 行要改成 if (n == 2)
(D) 程式碼沒有錯

迴圈、流程控制

奇偶數

int a = 0, b = 0;
int arr[] = {...};
for (int i = 0; i < 10; i++) {
    if (____) {
        a = a + arr[i];
    } else {
        b = b + arr[i];
    }
}

想要讓 a = a[0] + a[2] + a[4] + a[6] + a[8], b = a[1] + a[3] + a[5] + a[7] + a[9], 框框內要填什麼

(A) i % 2 == 0
(B) i % 2 != 0
(C) arr[i] % 2 == 0
(D) arr[i] % 2 != 0

column major

int arr[3][3] = {{1, 2, 3}, {5, 4, 3}, {7, 8, 9}};
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        arr[j][i] = arr[j][i] + 1;
        arr[j][i] = arr[j][i] + 1;
        arr[i][j] = arr[j][i];
    }
}

給四個選項選出正確的
(A) arr[0][1] = arr[1][0] = 2
(B) arr[2][2] = 9
(C) arr[1][2] = arr[2][1] = 12
(D) arr[1][2] = arr[3][2] = 6

second

下列程式碼想要輸出陣列次大的數字, 哪個輸入可能會錯

int a, b;
int p[] = {____};
a = b = p[0]; 
for (int i = 0; i < 10; i++) {
    if (p[i] > a) {
        b = a;
        a = p[i];
    } else if (p[i] > b) {
        b = p[i];
    }
}
printf("%d\n", b);

解題技巧

最大值在第一個的時候

(A) {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
(B) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
(C) {5, 4, 7, 6, 1, 3, 2, 9, 0, 8}
(D) {0, 8, 7, 6, 5, 4, 3, 2, 1, 9}

各個位數和

void f(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    if (sum % 2 && sum % 3) {
        printf("X");
    } else if (sum % 3 == 0) {
        printf("Y");
    } else {
        printf("Z");
    }
}
int main() {
    f(54321);
    f(112233);
}

求程式執行的輸出結果

(A) 'Y' 和 'Y'
(B) 'Y' 和 'X'
(C) 'Z' 和 'Y'
(D) 'Z' 和 'X'

matrix 壓扁

#define ROW 3
#define COL 2
int m[ROW][COL] = {{7, 1}, {4, 1}, {6, 3}};
const int MAXN = 10;
struct A {
    int x, y, v;
} a[MAXN];;

int main() {
    int num = 0;
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (m[i][j] != 1) {
                num++;
                a[num].x = i;
                a[num].y = j;
                a[num].v = m[i][j];
            }
        }
    }
    a[0].x = ROW;
    a[0].y = COL;
    a[0].v = num;
    for (int i = 0; i < num; i++) {
        printf("%d %d %d\n", a[i].x, a[i].y, a[i].v);
    }
}

求程式執行的輸出結果
(A)

3 2 4
0 0 7
1 0 4
2 0 6
2 1 3

(B)

3 2 0
2 0 6
2 1 3

(C)

3 2 4
0 0 7
1 0 4
2 1 3

(D)

3 2 4
0 0 7
2 1 3

s = s + i, i = i * 2

int main() {
    int s = 0;
    for (int i = 1; i * i <= 1024; i = i * 2)
        s = s + i;
    printf("%d %d\n", s, i);
}

求程式執行的輸出結果

(A) 65 64
(B) 40 68
(C) 13 59
(D) 51 68

字串

xor

int f(char s[], char k[], char out[]) {
    int i = 0;
    while (i < 8) {
        if (s[___] == k[___])
            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