# APCS 筆試題目分類
<style>
h1{
color: #52D3EA
}
h2{
color: #52D3EA
}
</style>
## 關於 APCS 筆試的題型細節
你可以在 [APCS 官網:評量架構](https://apcs.csie.ntnu.edu.tw/index.php/questionstypes/) 裡面找到下面這段關於考試筆試題型的介紹
![](https://i.imgur.com/yDCsc0u.png)
根據最近幾次考試的實際經驗,我們可以整理成下面的分類
- 基本語法 / 流程控制
- 變數
- scope: 全域變數 v.s. 區域變數
- int 五則運算 (+ ,- ,* ,/ ,%)
- 浮點數(float, double)運算
- 布林(bool)運算
- 條件判斷
- if, else if, else
- switch
- 迴圈控制
- while 迴圈
- for 迴圈
- 一維陣列 / 多維陣列
- 字串處理
- char 型別轉換
- 迴文判斷
- 進階語法
- 結構(struct)
- 指標與陣列(pointer)
- 巨集(macro)
- 函式
- 遞迴函式
- 數學
- 最大公因數(gcd)
- 等差級數、等比級數
- 帕斯卡三角形
- 費氏數列
- 質數篩法
- $a^n$
- 演算法概念
- $O(n^2)$ 排序法
- 二分搜尋法
- 複雜度分析
- 資料結構概念
- stack
- queue
- 其它(計算機概論知識、不宜出在 apcs 的題目)
## 出題方式
### 填空題
:::spoiler 題目:函式
下段程式碼為檢查一個 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
:::
### Debug 題
:::spoiler 題目:a 的 p 次方
```cpp=
int sum = 1;
while (p >= 0) {
sum = sum * a;
p = p - 1;
}
printf("%d\n", sum);
```
沒有正確輸出 a 的 p 次方,問哪裡錯
:::
:::spoiler 題目: 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
問上面程式哪裡寫錯
:::
### 陷阱題
:::spoiler 題目: 巢狀 if 沒有 {} 配對問題
```cpp=
int main() {
int x = 4;
if (x >= 2)
if (x < 6)
a = 1;
else
a = 2;
else
a = 3;
}
```
問輸出
:::
### Tracing Code
:::spoiler 題目: log16
```cpp=
for (int i = 0; i < 16; i++)
i = i * 2
```
問 i = i * 2 執行幾次
:::
## 基本語法 / 流程控制
### 變數
- scope: 全域變數 v.s. 區域變數
- int 五則運算 (+ ,- ,* ,/ ,%)
- 浮點數(float, double)運算
- 布林(bool)運算
:::spoiler 題目: float / int 運算
```c=
int a = 7, b = 3;
float w = a / 2 / b * 1.0;
float x = a / b / 2.0;
float y = a / 2 / b;
float z = 1.0 * a / 2 / b;
```
問 w, x, y, z 哪些相同
:::
:::spoiler 題目:變數 scope
```cpp=
int a = 30;
void b() {
int a = 20;
}
int main() {
int a = 10;
b();
printf ("%d ", a);
}
```
詢問輸出結果
:::
:::spoiler 題目:變數 scope
```cpp=
void swap(int i, int j) {
i = i + j;
}
int main(){
int i = 10, j = 5;
swap(i, j);
printf("%d %d\n", i, j);
}
```
詢問輸出結果
:::
:::spoiler 題目:布林變數運算
如果 `!x1 && !x2 && !x3` 為 True 且 x1 為 False, 問 x2 和 x3 應該為多少
:::
:::spoiler 題目:變數型別
```cpp=
void func() {
int b = 10, i;
float 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)
:::
### 條件判斷
- if, else if, else
- switch
:::spoiler 題目:switch
```cpp=
int a = 2;
switch(a) {
case 1+1:
printf("A");
case 1+2:
printf("B");
break;
default:
printf("??");
}
```
問輸出
:::
:::spoiler 題目:switch
```c=
int main(){
char c = 'a';
switch(c){
case 'a':
printf("a");
case 'b':
printf("b");
case 'c':
printf("c");
default:
printf("d");
}
}
```
求輸出結果
:::
:::spoiler 題目:找到正確的判斷式
```c=
int f(char s[], int n){
char t[1000];
int j = 0;
for (int i=0; i<m; i++, j+=2){
if (s[i] == '0'){
t[j] = 'w';
t[j+1] = 'a';
} else if (??? || ???){
t[j] = 't';
t[j+1] = 'e';
} else if (s[i] == '3' || s[i] == '5'){
t[j] = 'd';
t[j+1] = 'o';
} else if (s[i] == '4' || s[i] == '6'){
t[j] = 'p';
t[j+1] = 'u';
} else {
t[j] = ' ';
j = j-1;
}
}
t[j] = '\0';
printf("%s ", t);
}
int main(){
char s[] = "0328675";
f(s, 8);
}
```
已知輸出結果為 "wadote putedo",求兩個 ??? 分別應該是什麼?
:::
### 迴圈控制
- while 迴圈
- for 迴圈
:::spoiler 題目:多層迴圈、星星
希望程式輸出入下,請填空程式碼
```
***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)
}
}
}
```
填空程式碼
:::
:::spoiler 題目:多層迴圈、星星
```cpp=
for (int i = 0; i < 8; i++) {
for (int j = 0; ??; j++)
printf("%d ", (i + j) % 2);
printf("\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`
:::
:::spoiler 題目:判斷不可能的輸出
```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
:::
:::spoiler 題目:判斷不可能的輸出
```c=
int f(int n){
if (n>17) n += 5;
while (n>=23) n -= 6;
if (n > 17) n += 2;
return n;
}
```
:::
### 一維陣列 / 多維陣列
:::spoiler 題目:陣列基本觀念
```cpp=
int arr[] = {2, 5, 4};
int i = 1;
printf("%d\n", arr[i + 1]);
printf("%d\n", arr[i] + 1);
```
問輸出
:::
:::spoiler 題目:多維陣列初始化、內外層存取順序
```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");
}
```
詢問輸出結果
:::
:::spoiler 題目:矩陣翻轉
```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");
}
```
詢問輸出結果
:::
### 字串處理
- char 型別轉換
- 迴文判斷
:::spoiler 題目:ASCII 觀念
```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'
:::
:::spoiler 題目:字串傳入函式
```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);
printf("%s\n", z);
}
```
問 ?? 填入哪些輸出是 "000111110"
A. i, i
B. i, 8 - i
C. 8 - i, i
D. 三個選項都對
:::
:::spoiler 題目:凱薩加密
```cpp=
void func(char *s) {
char mp[] = "IEFGHDJKLMNOPCRSTUVWXYZABQ";
int len = strlen(s);
for (int i = 0; i < len; i++) {
int c = s[i] - 'A';
printf("%c", mp[c]);
}
}
```
已知輸出結果為 `FIHVIU` ,請問 `s` 應該是什麼?
:::
### 進階語法
- 結構(struct)
- 指標與陣列(pointer)
- 巨集(macro)
:::spoiler 題目:struct and array
```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';`
:::
:::spoiler 題目:pointer
```cpp=
void func(int *arr) {
// ...
}
int main() {
int arr[10] = {1};
func(arr);
}
```
問 傳進 func 的參數是什麼
A) 0
B) 1
C) 陣列的所有數字
D) 陣列的位址
:::
:::spoiler 題目:pointer
```c=
int f(int *a, int *b);
int g(int *a, int *b);
int main(){
int a = 2, b = 5;
int x = f(&a, &b);
printf("%d %d %d", x, a, b);
}
int f(int *a, int *b){
int c = 10;
*a = *a + *b / 5;
int p = g(b, a) % 2;
if (p % 2 == 0){
return *b - p;
} else {
return *b + p;
}
}
int g(int *a, int *b){
return (*a - *b) * 5 + 2;
}
```
求輸出結果
:::
:::spoiler 題目:macro 陷阱
```cpp=
#define add(a, b) a + b
int main() {
printf("%d\n", add(3, 5) * add(3, 5));
}
```
問輸出結果
:::
### 函式
:::spoiler 題目:多層函式呼叫、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;
}
```
詢問輸出結果
:::
### 遞迴函式
:::spoiler 題目:遞迴算 1+2+3+ . . . +n
```c=
int sum(int n){
if (???){
return ???;
}
return n + sum(n-1);
}
```
(1) n<=1, n
(2) n<0, n+1
(3) n==0, 0
答案是三個都可以
:::
:::spoiler 題目:遞迴算 a 的 n 次方
```cpp=
int f(int x, int y) {
if (x == y)
return 1;
return f(x, y - 1) * x;
}
```
問 f(2, 5) 回傳多少
:::
:::spoiler 題目:遞迴、2進制
```cpp=
void func(int n) {
if (n > 0) {
printf ("%d", n % 2);
func(n / 2);
}
}
func(21)
```
詢問回傳結果
:::
:::spoiler 題目:遞迴(先遞迴、後遞迴)
```cpp=
void func(int n) {
printf("%d ", 2 * n);
if (n < 4)
func(n + 1);
printf("%d ", 2 * n - 1);
}
func(2)
```
詢問輸出結果
:::
:::spoiler 題目:遞迴、數學
```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));
}
```
詢問輸出結果
:::
:::spoiler 題目:遞迴、數學
```c=
int f(int n){
if (n>=101) return n - 10;
return f(f(n + 11));
}
```
求出 f(5) 與 f(99)
:::
:::spoiler 題目:遞迴 trace code
```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);
```
詢問輸出結果
:::
:::spoiler 題目:遞迴 trace code
```c=
int f(int n){
if (n<2) retur n;
if (n / 2 % 2 == 0){
return -n * f(n-2);
} else {
return n * f(n-2);
}
}
```
求 f(8)
:::
:::spoiler 題目:遞迴 trace code
```cpp=
int f(int n) {
if (n == 0)
return 0;
printf("%d\n", n);
int tmp = n % 10 + f(n / 10);
printf("%d\n", tmp);
return tmp;
}
```
問 f(123) 輸出結果
:::
:::spoiler 題目:遞迴、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));
}
```
詢問輸出結果
:::
:::spoiler 題目:遞迴、判斷回文
判斷一個字串是不是回文
```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)
:::
## 數學
### 最大公因數(gcd)
:::spoiler 題目:gcd 遞迴式
```cpp=
int f(int a, int b) {
if (b == 0) {
return a;
}
return ???
}
```
問 ??? 填什麼 f 才會回傳 a, b 的最大公因數?
A. `f(a, b%a)`
B. `f(a%b, a)`
C. `f(b, a%b)`
D. `f(a%b, b)`
:::
:::spoiler 題目: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));
}
```
詢問輸出結果
:::
### 等差級數、等比級數
:::spoiler 題目:數學、級數
```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)
```
詢問輸出結果
:::
:::spoiler 題目:巢狀迴圈、數學
```c=
int f(int n){
int a = 0;
for (int i=0; i<n; i++){
for (int j=1; j<=n; j = j*2){
for (int k=i; k<n; k++){
a++;
}
}
}
return a;
}
```
求 f(n) 的結果
:::
### 帕斯卡三角形
:::spoiler 題目:帕斯卡三角形相關
```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]
:::
:::spoiler 題目:遞迴、帕斯卡三角形
```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);
```
詢問輸出結果
:::
### 費氏數列
:::spoiler 題目:迴圈版費氏數列
迴圈版本費氏數列
```cpp=
int a = 1, b = 1;
int s = a + b;
int n = 8;
while (i < n) {
a = b;
b = s;
s = a + b;
i++;
}
printf("%d\n", s);
```
問輸出結果
:::
### 質數篩法
:::spoiler 題目:迴圈、質數篩法
```c=
int a[21] = {0};
for (int i=0; i<=20; i++){
a[i] = 0;
}
for (int i=3; i<=20; i++){
if (a[i] == 0){
for (int j=i*i; j<=20; j+=i){
a[j] = 1;
}
}
}
```
求 a 最後有幾項是 1
:::
## 演算法概念
### $O(n^2)$ 排序法
:::spoiler 題目: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");
}
```
詢問輸出結果
:::
:::spoiler 題目:Bubble Sort 小變化
```c=
int F(int seed) {
int a[10] = {...};
for (int i=0 ;i<9; i++){
if (a[i+1] >= a[i] && a[i+1] <= seed){
int temp = a[i+1];
a[i+1] = a[i];
a[i] = temp;
}
}
printf("%d", a[seed-3]);
}
```
給定 seed = 7
求輸出結果
:::
:::spoiler 題目:Bubble Sort 小變化
```c=
int F() {
int a[8] = {8, 7, 6, 5, 1, 2, 3, 4}
for (int i=0; i<7; i++){
for (int j=i; j<7; j++){
if (a[i+1] >= a[i]){
int temp = a[i+1];
a[i+1] = a[i];
a[i] = temp;
}
}
}
}
```
求出最後 a 的內容
:::
:::spoiler 題目:Bubble Sort 交換次數問題
```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}
:::
:::spoiler 題目:Bubble Sort 交換次數問題
```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} 交換幾次
:::
:::spoiler 題目: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;
:::
### 二分搜尋法
:::spoiler 題目:二分搜尋法
```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` 執行了幾次
:::
:::spoiler 題目:二分搜尋法
```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
:::
:::spoiler 題目:二分搜尋法
```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);
}
```
最後的輸出是 5
問 mid + 1 應該要填入哪個 ____
:::
### 複雜度分析
:::spoiler 題目:複雜度
$\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 比較快
:::
:::spoiler 題目:估計迴圈次數
```cpp=
void F(int n) {
int ans = 0;
for (int i = 1; i <= n; i = i * 2) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k < j; k++) {
ans++;
}
}
}
printf("%d\n", ans);
}
```
請問呼叫 `F(100)` 的輸出最接近下面哪個選項?
(A) 100000000
(B) 5000000
\(C\) 30000
(D) 10000
:::
## 資料結構概念
- stack
- queue
:::spoiler 題目:queue
```cpp=
int main() {
int Q[5];
int i, j, loc = 0;
scanf("%d%d", &i, &j);
if (i == 1) {
for (int i = loc; i > 0; i--)
Q[i] = Q[i - 1];
Q[0] = j;
} 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) 4 1 2 0 0
:::
:::spoiler 題目:random stack
已經給定一個 stack 的實做程式法,支援 `empty`, `push(x)`, `pop()`, `top()`
```c=
int level = 1;
for (int i=0; i<6; i++){
if (empty()){
push(level);
level = level + 1;
} else if (rand() % 2 == 0){
printf("%d ", top());
pop();
level = level - 1;
} else {
push(level);
level = level + 1;
}
}
while (!empty()){
printf("%d ", top());
pop();
}
```
找出不可能的輸出結果
:::
## 其它(計算機概論知識、不宜出在 apcs 的題目)
:::spoiler 題目:考名詞
```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
:::
:::spoiler 題目:後序運算式 parser
給一個運算式 "3*5/6+2-1",求它的後序運算式
:::
<br>
<br>
![](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)
![](https://i.imgur.com/JENpJ4J.png =300x)