# 成大 100 軟體
###### tags: `NCKU` `100` `軟體`
1. (a) AVL Tree 和 Red-Black Tree 都會得到 (a) 的結果
(b) 母災
\(c\) min-heap
2. 最小的差距，只會發生在相鄰兩數。設計以下三組函式:
$MINGAP(r)$: 以 r 為祖父的所有數字間，最小的差距
$MAX(r)$: 以 r 為根的子樹中最大的值
$MIN(r)$: 以 r 為根的子樹中最小的值
則 $MINGAP(r) = \\min(MINGAP(r.left),MINGAP(r.right),\\r - MAX(r.left), MIN(r.right)-r)$
$MIN$ 跟 $MAX$ 都可以在 $O(lgn)$ 內求出，只需要一直往最左/最右走就可以了
3. (b) 先來先贏, queue
\(c\) hash
(d) 走迷宮通常是用 DFS，DFS 會用到 stack
(e) hash
(f) 看起來要最佳化硬碟的存取，選 B-Tree
7. 令 $Count(i)=$ $i$ 的個數
令 $Accu(i)$ 為 $0$~$i$ 的所有數字的個數

$$Accu(i) = Count(i) + Accu(i-1)$$
則 query $[a, b]$ 可用 $Accu(b)-Accu(a-1)$ 算出