# 台大 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)

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)

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) 略