APCS 11101 筆試 === :::info ## 算法 ### 複雜度 ### 二分搜 ### top-down dp ### 數學 #### gcd #### 篩法 #### 帕斯卡三角形 #### 費氏數列 #### $a^n$ ### bubble sort ### 枚舉 ## 資料結構 ### stack ### queue ## if else / switch ## loop ## 變數 ### 作用域 ### int / int ## 字串 ### 回文 ## 陣列 ## 函式 ### 遞迴 ## 指標 ## struct ## macro ::: ## 筆試第一場 ### array #### row major ```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]); printf("\n"); } ``` #### 2222 ```cpp= 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]); ``` #### 加奇數 index ```cpp= int sum = 0; for (int i = 0; i < n; i++) { if (i % 2 == 0) sum = sum + (-arr[i]); sum = sum + arr[i]; } ``` #### 4 的倍數 ```cpp= 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 ### sort #### selection ```cpp= 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 a[5] = {16, 18, 19, 20, 17}; func(a, 4); ``` #### bubble 但寫反 ```cpp= 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]) { // swap j, j + 1 } } } ``` (??) {8, ?, ?, ..., ?, ?, 9} ### loop ```cpp= int a[] = {0, 1, 5, 4, 5, 4, 5}; int n = 7, i, key = 5; for (i = 0; i < n; i++) { if (a[i] == key) { F = i; __?__; } } ``` 若 F 為 2,____ 要填啥 (A) break ### bs ```cpp= void func(int x) { int a = {0, 2, 15, 20, 25, 30}; do { int x = (i + j) / 2; } while (i <= j) } ``` 問 func(3), func(15), func(4) `int x = (i + j) / 2` call 了幾次 ### scope ```cpp= int a = 30; void b() { int a = 20; } int main() { int a = 10; b(); for (int i = 0; i < 3; i++) printf ("%d ", a); } ``` (A) 10 10 10 ### bool 如果 `!x1 && !x2 && !x3` 為 True 且 x1 為 False, 問 x2 和 x3 應該為多少 ### math #### lcm ```cpp= int g(int a, int b) { // iterative 版 gcd } int f(int a, int b) { return a * b / g(a, b); } int main() { printf("%d", f(10, 20)); } ``` #### 帕斯卡 填空邊界 ```cpp= 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] = __?__ + tmp; prev = tmp; } } j < i - 1, pas[j] ``` ### 遞迴 #### 1 + ... + 100 ```cpp= void f(int x, int y) { if (x == 0) return y; else return f(x - 1, x + y) } f(100, 10); ``` #### 30 ```cpp= 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; } k(30); ``` ### function #### 三層迴圈問總和 ```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) 20 #### f(g(h())) ```cpp= int f(int a) { //... } int g(int a, int b) { //... } int h(int a, int b) { //... } 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); ``` #### 47 / 4, 47 / 11 ```cpp= void func(double a) { int b = 10, i; for (int i = 0; i < 10; i++) { b = a / b; printf("%d", b); } } ``` (a) i 偶數輸出 4 (b) i 奇數輸出 11 (A) 兩個都對 (B) 兩個都錯 \(C\) 只對 (a) (D) 只對 (b) ### 可能回傳的數值 ```cpp= void func(int n) { if (n > 10) n = n + 5; while (n < 12) n = n + 1; if (n == 14) n = 5; return ; } ``` ### 變數賦值 ```cpp= int a = 1, b = 2, c = 3; a = b; b = c; c = a; ``` 問 a, b, c 的值 ### function 檢查一個 array 內的數字是否連續, 例如 {5, 3, 4, 2, 6} 完美覆蓋 2 ~ 6,而 {3, 5, 2, 6, 7} 缺 4 ```cpp= 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]; if (iMax - iMin == n) { // 複雜的東西 int ok = 0; _____ } _____ } ``` (A) ok = 0, return 0 (B) return 0, ok = 0; \(C\) ok = 1, return 1 (D) return 1, ok = 1; ## 筆試第二場 ### 遞迴 #### 2進制 ```cpp= void func(int n) { if (n > 0) { printf ("%d", n % 2); func(n / 2); } } func(21) ``` (A) 10101 #### print recur print ```cpp= void func(int n) { printf("%d ", 2 * n); if (n < 4) func(n + 1); printf("%d ", 2 * n - 1); } func(2) ``` (A) 4 6 8 7 5 3 #### 遞迴 5 + ... + 50 + 5 ```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); ``` 問輸出 #### 5! ```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); ``` ### 迴圈 #### 星星 ``` ****1***** ***3****** **5******* *7******** ``` ```cpp= 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) } } } ``` (A) n - i - 1 #### / 太大 問 f(1000) 和 f(49999) 回傳是 6 和 10,___ 填多少 ```cpp= 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 #### 轉置矩陣 ```cpp= 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"); } ``` #### 印三角形, 有空行 ```cpp= 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); ``` (A) ``` 1 22 333 4444 333 22 1 1 22 333 4444 333 22 1 ``` #### 1 - 1/4 + 1/7 - ... ```cpp= double x = 0, y = 1; int i = 1, n = 10; while (n--) { _______; y = -y; _______; } ``` (A) x + y / i, i = i + 3 ### selection 由大到小排 ```cpp= 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; ### merge 填空 ```cpp= 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] ### scope ```cpp= 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); } ``` ### if 税 規則 1. 40 以下免稅 2. 40 ~ 100 稅率 0.1 3. 100 ~ 150 稅率 0.25 4. 超過部分 稅率 0.3 ```cpp= 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` ### queue ```cpp= 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 ### bool ```cpp= 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) ### 字串 #### 字元 ```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[2] = 'd' (B) a[4] = 'm' \(C\) a[6] = 't' (D) a[8] = 'x' #### 字元 問下列怎麼填可輸出 bababb ```cpp= 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) (B) if (s[i] == c) s[i] = s[i] + 1; \(C\) (D) ### function ```cpp= 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