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

Doubly Linked List。節點有 next 與 prev，Forward 與 Back 皆 $O(1)$；Singly Linked List 只能單向，Back 須從 head 重新走訪。

struct Node {
    int data;
    Node *prev, *next;
};

void insertAfter(Node* node, int data) {
    Node* p = new Node;
    p->data = data;
    p->prev = node;
    p->next = node->next;
    if (node->next) node->next->prev = p;  // 後方節點回指
    node->next = p;
}

Hash Table 以 URL 為 key、value 為指向 DLL 對應節點的指標，查詢平均 $O(1)$。DLL 依瀏覽時間先後串接節點（新頁面接在尾端），串列順序即瀏覽順序，Back／Forward 沿 prev／next 移動。

Preorder：50, 30, 20, 10, 40, 70, 60, 65, 85, 80。

Postorder：10, 20, 40, 30, 65, 60, 80, 85, 70, 50。

70 有兩個子節點，以右子樹最左節點（inorder successor）80 取代 70，原本的 80 是葉節點，直接移除。

（如簡答圖）

最終陣列：[5, 20, 8, 25, 40, 15, 12, 30, 35]。

Max-Heap L 存較小的一半，Min-Heap R 存較大的一半，維持 $0\le |L|-|R|\le 1$。

Insert(x)：$x\le L.\text{root}$（或 L 為空）放入 L，否則放入 R；兩堆大小差超過 1 時，把較大堆的 root 移到另一堆。

QueryMedian()：大小相等時取 $(L.\text{root}+R.\text{root})/2$，否則取較大堆的 root。

Insert $O(\log n)$，QueryMedian $O(1)$。

Circular Queue。front、rear 到達 N-1 後以 mod 繞回 0：

• 插入：array[rear] = data; rear = (rear+1) % N;
• 刪除：data = array[front]; front = (front+1) % N;

重複利用刪除釋出的空位，不需搬移，插入 $O(1)$；以犧牲一格（滿：(rear+1) % N == front）或維護 count 區分滿與空。

採用額外 count 變數的作法，不犧牲陣列格數：

int front = 0, rear = 0, count = 0;

bool Insert(int data) {
    if (count == N) return false;  // Queue Full
    array[rear] = data;
    rear = (rear + 1) % N;
    count++;
    return true;
}

bool Delete(int &data) {
    if (count == 0) return false;  // Queue Empty
    data = array[front];
    front = (front + 1) % N;
    count--;
    return true;
}

bool isPalindrome(char* S, int left, int right) {
    if (left >= right) return true;          // base case
    if (S[left] != S[right]) return false;   // 左右不匹配
    return isPalindrome(S, left + 1, right - 1);  // 往內遞迴
}

遞迴版：時間 $O(n)$，空間 $O(n)$（呼叫堆疊深度約 $n/2$）。迭代版：時間 $O(n)$，空間 $O(1)$。兩者時間相同，迭代版較省空間。

1. 在 $T$ 中以 BFS 或 DFS 找出 $u$ 到 $v$ 的唯一路徑。
2. 找出路徑上權重最大的邊 $e_{max}$。
3. 若 $w_{new}<weight(e_{max})$，移除 $e_{max}$、加入 $e_{new}$；否則 $T$ 不變。

時間 $O(V)$（$T$ 只有 $V-1$ 條邊，找路徑與掃最大邊各 $O(V)$）；空間 $O(V)$。

（如簡答圖）

30。root 30 的左子樹 size 為 4，名次 $r=4+1=5=k$，root 即為第 5 小。

Level 2 的 x，scope_level = 2，value = 5。

4 次（x = y + 1 與 y = x + 2 各 2 次；宣告不計入）。

(a) (a,1), (ee,2), (cc,2), (ccd,3), (cca,3), (abc,3), (dddd,4), (fffff,5)。

(b)

[0] → dddd
[1] → a → fffff
[2] → ee → cc
[3] → ccd → cca → abc

(c) （如簡答圖）插入 (2,2) 時於 (0,1) 做 RR 旋轉（左旋），為唯一一次旋轉。