APCS 11011 筆試

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

筆試第一場

xor string
















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






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)

星星





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 沒有 {} 配對問題










int main() {
    int x = 4;
    if (x >= 2)
        if (x < 6)
            a = 1;
        else
            a = 2;
    else
        a = 3;
}

問輸出

i = i + j swap




void swap(int i, int j) {
    i = i + j;
    
}

switch










int a = 2;
switch(a) {
    case 1+1:
        cout << "A";
    case 1+2:
        cout << "B";
        break;
    default:
        cout << "??";
}

問輸出

bubble sort like 問 4 個陣列逆序數對大小關係






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











int i = 1;
void f() {
  i = 3;
  cout << i << '\n';
  i = 6;
}
int main() {
  cout << i << '\n';
  f();
  cout << i << '\n';
}

問輸出

while-loop








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

二分艘













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







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




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










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}$





int f(int x, int y) {
  if (x == y)
    return 1;
  return f(x, y - 1) * x;
}

問 f(2, 5) 回傳多少

$a^{p}$






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








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

判斷一個字串是不是回文







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)

遞迴








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





#define add(a, b) (a + b)

int main() {
  cout << add(3, 5) * add(3, 5) << '\n';
}

問輸出結果

複雜度

\sum_{i = 1}^{n} \frac{1}{i!}

兩種寫法哪種比較快

程式1








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














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















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';
}

問輸出

二分艘
















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 應該要填入哪個 ____

資料結構














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;
}

有以下函數可以用

Init(&X): 初始化資料結構 X
Clear(&X): 清除資料結構 X
add(X, d): 將資料 d 放入 X 內
getFirst(X): 將 X 目前第一個資料 pop 出來
getLast(X): 將 X 目前最後一個資料 pop 出來

問 X 是什麼資料結構
A) 堆疊
B) 佇列
C) 雙向佇列
D) heap

log16


for (int i = 0; i < 16; i++)
    i = i * 2

問 i = i * 2 執行幾次

loop fib

迴圈版本費氏數列










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';