申論題 - 阿摩線上測驗

申論題資訊

試卷：107年 - 107 地方政府特種考試_四等_統計、資訊處理：資料處理概要#73340
科目：資料處理
年份：107年
排序：0

一、佇列（queue）和堆疊（stack）是二種常用的資料結構。請回答下列問題。

⑴若要用深度優先的方式（depth-first search）走訪一樹狀結構（tree structure）的所有節點（node），請問佇列和堆疊，何者較適合？並說明原因。（10 分）

詳解提供者：hchungw

深度優先的特性：
- 深度優先搜索需要先走訪一條路徑到底，然後回溯並繼續走訪其他路徑。這種先深入再回溯的特性與堆疊的後進先出（LIFO，Last In First Out）特性非常匹配。
堆疊的運作機制：
- 當走訪到一個節點時，將其相鄰的節點（子節點）依次壓入堆疊中。
- 每次從堆疊中彈出最上面的節點進行走訪，然後繼續將這個節點的子節點壓入堆疊。
- 這樣的過程保證了每次總是先走訪最新加入堆疊的節點，即先走訪深入的節點，符合深度優先的需求。

初始化：
- 將根節點（root node）壓入堆疊。
重複以下步驟直到堆疊為空：
- 從堆疊中彈出一個節點，進行處理（例如打印節點值）。
- 將這個節點的子節點依次壓入堆疊（通常從右到左壓入，確保左子節點先被處理）。

堆疊（stack）因其後進先出的特性，非常適合用來實現深度優先搜索（DFS），而佇列（queue）則更適合廣度優先搜索（BFS）。

詳解提供者：114年高考上榜

若要用深度優先的方式走訪一樹狀結構的所有節點，堆疊（stack）是比較適合的資料結構。在深度優先搜尋中，我們先從根節點開始，遍歷其所有子節點，再往下一層遍歷，直到搜尋到樹的底部。當遍歷某個節點時，我們會先遍歷其左子節點，再遍歷右子節點。這種遍歷方式是使用堆疊可以比較方便地實現。

具體來說，我們可以使用一個堆疊來存儲要遍歷的節點。每次遍歷一個節點時，我們把該節點的右子節點和左子節點（如果有的話）按照相反的順序壓入堆疊中，這樣可以保證下一個被遍歷的節點是左子節點（因為堆疊是後進先出的）。當堆疊為空時，表示搜尋完成。