中央 111 年資管所 資料結構 參考答案

Singly：節點 (data, next)，單向走訪；刪除須先找到前一節點。Doubly：節點 (prev, data, next)，雙向走訪；插入須改 4 條指標，已知節點即可刪除。

• Singly 優點：每節點只有一個指標，省記憶體、維護簡單；缺點：只能單向走訪，刪除已知節點 $O(n)$。
• Doubly 優點：可雙向走訪，刪除已知節點 $O(1)$；缺點：多一個指標，記憶體較多、指標維護較複雜。

(a) $2^{11}-1=2047$。

(b) $2^7=128$。

(a) 4, 2, 8, 9, 7, 17, 28, 22, 37, 44, 40, 45, 30, 15。

(b) （如簡答圖）

9, 7, 12, 15, 63, 45, 17, 22（pivot 取第一個元素 15）。

224（Column-major，$l_0=20$、$m=33$）。

Prefix：$+-\times 1237÷5117÷213$

Postfix：$1237\times 5117÷-213÷+$

MST 邊集合 $=\{1\text{-}4,6\text{-}7,4\text{-}6,1\text{-}5,2\text{-}3,2\text{-}5\}$，總權重 17。

i=1：28, 40, 56, 15, 63, 74, 98, 80；i=2：不變；i=3：15, 28, 40, 56, 63, 74, 98, 80；i=4～6：不變；i=7：15, 28, 40, 56, 63, 74, 80, 98。

/* 在已排序的 arr[low..high] 中找出 val 的插入位置 */
int binarySearchPos(int arr[], int val, int low, int high) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] <= val) low = mid + 1;   /* <= 保證 stable */
        else                 high = mid - 1;
    }
    return low;
}

void binaryInsertionSort(int arr[], int n) {
    int i, j, pos, val;
    for (i = 1; i < n; i++) {
        val = arr[i];
        pos = binarySearchPos(arr, val, 0, i - 1);
        for (j = i - 1; j >= pos; j--)
            arr[j + 1] = arr[j];              /* 大的往後搬 */
        arr[pos] = val;
    }
}

（如簡答圖）

MD5 輸出 128 bits（32 個十六進位字元），SHA-1 輸出 160 bits（40 個十六進位字元）；兩者皆已可實際構造碰撞，不再用於安全用途。

Average case $O(1)$：key 均勻分散，算一次雜湊值加常數次比對。

Worst case $O(n)$：所有 key 碰撞到同一 bucket，須逐一比對。