---
# System prepended metadata

title: 台大 105 軟體
tags: [NTU, '105', 軟體]

---

# 台大 105 軟體
###### tags: `NTU` `105` `軟體`

1. DGCBCH
2. (a) $O(n^{log_83})$
(b) $O(lglgn)$
\(c\) $O(\frac{n^3}{\sqrt{M}})$
3. (a) i. $O(1+\frac{n}{m})$  ii. recursively 是...open addressing 的意思??看不懂
(b) $m=O(n^2)$
:::info
兩個 element 衝突的機率為: $\binom{m}{1}\frac{1}{m^2}=\frac{1}{m}$
期望值為 $\binom{n}{2}\frac{1}{m}=\frac{n(n-1)}{2}\frac{1}{m}=O(1)$
得 $m=O(n^2)$
:::
\(c\) 略
4. (a)
```c=
typedef struct node {
    int key;
    struct node *left;
    struct node *right;
} node;

bool verify(node *r)
{
    if (r == NULL) return true;
    
    return verify(r->left)  &&
           verify(r->right) && 
           (r->left == NULL  || r->left->key  <= r->key) && 
           (r->right == NULL || r->right->key >= r->key);

}
```
(b) 
```c=
int count(int n)
{
    if (n <= 1) return 1;
    
    int result = 0;
    for (int i = 0; i < n; i++) {
        result += count(i) * count(n - i - 1);
    }
    
    return result;
}
```
:::info
n 個點的二元搜尋樹的數量為第 n 個卡特蘭數
:::
\(c\)
:::info
            B
           / \
          /   \
         R     B
        / \     \
       B   B     R
      /
     R  
:::
5. 略
6. 令 $\Phi(H)=$ 所有節點的深度總和
- INSERT: $lgn + lgn=O(lgn)$ <= 因為多了一個深度為 $lgn$ 的節點
- EXTRACT-MIN: $lgn - lgn=O(1)$ <= 因為少了一個深度為 $lgn$ 的節點
7. (a) (1) 0 (2) 1 (3) $L(i + 1, j - 1) + 2$ (4) $max(L(i + 1, j), L(i, j - 1))$
(b) 略