Q117.
圖形(Graph)的深度優先搜尋(Depth First Search)中，下面那一種資料結構可用於暫存已拜訪過(Visited)的節點？
電腦軟體設計共同科目 · 乙級 · Q117
難易度分析
2 / 5
本題屬於基礎概念定義的記憶型問題，僅需掌握特定搜尋演算法與其對應輔助資料結構的單一對應關係即可解答。
正確答案：②堆疊(Stack)
② 堆疊(Stack):堆疊(Stack) 採用 LIFO(後進先出) 原則，符合 DFS 沿著路徑深入到底後再回溯 的搜尋策略。遞迴呼叫本身就是利用 系統呼叫堆疊(Call Stack) 來實現 DFS 的節點拜訪記錄。
錯誤選項解析
- ① 佇列(Queue):佇列(Queue) 採用 FIFO(先進先出) 原則，適用於 廣度優先搜尋(BFS) 的節點暫存，而非深度優先搜尋。DFS 需要後進先出的特性來實現回溯機制。
- ③ 堆積(Heap):堆積(Heap) 是一種滿足 堆積性質(父節點優先於子節點) 的完全二元樹，主要用於 優先佇列(Priority Queue) 與 堆積排序(Heap Sort)，與圖形遍歷的節點暫存無關。
- ④ 二元樹(Binary Tree):二元樹(Binary Tree) 本身是一種 非線性資料結構，用於表示具有階層關係的資料，並非用來暫存已拜訪節點的輔助結構。DFS 遍歷圖形時需搭配堆疊使用。
Learning Tip
"DFS 與 BFS 的資料結構選擇 是資料結構常考核心：DFS 使用 堆疊(Stack) 或 遞迴，BFS 使用 佇列(Queue)。考試常將兩者混淆出題，務必記住「深堆廣佇」口訣。另外需注意，實際實作 DFS 時還需搭配 Visited 陣列 避免重複拜訪同一節點，尤其在處理 有環路圖形 時更為關鍵。"
學員答題分佈
①佇列(Queue)0%
②堆疊(Stack)0%
③堆積(Heap)0%
④二元樹(Binary Tree)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！