調查局四等申論題
106年
[電子科學組] 計算機概要
第 一 題
📖 題組:
請解釋下列名詞,並分別舉例劃出一棵高度為3的樹:(每小題5分,共15分)
請解釋下列名詞,並分別舉例劃出一棵高度為3的樹:(每小題5分,共15分)
📝 此題為申論題,共 3 小題
小題 (一)
complete binary tree
思路引導 VIP
看到「complete binary tree」,首先要聯想到兩個核心條件:「除最底層外皆須填滿」以及「最底層節點一律靠左連續排列」。接著需注意「高度(Height)」的定義可能存在分歧,作答時建議先定義基準(例如標明邊數或層數),再繪出符合條件且層次分明的樹狀圖以確保拿分。
小題 (二)
max heap
思路引導 VIP
看到「max heap」,首先要聯想到它的兩大核心特性:「完全二元樹(Complete Binary Tree)」的結構限制,以及「父節點值大於或等於子節點值」的數值關係。繪製實例時,需特別注意題目限制的「高度為3」,確保階層數正確,且最後一層的節點必須嚴格由左至右填滿。
小題 (三)
binary search tree
思路引導 VIP
看到「二元搜尋樹 (BST)」,應立刻聯想到其核心定義:二元樹結構且節點值滿足「左子樹 < 根節點 < 右子樹」。作圖時務必確認數值符合此規則,並針對「高度為3」的限制,在圖旁註明高度的計算基準(例如根節點層級為1,最大層級為3)以避免學術定義分歧造成的失分。
完整二元樹定義與結構
💡 結構須由上至下、由左至右填滿,底層節點須連續靠左。
| 比較維度 | 完整二元樹 (Complete) | VS | 完美二元樹 (Perfect) |
|---|---|---|---|
| 填滿程度 | 除底層外全滿 | — | 所有層級皆全滿 |
| 底層排列 | 必須靠左連續 | — | 全部填滿無須排列 |
| 節點總數 | 2^h 至 2^(h+1)-1 | — | 固定為 2^(h+1)-1 |
💬完美二元樹是完整二元樹的一種特例,所有完整二元樹不一定是完美二元樹。