# 清大 112 計算機科學
###### tags: `考古`

大家好，因為清大都不公布考古，這邊想直接背出來
希望大家有印象的題目可以麻煩幫忙補上或是更正，以便明年考生參考，謝謝

~~詳解我考完再補~~
暑假慢慢補

## 答案僅供參考，錯了跟我講/留言一下，感謝
## 沒題號的題目

### 1.

大小為 N 的 uniform hash 兩個東西 collision 的機率
Ref Answer : **$\frac{1}{N}$**

### 2.

Quick sort worst case time complexity
Ref Answer : **$O(n^2)$**

### 3.

每個node有k個key 總共有n 個 node 有多少的 key 沒用到

:::spoiler 參考詳解
有 nk 個 link, 只有 n - 1 個有用到
:::
Ref Answer : **$nk - n + 1$**

### 4.

SCC & DAG
忘記選項ㄌ

### 5.

Trace dfs的code 求 foo 的 return value

#define INT_MIN -10000
struct Node {
    int val;
    Node *left;
    Node *right;
};
int dfs(Node *r, int &ans) {
    if(!r)
        return 0;
    int left = max(dfs(r->left), 0);
    int right = max(dfs(r->right), 0);
    ans = max(ans, r->val + right + left);
    return r->val + max(right, left);
}
int foo(Node *root) {
    int ans = INT_MIN;
    dfs(root, ans);
    return ans;
}

慢慢 trace 畫圖，要注意的是題目是問 foo 的 return value, 不是問 dfs 的 return value.
### 6.

上面 code 的 time/space complexity

Ref Answer : 時間 **$O(n)$** 空間 **$O(h)$**

### Postorder

Postorder 的順序
Postorder 轉換 inorder 過程中 stack 最大深度

### Amortized cost

A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. Please determine the amortized cost.

:::spoiler 參考詳解

:::
Ref Answer : **$O(1)$**

### 矩陣最小乘法數

A1為5x3，A2為3x4，A3為4x4，A4為4x2。求A1 x A2 x A3 x A4的最少乘法數。

:::spoiler 參考詳解
經典 DP 題
| 5 x 3 | 3 x 4 | 4 x 4 | 4 x 2 |
|-------|-------|-------|-------|
| 60 | 48 | 32 | |
| 108 | 56 | | |
| 86 | | | |

- **First row**
60 = 5 x 3 x 4 (A1 x A2)
48 = 3 x 4 x 4 (A2 x A3)
32 = 4 x 4 x 2 (A3 x A4)
- **Second row**
108 = 5 x 3 x 4 + 48 (A1 x (A2 x A3))
56 = 3 x 4 x 2 + 32 (A2 x (A3 x A4))
- **Ans**
86 = 5 x 3 x 2 + 56 (A1 x (A2 x (A3 x A4)))
:::
Ref Answer : **86**

### 複雜度

$T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + n$, find Theta notation
:::spoiler 參考詳解
$\frac{1}{2} + \frac{1}{4} < 1$

94年成大資工考過 $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n$
這題答案也是 $\Theta(n)$
:::
Ref Answer : **$\Theta(n)$**

### Logic

給一個方程式的解有p(x):x^2 - 10x + 21 = 0 , q(x) : x is odd , r(x) x > 0 選敘述為 true 的選項
Ref Answer : **$\exists（q(x) \implies p(x))$**

### Relation

有一個set = {A,B,C,D}。求reflexive且symmetric的relations有多少個
Ref Answer : 2^(3 * 2) = **64**

### 排列組合

4 digit 的密碼可填 1, 2, 3, 4，求密碼至少1個1，1個2，1個3的方法數
Ref Answer : 24 + 36 = **60**

### 機率

電腦剛拿到的時候壞掉的機率是 0.05, 如果剛拿到的時候沒有壞, 則能用至少一年的機率是 0.98, 問一台全新的電腦至少能用一年的機率是多少
Ref Answer : **0.95 * 0.98 = 0.931**

### Closure

Which of the following is a group:
A. $({1, -1}, "+")$
B. $({1, -1}, " * ")$
C. $({1, -1, 0}, "+")$
D. $({\frac{a}{2^b} | a, b in Z}, "+")$
E. $({f | f:A -> A,and f: 1-1 where A = {1, 2, 3, 4}}, "。" )$
Ref Answer : **BDE**

### 19.

Topological sort 的合法順序

Ref Answer : **ABD**

### 多選某些選項

1. Insertion sort 最佳情況
Ref Answer : **sorted**
2. Postfix 跟 Prefix 可轉換成 unique 的 tree
Ref Answer : **False**
3. Every elements in binary search tree is unique then binary search tree is unique
Ref Answer : **False**
4. $O(n^{2.0001}) > O(n^2logn)$
Ref Answer : **True**

### Greedy

Coin change 如果是 1, 2, 5 可以用 greedy 解 1, 6, 10 or 1, 6, 15這種沒辦法

Cashier's Algorithm 的適用情況

### vector, deque, linked-list
A. If can random access 且 insert/delete 元素在最尾端 最適合的是 **vector**
B. If can random access 且 insert/delete 元素在首尾兩端 最適合的是 **deque**
C. If insert/delete 元素在中間 最適合的是 **linked-list**
D. 如果x可以被search且需要依照大小排序 最適合的是 **map**
E. none
Ref Answer : **ABCD**

### 25. Choose **Right** statement

A. If some problem can polynomial reduce to some NP-complete problem, then it belongs to NP-complete
B. If there is a NP-complete problem can be solved in polynomial time then, P = NP
C. Define an integer is a prime or not is NP-complete
D. Find a Hamiltonian path in DAG can be solved in polynomial time
E. Time complexity of 0/1 knapsack is O(nW), so 0/1 knapsack can be solved in polynomial time.
:::spoiler 參考詳解
A. 證明 problem X 是 NP-complete 需先證明 X 在 NP, 且存在 NP-complete 可以 polynomial reduce 到 X
C. Neither P nor NP-C
E. Pseudo polynomial
:::

Ref Answer : **BD**

### 26. Choose **Right** statement

A. MST is not unique (不唯一但可以唯一)
C. Bellman-ford 跟 Dijkstra 在 all positive edge 的圖上執行時，可以選到不同的 edge ，但最後的 shortest path 長度會是一樣的
D. 考慮 edge weight 皆為 positive 的 Graph 執行 dijkstra 後的 shortest path, 其結果跟相同的圖對每個 edge - min edge weight 後做 dijkstra 所得到的 shortest path 是一樣的
E. 如果一個圖 DFS 的過程只得到剛好一條 back edge 則這張圖移除某條 edge 後會是 DAG
Ref Answer : **CE**

### 離散雜項

題目是 i = 1 開始, 但應該是要從 i = 0 開始才會是正負根號五