APCS 11011 筆試 === ![](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) ## 筆試第一場 ### xor string cpp= char z[10] = {}; void f(char *a, char *b) { for (int i = 0; i < 9; i++) { if (a[??] == b[??]) z[i] = '0'; else z[i] = '1'; } } int main() { char x[] = "000111110"; char y[] = "110001011"; f(x, y); f(z, y); cout << z << '\n'; }  問 ?? 填入哪些輸出是 "000111110" A. i, i B. i, 8 - i C. 8 - i, i D. 三個選項都對 ### gcd cpp= int f(int a, int b) { if (b == 0) { return a; } return ??? }  問 ??? 填什麼 f 才會回傳 gcd(a, b) A. f(a, b%a) B. f(a%b, a) C. f(b, a%b) D. f(a%b, b) ### 星星 cpp= for (int i = 0; i < 8; i++) { for (int j = 0; ??; j++) cout << (i + j) % 2 << ' '; cout << '\n'; }   1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1  詢問 ?? 分別要填入啥 A. j <= i B. j < i C. j >= i D. j > i ### 巢狀 if 沒有 {} 配對問題 cpp= int main() { int x = 4; if (x >= 2) if (x < 6) a = 1; else a = 2; else a = 3; }  問輸出 ### i = i + j swap cpp= void swap(int i, int j) { i = i + j; }  ### switch cpp= int a = 2; switch(a) { case 1+1: cout << "A"; case 1+2: cout << "B"; break; default: cout << "??"; }  問輸出 ### bubble sort like 問 4 個陣列逆序數對大小關係 cpp= int n = 5; int a[] = {???}; for (int i = 0; i < n; i++) for (int j = 0; j < n - 1; j++) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);  ### scope cpp= int i = 1; void f() { i = 3; cout << i << '\n'; i = 6; } int main() { cout << i << '\n'; f(); cout << i << '\n'; }  問輸出 ### while-loop cpp= int func(x) { if (x > 12) x = x + 5; while (x < 14) x = x - 3; x = x - 3; return x; }  不可能回傳哪些數字 A) 6 B) 7 C) 13 D) 16 ### 二分艘 cpp= int a[] = {2, 6, 10, 13, 66}; int bs(int l, int r, int key) { // 遞迴二分艘 if (l == r) return a[l]; int m = l + (r - l) / 2; if (a[m] < key) return bs(m + 1, r, key); else if (a[m] > key) return bs(l, m, key); else if (a[m] == key) return a[m]; return -1; }  問下咧哪個 function call 會出錯輸出結果 A) 1 B) 2 C) 10 D) 66 ### 枚舉 substring cpp= char str[] = "sdklfj"; int n = 6; for (int i = 0; i < 6; i++) for (??) { int len = j - i; substr(str + i, len); }  ?? 要填入啥才可以枚舉出所有 substring ### struct 語法 問哪一些會 compile error cpp= struct A { int x, y; char name[20]; }P, Q, B[10];  A) P.x = Q.y; B) B.name[5] = 'a'; C) B[3].name = B[5].name D) Q.name[3] = '1'; ### if-else cpp= char f(int x) { if (x <= 100 && x >= 90) return 'A'; else if (x >= 80) return 'B'; else if (x >= 70) return 'C'; else return 'D'; }  等地期望是 - 90 ~ 100: A - 80 ~ 89: B - 70 ~ 79: C - 60 ~ 69: D 問上面程式哪裡寫錯 ## 筆試第二場 ### $a^n$ cpp= int f(int x, int y) { if (x == y) return 1; return f(x, y - 1) * x; }  問 f(2, 5) 回傳多少 ### $a^p$ cpp= int sum = 1; while (p >= 0) { sum = sum * a; p = p - 1; } cout << sum << '\n';  沒有正確輸出 $a^p$, 問哪裡錯 ### 遞迴 3n + 1 改 - 如果 n 是奇數, 變成 n / 2 - 如果 n 是偶數, 變成 3 * n + 1 - 問幾次會收斂到 1 cpp= int func(int n) { if (n == 1) return 0; if (n % 2) return ____; else return ____; }  A) f(n / 2), f(3 * n + 1) B) f(3 * n + 1), f(n / 2) C) f(n / 2) + 1, f(3 * n + 1) + 1 D) f(3 * n + 1) + 1, f(n / 2) + 1 ### 遞迴 isPal 判斷一個字串是不是回文 cpp= int isPal(char *s, int i, int len) { if (len == 0 || len == 1) return 1; if (s[i] != s[s + len - 1]) return 0; return ??? }  問 ??? 要填入啥 A) isPal(s, i, len - 1) B) isPal(s, i + 1, len - 1) C) isPal(s, i + 1, len - 2) D) isPal(s, i, len - 2) ### 遞迴 cpp= int f(int n) { if (n == 0) return 0; cout << n << '\n'; int tmp = n % 10 + f(n / 10); cout << tmp << '\n'; return tmp; }  問 f(123) 輸出結果 ### macro cpp= #define add(a, b) (a + b) int main() { cout << add(3, 5) * add(3, 5) << '\n'; }  問輸出結果 ### 複雜度 $\sum_{i = 1}^{n}{\frac{1}{i!}}$ 兩種寫法哪種比較快 #### 程式1 cpp= double f(int n) { double acc = 1, ret = 0; for (int i = 1; i <= n; i++) { acc = acc * i; ret += 1 / acc; } return ret; }  #### 程式2 cpp= double q(int n) { double ret = 1; for (int i = 1; i <= n; i++) ret = ret * i; return ret; } double g(int n) { double ret = 0;; for (int i = 1; i <= n; i++) { ret += q(i); } return ret; }  哪一個跑比較快 A) f() B) g() C) 一樣快 D) n 很小的時候 g 比較快, 反之 f 比較快 ### dp cpp= int c[100] = {}; int func(int n, int c[]) { if (n < 1) return 1; else if (c[n] > 0) return c[n]; c[n] = 2 * func(n - 1) + func(n - 2); return c[n] } int main() { for (int i = 0; i < 100; i++) c[i] = 0; cout << func(6, c) << '\n'; }  問輸出 ### 二分艘 cpp= int binary_search(int *a, int s, int e, int key) { while (s < e) { int M = L + (R - L) / 2; if (a[M] < key) s = __1___ else if (a[M] > key) e = __2___ else e = __3___; } return ____; } int main() { int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; binary_search(a, 0, 9, 5); }  問 mid + 1 應該要填入哪個 ____ ### 資料結構 cpp= int isPal(char *s, int len) { Init(&X); for (int i = 0; i < len; i++) add(X, s[i]); int n = len; while (n > 1) { if (getFirst(X) != getLast(X))) return 0; n = n - 2; } Clear(&X); return 1; }  有以下函數可以用 1. Init(&X): 初始化資料結構 X 2. Clear(&X): 清除資料結構 X 3. add(X, d): 將資料 d 放入 X 內 4. getFirst(X): 將 X 目前第一個資料 pop 出來 5. getLast(X): 將 X 目前最後一個資料 pop 出來 問 X 是什麼資料結構 A) 堆疊 B) 佇列 C) 雙向佇列 D) heap ### log16 cpp= for (int i = 0; i < 16; i++) i = i * 2  問 i = i * 2 執行幾次 ### loop fib 迴圈版本費氏數列 cpp= int a = 1, b = 1; int s = a + b; int n = 8; while (i < n) { a = b; b = s; s = a + b; i++; } cout << s << '\n';  問輸出結果 ### pointer cpp= void func(int *arr) { // ... } int main() { int arr[10] = {1}; func(arr); }  問 傳進 func 的參數是什麼 A) 0 B) 1 C) 陣列的所有數字 D) 陣列的位址 ### bubble sort like 1 cpp= int n = 8; int a[] = {???}; for (int i = 0; i < n; i++) for (int j = 0; j < n - 1; j++) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);  給 4 個陣列問交換次數最多的是哪一個 A) {1, 2, 3, 4, 5, 6, 7, 8} B) {8, 7, 6, 1, 2, 4, 3, 5} C) {7, 3, 1, 6, 4, 2, 5, 8} D) {6, 3, 8, 7, 4, 1, 2, 5} ### bubble sort like 2 cpp= int n = 5; int a[] = {???}; for (int i = 0; i < n; i++) for (int j = 0; j < n - 1; j++) if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);  問一個陣列 {5, 3, 3, 2, 1} 交換幾次 ### 輸出 cpp= for (int i = 0; i < 5; i++) for (int j = 0; ??; j += 2) cout << "[" << i + j << "]";  若輸出是 [0][1][2][4][3][5][4][6][8], 則 ?? 要填入啥 A) j < i B) j <= i C) j > i D) j >= i ### 0-based array cpp= int arr[] = {2, 5, 4}; int i = 1; cout << arr[i + 1] << '\n'; cout << arr[i] + 1 << '\n';  問輸出