# APCS 11106 筆試 :::info 以下題目是人工從考場背出來的,題目敘述會盡可能與原題相似,但無法保證完全一致。關於題目或選項有任何建議歡迎使用 HackMD 的留言功能於下方留言。 ::: ![](http://mirrors.creativecommons.org/presskit/buttons/88x31/png/by-nc-sa.png =100x) [CC 姓名標示─非商業性─相同方式分享](https://creativecommons.org/licenses/by-nc-sa/3.0/tw/legalcode) ## 筆試第一場 ### if #### grade ```cpp= char result; if (x >= 90) { result = 'A'; } else if (x >= 80) { result = 'B'; } else if (x >= 70) { result = 'C'; } else { result = 'D'; } ``` ```cpp= 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 不一定會輸出正確解答 <span class="ans"> (B) 程式 2 不一定會輸出正確解答 </span> \(C\) 程式 1 和程式 2 都不一定會輸出正確解答 (D) 程式 1 和程式 2 都會輸出正確解答 #### wrong* ```cpp= 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*` <span class="ans"> (B) `positive*wrong*` </span> \(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 <span class="ans"> (D) x = 3, y = 5, z = 7 </span> :::spoiler 解題技巧 直接找 x <= z 的選項就是答案 ::: ### for #### 迴圈執行次數 ```cpp= int j = 0; for (int i = 0; i < 128; i = i + j + 1) j = i + 1; ``` 問迴圈執行的次數 (A) 4 (B) 5 (C\) 6 <span class="ans"> (D) 7 </span> #### min - max ```cpp= 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 不一樣 <span class="ans"> (A) 5, 4, 3, 2, 1 </span> (B) 1, 2, 3, 4 ,5 (C\) 4, 1, 5, 3, 2 (D) 2, 3, 1, 4, 5 #### counting ```cpp= 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]); } ``` 求程式執行的輸出結果 <span class="ans"> (A) 0 </span> (B) 1 (C\) 2 (D) 3 #### 哪一行一定不會被執行到 ```cpp= 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; <span class="ans"> (D) a = a * 5; </span> ### 字串 #### 回文 ```cpp=0 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 才會正常運作 <span class="ans"> (A) line 3 改 for (int i = 0; i < len / 2; i++) { </span> (B) line 3 改 for (int i = 0; i < len / 2 + 1; i++) { (C\) 程式沒有任何錯誤 (D) line 5 改成 p = 1 ### scope #### pass by value 1 ```cpp= 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 <span class="ans"> (B) 10, 5 </span> (C\) 5, 10 (D) 10, 10 :::spoiler 解題技巧 f 不會改變 main 裡面的 a, b 因此可以知道一開始的 a, b 和輸出的 10 5 是一樣的 ::: #### pass by value 2 + int / int ```cpp= 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 <span class="ans"> (B) -3 </span> (C\) 3 (D) 4 :::spoiler 解題技巧 f 不會改變 main 裡面的 x, y 因此 v = (3 - 4) * (3 + 4) / 2; ::: #### pass by value 3 ```cpp= int x = 1; int f() { x = x + 3; printf("%d ", x); } int main() { int x = 5; f(); f(); printf("%d ", x); } ``` 問最後一個輸出的數字是什麼 <span class="ans"> (A) 5 </span> (B) 8 (C\) 4 (D) 7 ### 函式與遞迴 #### 多個 function trace code ```cpp= 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 <span class="ans"> (C\) 3 </span> (D) 4 #### 前後置 recursion ```cpp= 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 <span class="ans"> (D) 9 6 3 2 5 8 </span> #### 後置 recursion ```cpp= int f(int i) { if (i < 8) { i = i + 2; f(i); printf("%d\n", i); } } int main() { f(4); } ``` 求程式執行的輸出結果 <span class="ans">(A) 8 6</span> (B) 6 8 (C\) 4 6 8 (D) 8 6 4 ### 數學 #### base10->base2 6 從 10 進制轉換成 2 進制 ```cpp= 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; } ``` <span class="ans"> (A) result, base10; </span> (B) base2, base10; (C\) base10, result (D) base2, base10 #### f91 ```cpp= int f(int x) { if (x >= 101) return x - 10; return f(f(x + 11)); } ``` 找出以下正確的選項 <span class="ans"> (A) f(4) = 91, f(89) = 91 </span> (B) f(94) = 94, f(101) = 91 (C\) f(4) = 101, f(89) = 89 (D) f(91) = 91, f(35) = 35 ### 排序觀念 #### cmp function ```cpp= 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 :::info f = push, g = pop; ::: ```cpp= 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(),問輸出結果 <span class="ans"> (A) 2 3 </span> (B) 3 2 (C\) 2 3 1 (D) 2 1 ## 筆試第二場 ### 數學 #### 可樂 每五瓶可以換一個可樂,下面是一個回傳最少要買幾瓶可樂才可以喝到至少 n 罐的的程式碼,除錯 ```cpp=0 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 行錯 <span class="ans"> (B) 第 5 行錯 </span> (C\) 第 6 行錯 (D) 沒有錯 #### fib ```cpp= int f(int n) { if (n <= 2) return 1; return f(n - 1) + f(n - 2); } ``` 問 f(6) 為多少 (A) 3 (B) 5 <span class="ans"> (C\) 8 </span> (D) 13 #### n!/2 已知 f(4) = 12, f(5) = 60, 下列框框要填多少 ```cpp= int f(int n) { if (____) return n * f(n - 1); return 1; } ``` <span class="ans"> (A) n > 2 </span> (B) n >= 2 (C\) n == 0 (D) n == 1 #### !(A or B) = !A and !B ```cpp= #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); ``` ```cpp= #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); ``` ```cpp= #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 輸出一樣 <span class="ans"> (C\) 程式碼2 和程式碼 3 輸出一樣 </span> (D) 三個程式碼輸出都不一樣 ### function #### pass by pointer ```cpp= 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) 輸出 <span class="ans"> (A) 20 0 </span> (B) 18 2 (C\) 2 18 (D) 15 2 #### 10 ~ 50 的 % 3 == 0有幾個 ```cpp= int f(int n) { int count = 0; for (int i = 10; i < n; i += 3) count = count + 1; return count; } ``` 問 f(50) 的回傳值 (A) 13 <span class="ans"> (B) 14 </span> (C\) 15 (D) 16 #### 1 * 2 + 2 * 3 + .. 想要計算 1 * 2 + 2 * 3 + 3 * 4 + ... + 9 * 10, 但下列程式碼有錯, 除錯 ```cpp=0 int sum(int n) { if (n == 1) return 1; return n * (n - 1) + sum(n - 1); } int main() { sum(10); } ``` <span class="ans"> (A) 第 2 行要改成 return 0; </span> (B) 第 3 行要改成 return (n - 1) * n + sum(n - 1); (C\) 第 1 行要改成 if (n == 2) (D) 程式碼沒有錯 ### 迴圈、流程控制 #### 奇偶數 ```cpp= 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], 框框內要填什麼 <span class="ans"> (A) i % 2 == 0 </span> (B) i % 2 != 0 (C\) arr[i] % 2 == 0 (D) arr[i] % 2 != 0 #### column major ```cpp= 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 <span class="ans"> (C\) arr[1][2] = arr[2][1] = 11 </span> (D) arr[1][2] = arr[3][2] = 6 #### second 下列程式碼想要輸出陣列次大的數字, 哪個輸入可能會錯 ```cpp= 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); ``` :::spoiler 解題技巧 最大值在第一個的時候 ::: <span class="ans"> (A) {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} </span> (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} #### 各個位數和 ```cpp= 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); } ``` 求程式執行的輸出結果 <span class="ans"> (A) 'Y' 和 'Y' </span> (B) 'Y' 和 'X' (C\) 'Z' 和 'Y' (D) 'Z' 和 'X' #### matrix 壓扁 ```cpp= #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); } } ``` 求程式執行的輸出結果 <span class="ans">(A)</span> ``` 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 ```cpp= int main() { int s = 0; for (int i = 1; i * i <= 1024; i = i * 2) s = s + i; printf("%d %d\n", s, i); } ``` 求程式執行的輸出結果 <span class="ans"> (A) 65 64 </span> (B) 40 68 (C\) 13 59 (D) 51 68 ### 字串 #### xor ```cpp= 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 <span class="ans"> (C\) i + 1, i</span> (D) i, i + 1 :::info ## 分類主題 - 基本語法 / 流程控制 - 變數 - 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 的題目) ::: <style> .ans{ color: blue; font-weight: bold; } </style>