# APCS 觀念題 - 演算法與資料結構
###### tags: `APCS`
## 第 1 題
List 是一個陣列，裡面的元素是 element，它的定義如下。
```c
struct element
{
char data;
int next;
}
```
List 中的每一個 element 利用 `next` 這個整數變數來記錄下一個 element 在陣列中的位置，如果沒有下一個 element，`next` 就會記錄 -1。所有的 element 串成了一個串列 (linked list)。例如在 list 中有三筆資料：
|1|2|3|
|-|-|-|
|data = 'a'<br>next = 2|data = 'b'<br>next = -1|data = 'c'<br>next = 1|
它所代表的串列如下圖：
`RemoveNextElement` 是一個函式，用來移除串列中 `current` 所指向的下一個元素，但是必須保持原始串列的順序。例如，若 `current` 為 `3` (對應到 `list[3]`)，呼叫完 `RemoveNextElement` 後，串列應為
請問在下方程式碼中 (?) 應該填入的程式碼為何?
```c
void RemoveNextElement(element list[], int current)
{
if (list[current].next != -1)
{
/*移除 current 的下一個 element*/
___(?)___;
}
}
```
(A) `list[current].next = current;`
(B) `list[current].next = list[list[current].next].next;`
\(C\) `current = list[list[current].next].next;`
(D) `list[list[current].next].next = list[current].next;`
<!-- B -->
## 第 2 題
下方程式片段擬以輾轉除法求 `i` 與 `j` 的最大公因數。請問 `while` 迴圈內容何者正確？
```c
i = 76;
j = 48;
while ((i % j) != 0) {
________________
________________
________________
}
printf ("%d\n", j);
```
(A) `k = i % j;` `i = j;` `j = k;`
(B) `i = j;` `j = k;` `k = i % j;`
\(C\) `i = j;` `j = i % k;` `k = i;`
(D) `k = i;` `i = j;` `j = i % k;`
<!-- A -->
## 第 3 題
下方程式片段主要功能為：輸入六個整數，檢測並印出最後一個數字是否為六個數字中最小的值。然而，這個程式是錯誤的。請問以下哪一組測試資料可以測試出程式有誤？
```c
#define TRUE 1
#define FALSE 0
int d[6], val, allBig;
// ...
for (int i = 1; i <= 5; i = i + 1)
{
scanf("%d", &d[i]);
}
scanf("%d", &val);
allBig = TRUE;
for (int i = 1; i <= 5; i = i + 1)
{
if (d[i] > val)
{
allBig = TRUE;
}
else
{
allBig = FALSE;
}
}
if (allBig == TRUE)
{
printf("%d is the smallest.\n", val);
}
else
{
printf("%d is not the smallest.\n", val);
}
```
(A) 11 12 13 14 15 3
(B) 11 12 13 14 25 20
\(C\) 23 15 18 20 11 12
(D) 18 17 19 24 15 16
<!-- B -->
## 第 4 題
下面哪組資料若依序存入陣列中，將無法直接使用二分搜尋法搜尋資料？
(A) a, e, i, o, u
(B) 3, 1, 4, 5, 9
\(C\) 10000, 0, -10000
(D) 1, 10, 10, 10, 100
<!-- B -->
## 第 5 題
給定一個 1x8 的陣列 `A`， `A = {0, 2, 4, 6, 8, 10, 12, 14}`。下方函式 `Search(x)` 真正目的是找到 `A` 之中大於 x 的最小值。然而，這個函式有誤。請問下列哪個函式呼叫可測出函式有誤？
```c
int A[8] = {0, 2, 4, 6, 8, 10, 12, 14};
int Search(int x)
{
int high = 7;
int low = 0;
while (high > low)
{
int mid = (high + low) / 2;
if (A[mid] <= x)
{
low = mid + 1;
}
else
{
high = mid;
}
}
return A[high];
}
```
(A) `Search(-1)`
(B) `Search(0)`
\(C\) `Search(10)`
(D) `Search(16)`
<!-- D -->
## 第 6 題
下方函式兩個回傳式分別該如何撰寫，才能正確計算並回傳兩參數 `a`, `b` 之最大公因數 (Greatest Common Divisor)？
```c
int GCD(int a, int b)
{
int r;
r = a % b;
if (r == 0)
return __________;
return _____________;
}
```
(A) `a`, `GCD(b,r)`
(B) `b`, `GCD(b,r)`
\(C\) `a`, `GCD(a,r)`
(D) `b`, `GCD(a,r)`
<!-- B -->
## 第 7 題
若 `A[1]`、`A[2]`，和 `A[3]` 分別為陣列 `A[]` 的三個元素 (element)，下列那個程式片段可以將 `A[1]` 和 `A[2]` 的內容交換？
(A) `A[1] = A[2]; A[2] = A[1];`
(B) `A[3] = A[1]; A[1] = A[2]; A[2] = A[3];`
\(C\) `A[2] = A[1]; A[3] = A[2]; A[1] = A[3];`
(D) 以上皆可
<!-- B -->
## 第 8 題
給定一整數陣列 `a[0]`、`a[1]`、...、`a[99]` 且 `a[k] = 3*k + 1`，以 `value = 100` 呼叫以下兩函式，假設函式 `f1` 及 `f2` 之 `while` 迴圈主體分別執行 `n1` 與 `n2` 次 (i.e, 計算 `if` 敘述執行次數，不包含 `else if` 敘述)，請問 `n1` 與 `n2` 之值為何？
註： `(low + high) / 2` 只取整數部分。
```c
int f1(int a[], int value)
{
int r_value = -1;
int i = 0;
while (i < 100)
{
if (a[i] == value)
{
r_value = i;
break;
}
i = i + 1;
}
return r_value;
}
```
```c
int f2(int a[], int value)
{
int r_value = -1;
int low = 0, high = 99;
int mid;
while (low <= high)
{
mid = (low + high) / 2;
if (a[mid] == value)
{
r_value = mid;
break;
}
else if (a[mid] < value)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return r_value;
}
```
(A) n1 = 33, n2 = 4
(B) n1 = 33, n2 = 5
\(C\) n1 = 34, n2 = 4
(D) n1 = 34, n2 = 5
<!-- D -->
----
## 解答
|1|2|3|4|5|
|-|-|-|-|-|
|B|A|B|B|D|
|6|7|8|9|10|
|-|-|-|-|-|
|B|B|D|-|-|
[<< APCS 觀念題 - 遞迴](https://hackmd.io/@kaeteyaruyo/APCS-concept-recursion) | [目錄](https://hackmd.io/@kaeteyaruyo/APCS-concept-index)
Sign in with Wallet
Connect another wallet