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

初始陣列：[24, 58, 89, 36, 48, 77, 10, 94, 99]

bottom-up 建堆後最終陣列：[99, 94, 89, 58, 48, 77, 10, 24, 36]

Best $O(1)$、Worst $O(\log n)$；Average：Insert $O(1)$、Delete-Max $O(\log n)$。

最終陣列：[94, 58, 89, 36, 48, 77, 10, 24]，99 移至陣列尾端（已排序區）。

(a) [67, 88] [34] [98] [17] [26, 35] [4] [23] [30] → [34, 67, 88] [17, 98] [4, 26, 35] [23, 30] → [17, 34, 67, 88, 98] [4, 23, 26, 30, 35] → 4, 17, 23, 26, 30, 34, 35, 67, 88, 98

(b) Best、Average、Worst 皆為 $\Theta (n\log n)$。

(c) 鍵值相等的資料排序後相對順序不變即為 stable；merge sort 是 stable。

(a)

function PrintFib(a, b):
    if a >= 1000: return
    print a
    PrintFib(b, a + b)

PrintFib(0, 1)

(b)

function PrintFibonacciIterative():
    a = 0
    b = 1
    print a
    while b < 1000:
        print b
        temp = a + b
        a = b
        b = temp

(a) 每一對相異頂點之間都恰有一條邊相連的 simple graph。

(b) ${\displaystyle \frac{x(x-1)}{2}}$ 條。

(a) BFS：以 Queue 逐層向外，先拜訪距起點 1 步的所有鄰居，再拜訪 2 步者。例：$A\to B\to C\to D\to E\to F$。（如簡答圖）

(b) DFS：以 Stack 或遞迴沿一條路徑深入，無法前進才回溯。例：$A\to B\to D\to E\to C\to F$。

碰撞（collision）：不同資料算出相同的 128-bit 摘要。輸出空間固定，資料量大時碰撞機率上升，且 MD5 已可實際構造碰撞，攻擊者能偽造摘要相同、內容不同的文件，破壞完整性驗證與數位簽章。

(a) pivot 取最後一個元素：pivot 86 → 75, 40, 61, 23, 54, 12, 86, 98；pivot 12 → 12, 40, 61, 23, 54, 75；pivot 75 不動；pivot 54 → 12, 40, 23, 54, 61；pivot 23 → 12, 23, 40；結果：12, 23, 40, 54, 61, 75, 86, 98。

(b)

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a; *a = *b; *b = t;
}

/* Lomuto partition：以最後一個元素為 pivot */
int partition(int arr[], int low, int high) {
    int pivot = arr[high];      /* 選最後一個元素當 pivot */
    int i = low - 1;            /* i：「<= pivot」區的右邊界 */
    int j;
    for (j = low; j < high; j++)
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);   /* 把小的換到左側 */
        }
    swap(&arr[i + 1], &arr[high]);    /* pivot 歸位 */
    return i + 1;                     /* 回傳 pivot 的最終 index */
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {                 /* 區間 <= 1 個元素即終止 */
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);  /* 遞迴左半 */
        quickSort(arr, pi + 1, high); /* 遞迴右半 */
    }
}

int main(void) {
    int arr[] = {75, 40, 61, 23, 54, 12, 98, 86};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i;
    quickSort(arr, 0, n - 1);
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}