APCS 11101 筆試

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

筆試第一場

1. 陣列、row major

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

詢問輸出結果

2. 陣列

for (int i = 0; i < 100; i++)
    a[i] = 0, s[i] = 0;

s[0] = 1;
for (int i = 0; i < 100; i++) {
    int index = i / 50;
    s[i] = s[i] + s[a[index]];
}
printf("%d", s[50]);

詢問輸出結果

3. 加奇數 index

int sum = 0;
for (int i = 0; i < n; i++) {
    if (i % 2 == 0)
        sum = sum + (-arr[i]);
    sum = sum + arr[i];
}
printf("%d\n", sum);

詢問輸出結果

4. 4 的倍數

void func(int n, int m) {
    int arr[100];
    int tail = 0;
    for (int i = 1; i <= n; i++) {
        arr[tail] = i;
        tail = tail + 1;
    }
    int head = -1, count = 0;
    while (tail > head + 1) {
        count = count + 1;
        head = head + 1;
        if (count == m) {
            arr[tail] = arr[head];
            count = 0;
            tail = tail + 1;
        }
    }
    return arr[head];
}

func(30, 4)

詢問回傳結果
(A) 18
(B) 14
(C) 30
(D) 24

5. 選擇排序法(Selection Sort)

您好請問這一題 是要問func(a, 4)嗎 填充答案是多少啊 謝謝您

void func(int a[], int n) {
    int target = a[n], j;
    for (__1__; (a[j - 1] > target) && __2__; __3__) {
        a[j] = a[j - 1];
    }
    a[j] = target;
}

int main(){
    int a[5] = {16, 18, 19, 20, 17};
    func(a, 4);
    for (int i = 0; i <= 4; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

詢問輸出結果

6. 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");   
}

詢問輸出結果

7. 迴圈

int a[] = {0, 1, 5, 4, 5, 4, 5};
int n = 7, i, key = 5, F = 0;
for (i = 0; i < n; i++) {
    if (a[i] == key) {
        F = i;
        __?__;
    }
}

若 F 為 2，____ 要填啥

(A) break
(B) continue
(C) i++
(D) i–

8. Binary Search

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 call 了幾次

9. 變數 scope

int a = 30;
void b() {
    int a = 20;
}
int main() {
    int a = 10;
    b();
    for (int i = 0; i < 3; i++)
        printf ("%d ", a);
}

詢問輸出結果

10. Boolean 變數

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

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

詢問輸出結果

12. 帕斯卡三角形相關

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]

13. 遞迴

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

詢問輸出結果

14. 遞迴、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));
}

詢問輸出結果

15. 數學、迴圈

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)

詢問輸出結果

16. 多層函式呼叫、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;
}

詢問輸出結果

17. 變數型別

void func() {
    int b = 10, i;
    double 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)

18. 可能回傳的數值

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

19. 變數賦值

int a = 1, b = 2, c = 3;
a = b;
b = c;
c = a;

問 a, b, c 的值

20. 函式

下段程式碼為檢查一個 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

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

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

筆試第二場

1. 遞迴、2進制

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

詢問回傳結果

2. 遞迴（先遞迴、後遞迴）

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

詢問輸出結果

3. 遞迴

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

詢問輸出結果

4. 遞迴、帕斯卡三角形

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

詢問輸出結果

5. 迴圈、星星

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

填空程式碼

6. 數學

問 f(1000) 和 f(49999) 回傳是 6 和 10，___ 填多少

int f(int n) {
    int sum = 0;
    while (n) {
        n = n - n % 5;
        ______
        n = n / 5;
    }
    return sum;
}

(A) isZero = isZero - n / 5
(B) isZero = isZero + n / 5
(C) isZero = isZero + n / 6
(D) isZero = isZero + n % 6

7. 迴圈、矩陣翻轉

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

詢問輸出結果

8. 迴圈, 印三角形, 有空行

void func(int f) {
    while (f) {
        f = f - 1;
        int a = 4;
        for (int i = 1; i <= a; i++) {
            for (int j = 0; j < i; j++)
                printf("%d", i);
            printf("\n");
        }
        for (int i = a - 1; i >= 1; i--) {
            for (int j = 0; j < i; j++)
                printf("%d", i);
            printf("\n");
        }
        if (f) printf("\n");
    }
}

func(2);

詢問輸出結果

9. 迴圈

要實作一個加總

$1-\frac{1}{4}+\frac{1}{7}-\frac{1}{11}+...$ 的程式, 空格應填入

double x = 0, y = 1;
int i = 1, n = 10;
while (n--) {
    _______;
    y = -y;
    _______;
}

填空
(A) x = x + y / i, i = i + 3

10. 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;

11. Merge Sort 相關

填空

void func(int a[], int an, int b[], int bn) {
    int ai = 0, bi = 0, c[200], ci = 0;
    for (; (ai < an && bi < bn); ____) {
        if (____) {
            c[i] = a[ai];
            ai = ai + 1;
        } else {
            c[i] = b[bi];
            bi = bi + 1;
        }
    }
}

(A) ci = ci + 1, a[ai] <= b[bi]

12. scope

double a = 1.0;
const double b = 2.0;
int sw(double a, double b) {
    return a + b;
}
int main() {
    double b = 3.0;
    b = sw(a, b);
    a = a + 1.0;
    printf("%.2f %.2f", a, b);
}

13. 條件判斷

規則

1. 40 以下免稅
2. 40 ~ 100 稅率 0.1
3. 100 ~ 150 稅率 0.25
4. 超過部分 稅率 0.3

int f(int pay) {
    if (pay <= 40)
        return 0;
    if (pay <= 100)
        return (pay - 40) * 0.1
    if (pay <= 150)
        return pay * 0.2;
    return (pay - 150) * 0.3 + 12.5 + 6;
}

以上是錯的，要如何更改
(A) 第 4 和 6 行要變成 else if
(B) 第 7 行為 pay * 0.25 - 19
(C) 第 7 行為 (pay - 100) * 0.25 + 10
(D) 第 7 行為 (pay - 100) * 0.25 + 14

14. queue

int main() {
    int Q[5];
    int i, j, loc = 0;
    while(scanf("%d%d", &i, &j) == 2) {
        if (i == 1) {
            for (int i = loc; i > 0; i--) {
                Q[i] = Q[i - 1];
                Q[0] = j;
            }
            loc++;
        } 
        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) 2 1 4 0 0

15. boolean

void logic(int i, int j, int k) {
    int m[4] = {}, c = 0;
    m[c] = (i + k <= j);
    c = c + 1;
    // 不重要
}

logic(1, 5, 4);

(A)
(B)
(C) 1011
(D)

16. 字串相關

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'

17. 字串相關

問下列怎麼填可輸出 bababb

char s[] = {'a', 'b', 'a', 'b', 'a', 'a'};
void f(char x) {
    for (int i = 0; i < 7; i++) {
        ______
        else s[i] = x;
    }
}
int main() {
    f('a');
    for (int i = 0; i < 7; i++)
        printf("%c", s[i]);
}

(A) if (s[i] == c) s[i] = s[i] + 1;

18. 函式

int f1(int a, int b) {
    if (___)
        return b * 2;
    else
        return a * b;
}
int f2(int a, int b) {
    for (int i = 0; i < b; i++)
        a = a + i * 2;
    return a;
}

int main() {
    int a = 3, b = 2, c = 1;
    c = f1(a, b);
    a = f2(a, c);
    printf("%d %d", a, c)
}

若輸出為 10, 6 則空白應填入

(A) a + 2 < b

• 語法 / 流程控制
  • if else
  • switch
  • 迴圈
  • 變數
    • 全域變數, 區域變數
    • int 運算
  • 陣列
  • 字串
    • 迴文判斷
  • 進階語法
    • 指標
    • struct
    • macro
  • 函式、遞迴函式
• 數學
  • gcd
  • 篩法
  • 帕斯卡三角形
  • 費氏數列
  • $a^n$
• 算法
  • 氣泡排序法
  • 二分搜
  • 複雜度
  • top-down dp
• 資料結構
  • stack
  • queue