APCS 11101 筆試
===
[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
:::
Sign in with Wallet
Connect another wallet