高考申論題
105年
[資訊處理] 資料結構
第 一 題
📖 題組：
假設一個無向圖（undirected graph）的邊（edges）如下： S, T S, Z T, Y T, Z V, Y V, Z Y, Z
假設一個無向圖（undirected graph）的邊（edges）如下： S, T S, Z T, Y T, Z V, Y V, Z Y, Z
📝 此題為申論題，共 2 小題
小題 (一)
使用堆疊（stack），從 S 開始，進行深度優先走訪（depth-first traversal），請寫出走訪結果。（10 分）
思路引導 VIP
看到深度優先走訪（DFS），首先要想到使用「堆疊（Stack）」的後進先出（LIFO）特性。由於題目未規定相鄰節點的走訪優先順序，解題時應主動宣告「遇到多個相鄰節點時，依字母順序優先走訪」，並逐步畫出堆疊推入與彈出的狀態變化，以展現嚴謹的邏輯推演。
小題 (二)
使用佇列（queue），從 S 開始，進行廣度優先走訪（breadth-first traversal），請寫出走訪結果。（10 分）
思路引導 VIP
面對圖的走訪題型，首先應將邊的集合轉換為相鄰串列（Adjacency List）或畫出無向圖。接著確立 BFS 演算法的核心是使用「佇列（Queue）」遵循先進先出（FIFO）原則；為確保解答唯一性，建議在答題時主動宣告「相鄰節點依英文字母順序加入佇列」，並詳細列出每一步驟的 Queue 狀態與走訪結果以獲取完整過程分。