APCS 11101 筆試 === ![](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) ## 筆試第一場 #### 1. 陣列、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"); }  詢問輸出結果 #### 2. 陣列 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]);  詢問輸出結果 #### 3. 加奇數 index cpp= 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 的倍數 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 #### 5. 選擇排序法(Selection Sort) :::success 您好請問這一題 是要問func(a, 4)嗎 填充答案是多少啊 謝謝您 ::: 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 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 但寫反 cpp= 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. 迴圈 cpp= 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 cpp= 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 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); }  詢問輸出結果 #### 10. Boolean 變數 如果 !x1 && !x2 && !x3 為 True 且 x1 為 False, 問 x2 和 x3 應該為多少 #### 11. gcd / lcm 相關 cpp= 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. 帕斯卡三角形相關 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] = __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. 遞迴 cpp= 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 條件控制 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; } int main() { printf("%d\n", k(30)); }  詢問輸出結果 #### 15. 數學、迴圈 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)  詢問輸出結果 #### 16. 多層函式呼叫、scope cpp= 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. 變數型別 cpp= 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. 可能回傳的數值 cpp= 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. 變數賦值 cpp= 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 cpp= 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進制 cpp= void func(int n) { if (n > 0) { printf ("%d", n % 2); func(n / 2); } } func(21)  詢問回傳結果 #### 2. 遞迴（先遞迴、後遞迴） cpp= void func(int n) { printf("%d ", 2 * n); if (n < 4) func(n + 1); printf("%d ", 2 * n - 1); } func(2)  詢問輸出結果 #### 3. 遞迴 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);  詢問輸出結果 #### 4. 遞迴、帕斯卡三角形 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);  詢問輸出結果 #### 5. 迴圈、星星  ***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) } } }  填空程式碼 #### 6. 數學 問 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 #### 7. 迴圈、矩陣翻轉 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"); }  詢問輸出結果 #### 8. 迴圈, 印三角形, 有空行 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);  詢問輸出結果 #### 9. 迴圈 要實作一個加總 $1 - \frac{1}{4} + \frac{1}{7} - \frac{1}{11} + ...$ 的程式, 空格應填入 cpp= 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 由大到小排 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; #### 11. Merge Sort 相關 填空 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] #### 12. 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); }  #### 13. 條件判斷 規則 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 #### 14. queue cpp= 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 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) #### 16. 字串相關 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' #### 17. 字串相關 問下列怎麼填可輸出 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) if (s[i] == c) s[i] = s[i] + 1; #### 18. 函式 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 :::info - 語法 / 流程控制 - if else - switch - 迴圈 - 變數 - 全域變數, 區域變數 - int 運算 - 陣列 - 字串 - 迴文判斷 - 進階語法 - 指標 - struct - macro - 函式、遞迴函式 - 數學 - gcd - 篩法 - 帕斯卡三角形 - 費氏數列 - $a^n$ - 算法 - 氣泡排序法 - 二分搜 - 複雜度 - top-down dp - 資料結構 - stack - queue :::