高考申論題
112年
[電力工程] 計算機概論
第 一 題
📖 題組：
三、陣列與二元樹是撰寫程式常用的資料結構。 | 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 鍵值 | 18 | 10 | 21 | | 15 | | 23 | | | 13 | 17 | | | | 25 |
三、陣列與二元樹是撰寫程式常用的資料結構。 | 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 鍵值 | 18 | 10 | 21 | | 15 | | 23 | | | 13 | 17 | | | | 25 |
📝 此題為申論題，共 2 小題
小題 (一)
使用陣列（Array）結構儲存二元樹（Binary Tree）有何優點？（10分）
思路引導 VIP
本題詢問陣列表現二元樹的優點。應先想到陣列表示法的運作原理：對於索引 i 的節點，其左子節點為 2i+1，右子節點為 2i+2，父節點為 (i-1)/2。從這點出發，推導出它的優點：不需要指標（Pointer）、節省空間（若為完整或完滿二元樹）、透過公式隨機存取速度極快。若篇幅允許，可稍微提一下缺點（歪斜樹浪費空間）作為對比以顯全面。
小題 (二)
下面陣列Arr[0:14]表示一棵二元樹，陣列的元素代表該樹每個節點的鍵值，請撰寫一個演算法重建出該二元樹。該樹是否為一棵二元搜尋樹（Binary Search Tree）？（15分）
思路引導 VIP
本題需要完成兩項任務。第一：撰寫演算法。由於已經給定陣列，可以使用遞迴方式建立節點，建立根節點後，遞迴呼叫 2i+1 建左子樹，2i+2 建右子樹。可以使用 C 語言或 Pseudo-code。第二：判斷是否為 BST。首先要先畫出樹的形狀：根為18，左子為10，右子為21。10的右子為15，15的左子13，右子17。21的右子為23，23的右子為25。畫完後，檢驗是否滿足「左子樹所有節點 < 父節點 < 右子樹所有節點」的特性。也可說明若將此樹進行中序追蹤（In-order Traversal），是否產生嚴格遞增數列。判斷結果為「是」。