# 112 北科 程設 參考詳解
> ==採用 [CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hant) 許可協議共享，轉載請註明來源，禁止任何營利使用。==
> [name=SayA] [time=Tue, Feb 20, 2024 10:19 PM] [color=#4c33af]
- [PDF手寫檔](https://drive.google.com/file/d/1IapZhbJZ0psx16S5QA64RZz7XLUfK1XV/view?usp=sharing)，手寫檔會用螢光筆標註一些重要的地方，可搭配服用。
- 程式碼部分修改自 [@jack804916](https://www.dcard.tw/f/graduate_school/p/254653623) 提供的程式碼，使得我不用花過多精力在OCR考卷上，在此致謝。
- 修改後的程式碼與考卷上的**行號對齊**。
## Problem 1
### 題目
- Suppose that the outputs of the following `C` program are as follows: $2, 3, 12, 21, 23, 43, 65$
- Please trace the program and fill the blanks with correct statements.
### 答案
1. `NULL`
2. `parent->left`
3. `parent->right`
4. `root`
5. `root->left`
6. `root->right`
### Code
```cpp=
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} node_t;
typedef node_t * nodep_t; // a nodep_t is a pointer to a node_t
nodep_t createNode(int value) {
nodep_t p = (nodep_t) malloc(sizeof(node_t));
p->data = value;
p->left = p->right = NULL; // 左右子節點初始化為空節點 /* Problem 1-1 */
return p;
}
void build(nodep_t current, nodep_t newNode, int value) { // 從二分可以判斷是BST
nodep_t parent;
while (1) {
parent = current;
if (value < parent->data) {
current = current->left;
if (current == NULL) {
parent->left = newNode; /* Problem 1-2 */
return;
}
}
else {
current = current->right;
if (current == NULL) {
parent->right = newNode; /* Problem 1-3 */
return;
}
}
}
}
nodep_t insert(int value, nodep_t root) {
nodep_t current, parent, newNode;
newNode = createNode(value);
if (root == NULL) {
root = newNode;
} else {
parent = current = root; // parent其實不會用到，是誤導用的，考慮cur即可 /* Problem 1-4 */
build(current, newNode, value);
}
return root;
}
void inorder_traversal(nodep_t root) {
if (root != NULL) {
inorder_traversal(root->left); /* Problem 1-5 */
printf("%d ", root->data);
inorder_traversal(root->right); /* Problem 1-6 */
}
}
int main() {
nodep_t root = NULL;
int array[] = {23,12,43,21,65,3,2};
for (int i=0; i<7; i++) {
root = insert(array[i], root); // 由題幹中可知inorder traversal的結果是由小到大的，所以是BST
}
inorder_traversal(root);
return 0;
}
```
### 說明
- 從給定的輸入是 $23, 12, 43, 21, 65, 3, 2$ 和 `inorer traversal` 的結果是 $2, 3, 12, 21, 23, 43, 65$ ，可以得出是BST，但直接trace code就可了。
- `build` 為根據二分結果插入newNode，也可以得出為BST的insert
- ++line 43++ 的 $parent$ 其實沒用到，是誤導用的。
## Problem 2
### 題目
Please trace the following `C` program and answer the output of each printf() statement for problems 2-1~2-6.
### 答案
1. `NTUTGood`
2. `0`
3. `5 7`
4. `21`
5. `4.00`
6. `001` 假設array D被初始化為0，否則未初始化的變數具有不確定的值，可能會導致 ==Undefined behavior (UB)==。
### Code
```cpp=
#include <stdio.h>
#include <stdlib.h>
typedef enum {black_ops, top_secret, secret, non_secret} securitylevels; // 0, 1, 2, 3
void f1(char *s1, char *s2) { // s1 = concatenation of s1 and s2
for (; *s1!='\0'; s1++); // find the end of s1
for (; *s2!='\0'; *s1=*s2, s1++, s2++); // concatenate s2 to s1
*s1 = '\0';
}
securitylevels f2() {
return (non_secret-black_ops)/3<secret?black_ops:non_secret;
}
int getValue(int A[][2], int B[][2], int n, int row, int column) {
int value = 0;
for (int k=0; k<n; k++) {
value = value + A[row][k]*B[k][column];
}
return value;
}
void f3(int A[2][2], int B[2][2], int C[2][2], int n) {
for (int row=0; row<n; row++) {
for (int column=0; column<n; column++) {
C[row][column] = getValue(A, B, n, row, column);
}
}
}
int f4(int i) { // return i+1
int *p = &i, *q = p; // p, q are both pointers to i
return ++(*q);
}
double f5(int a, int b) {
double t = ((a--)/3+b%4); // a-- means a is used first, then decremented
return t;
}
void f6(int D[], int n) {
int i=0, m=0;
m = n>>4; // clear the last 4 bits of n, and store the result in m
m = m<<4;
for (int i=7; i>=4; i--) { // if the i-th bit of n is 1, then the i-th element of D is 1
D[i] = (m&(1<<i))?1:0;
}
}
int main() {
char s1[100] = "NTUT", s2[100] = "Good";
int A[2][2] = {{1,2}, {2,1}}, B[2][2] = {{1,2}, {2,3}}, C[2][2], D[10];
f1(s1, s2);
printf("%s\n", s1); /* Problem 1-1 */
printf("%d\n", f2()); /* Problem 1-2 */
f3(A,B,C,2);
printf("%d %d\n", C[0][0], C[1][1]); /* Problem 1-3 */
printf("%d\n", f4(20)); /* Problem 1-4 */
printf("%3.2f\n", f5(6, 6)); /* Problem 1-5 */
memset(D, 0, sizeof(D)); f6(D, 123); // 假設array D被初始化為0
printf("%d%d%d\n", D[1], D[3], D[5]); /* Problem 1-6 */
}
```
### 說明
#### $f1()$
- ++line 05++ 為將s1的指標移到s1的結尾(即`'\0'`的位置)。
- ++line 06++ 為將s2的字元一個一個複製到s1 (`*s1 = *s2`)，直到s2的結尾(即`'\0'`的位置)。
- 故 $f1()$ 為 ==字串串接(concatenation)== 的函數，將s2的字串串接到s1的後面。
#### $f2()$
- $securitylevels$ 是一個==列舉型別（enum）==，它包含四個值：$black_ops$、$top_secret$、$secret$ 和 $non_secret$。這四個值在內部都會被賦予一個整數值，預設從 $0$ 開始，並按照它們在列舉中的順序遞增。也就是說，$black_ops$ 的值為 $0$，$top_secret$ 的值為 $1$，$secret$ 的值為 $2$，$non_secret$ 的值為 $3$。
- `(condition)?x:y` 是==三元運算子（Ternary Operator）==，如果condition為真，則回傳x，否則回傳y。
- `return (3-0)/3<2?0:3`，condition部分為 $1<2$，故回傳 $0$。
#### $f3()$
- $f3()$ 為==矩陣相乘(matrix multiplication)==的函數，將 $A$ 和 $B$ 兩個 $2\times 2$ 的矩陣相乘，結果存入 $C$。
$$
A = \begin{bmatrix}
1 & 2 \\
2 & 1
\end{bmatrix},
B = \begin{bmatrix}
1 & 2 \\
2 & 3
\end{bmatrix},
C = \begin{bmatrix}
5 & 8 \\
4 & 7
\end{bmatrix}
$$
#### $f4()$
- $p$ 和 $q$ 都是指向 $i$ 的指標，所以 $*p$ 和 $*q$ 都是 $i$，因此 $f4(i)$ 為將 $i$ 加一後回傳的函數。
#### $f5()$
- 若 ==decrement operator== `--`
- 在變數後面，則先使用變數，再遞減（先用再減）；
- 在變數前面，則先遞減，再使用變數（先減再用）。
- 故 $f5(6, 6)$ 為 $((6--)/3+6\%4) = 6/3+2 = 2+2 = 4$，再轉型為 `double` 型態，返回 $4.0$。
- `printf("%3.2f\n", f5(6, 6));` 表示要輸出一個浮點數，整數部分至少有 3 位，小數部分有 2 位，故輸出 $4.00$。
:::success
📌 其他考點：
- 需注意 `(int) / (int)` 為整數除法，結果為整數，若要轉型為 `double`，則至少有一個運算數為 `double`。
- 若將題目改成 `double t = ((a--)/4+b%4);`，則結果為 $1+2 = 3.0$。
- 若將題目改成 `double t = ((a--)/4.0+b%4);`，則結果為 $1.5+2 = 3.5$。
:::
#### $f6()$
- $m = n>>4$ 和 $m = m<<4$ 的作用是清除 $n$ 的最後 4 位，即將 $n$ 的最後 4 位設為 0，並將結果存入 $m$。
- `D[i] = (m&(1<<i))?1:0;` 的作用是判斷 $n$ 的第 $i$ 位是否為 1，若為 1，則 $D[i]$ 設為 1，否則設為 0。
- $n = 123$ 的二進位為 $1111011$，故 $m = 112$，其二進位為 $1110000$，故 $D[4] = 1, D[5] = 1, D[6] = 1, D[7] = 0$。
- 若array $D$ 未初始化，則未初始化的變數具有不確定的值，可能會導致 ==Undefined behavior (UB)==。
- 假設array $D$ 被初始化為 $0$，則 $D[1] = 0, D[3] = 0, D[5] = 1$，故輸出為 $001$。
## Problem 3 (1)
### 題目
Please trace the following `Python` program and answer the output of each print() statement for problems (3-1~3-7).
### 答案
1. `6`
2. `2`
3. `13`
4. `[['Bob', 50, 70]]`
5. `utod`
6. `[8, 16, 6]`
7. `bc`
### Code
```python=
def f1(n):
X = [i for i in range(1, n) if i % 2 == 0]
return (X)
def f2(S):
data = dict()
for s in S:
if s in data.keys():
data[s] = data[s]+1
else:
data[s] = 1
return data
def f3(n):
f = lambda m,n: m*n+1
X = {i: f(i, i+1) for i in range(1, n) if i % 3 == 0}
return (X)
def f4():
scores = [['John', 90, 80], ['Bob', 50, 70], ['Mary', 80, 70]]
data = filter(lambda x: True if sum(x[1:3]) < 130 else False, scores)
return list(data)
def f5(s1, s2, m, n):
return s1[m:n]+s2[m:n]
def f6(A, B):
return list(map(lambda x, y: x**y, A, B))
def f7(data,n):
if n==len(data): return [data]
elif n==0: return ['']
s0 = f7(data[1:], n)
s1 = [data[0] + s for s in f7(data[1:], n-1)]
return sorted(s0+s1)
print(f1(8)[2]) # (Problem 3-1)
print(f2('ntut csie')['t']) # (Problem 3-2)
print(f3(6)[3]) # (Problem 3-3)
print(f4()) # (Problem 3-4)
print(f5('ntut','good',2,4)) # (Problem 3-5)
print(f6([2,4,6], [3,2,1])) # (Problem 3-6)
print(f7('abc', 2)[2]) # (Problem 3-7)
```
### 說明
#### $f1()$
- ==List Comprehension== 是一種用來創建列表的方法，它提供了一個簡潔的方法來創建列表。
- `X = [i for i in range(1, n) if i % 2 == 0]` 為創建一個列表，列表中的元素為 $1$ 到 $n-1$ 中的偶數。
- 故 $f1(8)[2]$ 為 $[2, 4, 6]$ 中的第 $3$ 個元素，即 $6$。
- 展開後的程式碼為：
```python
def f1(n):
# X = [i for i in range(1,n) if i%2==0]
X = []
for i in range(1,n): # in C/C++: for(int i=1; i<n; i++)
if i % 2 == 0:
X.append(i)
return (X)
```
#### $f2()$
- 使用 `dict()` 創建一個空字典，若 `s` 在字典中，則將 `s` 的值加一，否則將 `s` 加入字典中，並設為 $1$。
- 即為計算字串 `S` 中每個字元的出現次數。
- 故 `f2('ntut csie')['t']` 為字串 `'ntut csie'` 中字元 `t` 的出現次數，即 $2$。
:::success
📌 `python` 中的 `Counter` 可以簡單的達成同樣的效果。
```python
from collections import Counter
cnt = Counter(S)
```
:::
#### $f3()$
- 定義一個名為 $f$ 的 ==Lambda 函數==。Lambda 函數是一種匿名函數，在 `Python` 中，我們可以使用 `lambda` 關鍵字來創建 `lambda` 函數。
- 使用 ==Dictionary Comprehension== 創建一個字典，字典中的鍵為 $1$ 到 $n-1$ 中的 $3$ 的倍數，值為 $f(i, i+1)$。
- 故 `f3(6)[3]` 為字典 `{3: f(3, 4)}` 中的第 $1$ 個元素，即 $13$。
#### $f4()$
- `filter( function, iterable )`，`function` 為過濾函數，`iterable` 為可迭代對象。`filter` 函數的作用是對序列中的元素進行過濾，返回一個迭代器，迭代器中的元素是滿足條件的元素。
- 使用 ==filter 函數== 對 `scores` 中的每個元素進行過濾，條件為 `sum(x[1:3]) < 130`。
- 故 `f4()` 為過濾後的結果，即 `[['Bob', 50, 70]]`。
- 展開後的程式碼為：
```python
def isLessThan130(x):
if sum(x[1:3]) < 130:
return True
else:
return False
def f4():
scores=[['John',90,80],['Bob',50,70],['Mary',80,70]]
# filter( function, iterable )
data = filter(isLessThan130, scores)
return list(data)
```
#### $f5()$
- $s1[m:n]$ 為取字串 $s1$ 中從第 $m$ 個字元到第 $n-1$ 個字元的子字串，若 $n$ 超過字串長度，則取到字串結尾。
- 故 `f5('ntut','good',2,4)` 為 $'ntut'[2:4]$ 和 $'good'[2:4]$ 的串接，即 $'ut'+'od'$，即 $'utod'$。
#### $f6()$
- `map( function, iterable )`，`function` 為映射函數，`iterable` 為可迭代對象。`map` 函數的作用是對序列中的每個元素進行映射，返回一個迭代器，迭代器中的元素是映射後的結果。
- 使用 ==map 函數== 對 `A` 和 `B` 中的每個元素進行映射，映射函數為 `lambda x, y: x**y`。
- 故 `f6([2,4,6], [3,2,1])` 為 $[2^3, 4^2, 6^1]$，即 $[8, 16, 6]$。
- 展開後的程式碼為：
```python
def f6(A,B):
f = lambda x, y :x**y # exponentiation x^y, f(x,y) = x**y
res = []
for x, y in zip(A,B):
res.append(f(x,y))
return res
```
:::success
📌 對於一些需要手動處理輸出入的 Online Judge(OJ) 平台，很常會用到map函數，例如：
```python
arr = list(map(int, input().split()))
```
:::
#### $f7()$
- $f7()$ 為一個 ==遞迴(Recursion)函數==，遞迴函數是一個函數在其函數體中調用自己的函數。
- $f7(abc, 2) = ['ab', 'ac', 'bc']$
- $f7(bc, 2) = ['bc']$
- $f7(bc, 1) = ['b', 'c']$
- $f7(c, 1) = ['c']$
- $f7(c, 0) = ['']$
- $s0 = ['c']$
- $s1 = ["b" + s for s in ['']] = ["b"]$
- $s0 = ['bc']$
- $s1 = ["a" + s for s in ["b", "c"]] = ["ab", "ac"]$
- 故 `f7('abc', 2)[2]` 為 $['ab', 'ac', 'bc']$ 中的第 $3$ 個元素，即 $'bc'$。
:::success
📌 在 `python` 中，單引號 `''` 和 雙引號 `""` 是等價的，都可以用來表示字串。
:::
## Problem 3 (2)
### 題目
Suppose that the outputs of the following `Python` program are as follows:
- $[[5, 7], [19, 21]]$
- $[[5, 7, 9], [19, 21, 23], [33, 35, 37]]$
- $[[9, 12], [30, 33]]$
Please trace the program and fill the blanks with correct statements.
### 答案
8. `data[i][j]`
9. `(n*n)` 或 `n**2` ，前者因為 `*` 的operator precedence較低，所以要用括號括起來。
10. `m//n`
### Code
```python=
def op(data, x, y, n):
sum = 0
for i in range(x, x+n):
for j in range(y, y+n):
sum = sum + data[i][j] # (Problem 3-8)
return sum//(n*n) # (Problem 3-9)
def compress(data, m, n):
size = m//n # (Problem 3-10)
target = []
for x in range(size):
row = []
for y in range(size):
row.append(op(data, x*n, y*n, n))
target.append(row)
return target
data = [[1, 2, 3, 4, 5, 6, 7],
[8, 9, 10, 11, 12, 13, 14],
[15, 16, 17, 18, 19, 20, 21],
[22, 23, 24, 25, 26, 27, 28],
[29, 30, 31, 32, 33, 34, 35],
[36, 37, 38, 39, 40, 41, 42],
[43, 44, 45, 46, 47, 48, 49]]
print(compress(data, 4, 2), '\n##')
print(compress(data, 6, 2), '\n##')
print(compress(data, 6, 3), '\n##')
#(1+2+8+9)//4=5
#(3+4+10+11)//4=7;
#(15+16+22+23)//4=19,
#(17+18+24+25)//4=21
...
#(1+2+3+8+9+10+15+16+17)//9=9,
#(4+5+6+11+12+13+18+19+20)//9=12,
#(22+23+24+29+30+31+36+37+38)//9=30,
#(25+26+27+32+33+34+39+40+41)//9=33
```
### 說明
1. 由function名稱`compress`可知是壓縮的意思，所以是將原本的矩陣壓縮成較小的矩陣。
2. 壓縮可以將一定範圍內的數值取平均/取中位數/取最大值/取最小值等等，從++line 28-36++ 的註解可以看出是取平均。
3. 故 `op()` 函數的作用是取一定範圍內的數值的平均值，並返回結果。也就是以 $(x, y)$ 為左上角，長寬皆為 $n$ 的矩陣的平均值。
4. 從 ++line 25-26++ 的輸出結果可以看出，前 $2 \times 2$ 的內容一樣，故可以推測出 $m$ 為壓縮前的矩陣的長度，因此壓縮後矩陣的長度 $size = m//n$。
## Problem 3 (3)
### 題目
Suppose that the outputs of the following Python program are as follows:
$$
\begin{aligned}
& (0,0)(0,1)(0,2)(0,3) \\
& (1,0)(1,1)(1,2)(1,3) \\
& (2,0)(2,1)(2,2)(2,3) \\
& (3,0)(3,1)(3,2)(3,3)
\end{aligned}
$$
Please trace the program and fill the blanks with correct statements.
### 答案
11. `//`
12. `%`
### Code
```python=
def printSquare(n):
i = 0
while i < n*n:
print((i//n, i % n), end='') # (Problem 3-11), (Problem 3-12)
i = i+1
if i % n == 0:
print()
printSquare(4)
```
### 說明
- 觀察輸出結果可以得知，這段程式碼的目的是輸出一個 $n \times n$ 的方陣，方陣中的元素為 $(i, j)$，其中 $i$ 為行，$j$ 為列。
- 從 $0$ 開始，每次輸出 $(i//n, i\%n)$，其中
- `//` 是整除運算符，返回商的整數部分。
- `%` 是取餘運算符，返回除法的餘數。
## Problem 4 ~[TODO]~
### 題目
### 答案
### Code
### 說明
## Problem 5 ~[TODO]~
### 題目
### 答案
### Code
### 說明
<style> :root{
--markup-code: #000033;
}
.markdown-body code,
.markdown-body tt {
background-color: #ffcccc;
color: var(--strong-code);
}
.markdown-body strong{
color: var(--strong-code);
font-weight:700
}
.markdown-body code{
color: var(--markup-code)!important
}
</style>
Sign in with Wallet
Connect another wallet