高考申論題
106年
[資訊處理] 資料結構
第 二 題
📖 題組：
給定如下圖所示之兩個環狀單向鏈結串列（circular singly linked list），並以 A，B 分別指向其中兩個串列中的一個節點，另有一個指標 C 可以使用。請用類 C 之虛擬語言（C-like pseudo code）完成下列動作。 (一)請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分） (二)請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10 分） (三)請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15 分）
給定如下圖所示之兩個環狀單向鏈結串列（circular singly linked list），並以 A，B 分別指向其中兩個串列中的一個節點，另有一個指標 C 可以使用。請用類 C 之虛擬語言（C-like pseudo code）完成下列動作。 (一)請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分） (二)請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10 分） (三)請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15 分）
📝 此題為申論題，共 3 小題
小題 (二)
請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10 分）
思路引導 VIP
解決環狀單向串列的 O(1) 合併問題，核心在於「交叉連接」。透過交換 A->link 與 B->link，即可將 B 串列完美嵌入 A 串列中。配合題目提示「有指標 C 可以使用」，利用 C 作為暫存變數，並運用逗號運算子將敘述壓縮至兩行內。
小題 (一)
請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分）
思路引導 VIP
在單向鏈結串列中刪除節點的關鍵，是必須掌握欲刪除節點的「前驅節點（previous node）」。觀察圖示可知，指標 A 恰好指向指標 C 的前驅節點，因此只需修改 A 的指標欄位跳過 C，再將 C 的記憶體釋放即可。
小題 (三)
請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15 分）
思路引導 VIP
本題考查單向鏈結串列的經典 O(1) 插入技巧（Value Swapping）。由於單向串列無法直接取得節點的前驅，要在節點 A 之前插入節點 B，必須先將 B 插入到 A 的『後方』，再『交換兩者的資料』，即可在邏輯上達成前插的效果並維持環狀。