調查局三等申論題
112年
[電子科學組] 計算機概論
第 一 題
📖 題組：
五、T 為一二元樹（Binary Tree），可以是空的或是每一個節點儲存著一個數值且與其他節點的數值不重複。假設 T 起始為空的，即 T = null。樹中節點（node）的定義如下： struct node{ int data; struct node *l_link, *r_link; } 請回答下列問題：
五、T 為一二元樹（Binary Tree），可以是空的或是每一個節點儲存著一個數值且與其他節點的數值不重複。假設 T 起始為空的，即 T = null。樹中節點（node）的定義如下： struct node{ int data; struct node *l_link, *r_link; } 請回答下列問題：
📝 此題為申論題，共 4 小題
小題 (一)
插入一節點其 data 欄位為 value 的演算法如下：
Procedure Insert(T, value)
Begin
If(T == null)
建立一個新節點，並將data欄位設為value;
Elseif(T->data > value)
Insert(T->l_link, value);
Else
Insert(T->r_link, value);
Endif
End
請根據以上插入節點的演算法依序插入節點，其值分別為：23，56，12，19，42，4，98，36。請以圖示的方式呈現完整的插入過程。（10 分）
思路引導 VIP
分析給定的演算法可知，此為建立「二元搜尋樹（Binary Search Tree, BST）」的過程：小於目前節點值往左子樹、大於等於則往右子樹。解題時應依序讀取數值，從根節點向下比較尋找空位插入，並將每一步的樹狀結構變化畫出，以符合題目『圖示呈現完整插入過程』的要求。
小題 (二)
請設計一演算法以在樹中搜尋一給定鍵值（key），如：Search（T, key）。若 key 存在 T 中，回傳“found”；若 key 不存在 T 中，回傳“not found”。（10 分）
思路引導 VIP
首先辨明題目給定的資料結構是『一般二元樹（Binary Tree）』而非『二元搜尋樹（BST）』，因此無法透過節點值的大小比較來縮減搜尋方向。考生應立即聯想到必須採用『完整的樹狀遍歷（Tree Traversal）』策略。建議採用基於遞迴的深度優先搜尋（DFS），邏輯清晰且易於實作，並切記處理節點為空（NULL）的邊界條件。
小題 (三)
若 T 中有 n 個節點。最糟的情況下，需要搜尋幾次？（5 分）
思路引導 VIP
看到此題應立刻聯想「二元樹的極端樹型與時間複雜度之關係」。最糟情況發生在樹失去平衡、退化成「歪斜二元樹（Skewed Tree）」時，應將其視同單向鏈結串列進行推導。
小題 (四)
承第(三)子題，此最糟的情況是什麼？請舉例說明。（5 分）
思路引導 VIP
看到「二元樹操作的最糟情況」，應立刻聯想到未經平衡處理的二元搜尋樹（BST）退化為「偏斜樹（Skewed Tree）」的現象。解題重點在於指出特定的資料輸入順序（完全遞增或遞減）會導致樹狀結構退化為線性鏈結串列，並舉出明確的數列與結構推演作為實例佐證。