政大 112 年資管所（科技組） 資料結構 參考答案

$$L[i,j]=\{\begin{array}{cc}0\hfill & \text{if }i=0\text{ or }j=0\hfill \\ L[i-1,j-1]+1\hfill & \text{if }X[i-1]=Y[j-1]\hfill \\ max(L[i-1,j],L[i,j-1])\hfill & \text{if }X[i-1]\ne Y[j-1]\hfill \end{array}$$

1. 建立 $(m+1)\times (n+1)$ 表格，第 0 列與第 0 行設為 0。
2. 逐列逐行依上式填表，$L[m,n]$ 即為 LCS 長度。
3. 由 $L[m,n]$ 反向追蹤：字元相等時輸出該字元並往左上走，否則往 $L[i-1,j]$、$L[i,j-1]$ 中較大者走，最後把輸出反轉即為 LCS。

$L[12,9]=8$。

（如簡答圖）

對 $T$ 做 Inorder Traversal（左、根、右），依序印出 key。

輸出：22, 26, 27, 29, 33, 48, 49, 53, 54, 69, 72, 97, 99, 108, 120, 208

$T$：

（如簡答圖）

put(118) 後：

（如簡答圖-2）

最終雜湊表（未列出者為空）：

0:108　1:27　2:29　3:54　4:26　6:33　12:120　15:69　16:97　18:72　19:99　20:208　21:48　22:22　23:49　26:53

最終雜湊表（未列出者為空）：

0:108　1:49　2:29　6:33　11:54　12:120　15:69　16:97　18:72　19:208　21:48　22:22　23:99　24:27　25:26　26:53

（如簡答圖）

function evaluate(node):
    if node is a leaf (external node):
        return node.value
    leftVal  = evaluate(node.left)
    rightVal = evaluate(node.right)
    return applyOperator(node.operator, leftVal, rightVal)

function printExpression(v):
    if v is a leaf (external node):
        print(v.value)
    else:
        print("(")
        printExpression(v.left)
        print(v.operator)
        printExpression(v.right)
        print(")")