APCS 110.01.09

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

觀念第一場

bubble sort like











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 like












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 的內容

recursion, dp, math




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

求出 f(5) 與 f(99)

recursion








int i = 5;
int main(){
    while (i){
        i = i - 1;
        main();
        printf("%d", i);
    }
}

求輸出結果

學生成績，填入 if 條件中的大小於，code 有用到 struct
```
typedef struct student_info{
    ...
} student_t;
```
找各科成績總和最高的
分數一樣先比數學
數學也一樣就輸出第一個找到的
兩個填空看出第一個就可以選出選項了

nested loop, time complexity











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) 的結果

for loop 篩法











int a[21];
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

費氏數列












int F(int n){
    int a = 1, b = 2;
    int i = 0;
    int p = 0;
    while (i<n){
        p = a + b;
        a = b;
        b = p
        i = i+1;
    }
    return p;
}

求出 F(9)

1+2+3+…+n 遞迴，多選題，上次考試出過






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

(a) n<=1, n
(b) n<0, n+1
(c) n==0, 0
答案是三個都可以

array index






int F(int n){
    int A[1000] = {};
    for (int i=1; i!=n; i+=2){
        A[i] = 1;
    }
}

1000
999
0
-1

問 n 等於哪個選項不會造成陣列索引值錯誤

array index






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

輸出是 2
輸出是 6
a[] 索引值錯誤
b[] 索引值錯誤

queue









int Q[100];
int front = 0, end = 0;
for (int i=1; i<=15; i++){
    Q[end] = i;
    end = end + 1;
}
while (front + 1 < end){
}
printf("%d", front);

求輸出結果

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

swap







void swap(int a, int b){
    printf("%d, %d", a, b);
    ???
    b = a - b;
    a = a - b;
    printf("%d, %d", a, b);
}

求 ??? 要填入什麼可以讓 a, b 數值交換

觀念第二場

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

求輸出結果

reverse array

void reverse(int a[], int n){
    for (int i=0; ???; i++){    
        int temp = a[i];
        a[i] = a[n-1-i];
        a[n-1-i] = temp;
    }
}

??? 應該填入什麼可以讓這個 function 成功把陣列的順序顛倒?

call by value, 不會改變數值










void f(int x, int y){
    int temp = x;
    x = y;
    y = temp;
}
int main(){
    int x = 32, y = 5;
    h(x, y);
    printf("%d", (x-y)*(x+y + 4);
}

求輸出結果

nested loop





for (int i = 1; i <= 5; i++) {
    for (int j = 0; ??? ; j += 3) {
        printf("[%d] ", i + j);
    }
}

已知輸出結果為 [1][2][3][4][7][5][8], 求 ??? 應該填入什麼？

nested loop




























int f(char s[], int n){
    char t[1000];
    int j = 0;
    for (int i=0; i<m; 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"，求兩個 ??? 分別應該是什麼？

string encode



char s1[10][10] = {'A'};
char s2[10][20] = {};

後序運算式 parser
給一個運算式 "3*5/6+2-1"，求它的後序運算式
魔方陣
對於 a[n][n] 是一個 n 階魔方陣
1 的位置在 [n-1][(n-1)/2]
若 i 的位置在 (x, y)，且右下方沒有東西，i+1 就放在右下方
否則 i+1 方在 i 的正上方一格
給定 i 的座標 (x, y)，已知右下方有東西，求 i+1 的座標

陣列中奇數個數









int f(){
    int a[5] = {9, 2, 4, 7, 2};
    int b[10] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1};
    int c = 0;
    for (int i=0; i<5; i++){
        c += b[a[i]];
    }
    return c;
}

求回傳值

recursion








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)

stack
有一個空的 stack 依序放入 5, 3, 10, 4, 20
求這個 stack pop 的順序

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

找出不可能的輸出結果

找不可能的 output






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

array index easy







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

求輸出結果

switch without break













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

求輸出結果

binary search


















int f(int a[], int s, int f) {
    int min = 0, max = s-1;
    while (min < max){
        int mid = (min + max) / 2;
        if (f > a[mid]){
            l = mid + 1;
        } else if (f < a[mid]){
            r = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
int main(){
    int a[8] = {2, 3, 3, 5, 8, 8, 8, 8};
    printf("%d", f(a, 8, 8));
}

求輸出結果