APCS 11011 筆試
===
[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';
```
問輸出
Sign in with Wallet
Connect another wallet