地特三等申論題
109年
[電力工程] 計算機概論
第 一 題
📖 題組：
請回答下列問題：（每小題6分，共24分） (一)請問下列遞迴（recursive）演算法的解為何？ T(n) = 2 if n = 2, T(n) = 2T(n/2) + n if n = 2^k, for k > 1 (二)請畫出將2、1、4、5、9、3、6、7插入最初為空的 AVL 樹中的結果。 (三)在下圖的展開樹（splay tree）中，請畫出用鍵值（key）6刪除元素（deleting the element）的結果。 (四)請畫出使用線性時間演算法（linear time algorithm），將10、12、1、14、6、5、8、15、3、9、7、4、11、13和2，來建立二元堆積（binary heap）的結果。
請回答下列問題：（每小題6分，共24分） (一)請問下列遞迴（recursive）演算法的解為何？ T(n) = 2 if n = 2, T(n) = 2T(n/2) + n if n = 2^k, for k > 1 (二)請畫出將2、1、4、5、9、3、6、7插入最初為空的 AVL 樹中的結果。 (三)在下圖的展開樹（splay tree）中，請畫出用鍵值（key）6刪除元素（deleting the element）的結果。 (四)請畫出使用線性時間演算法（linear time algorithm），將10、12、1、14、6、5、8、15、3、9、7、4、11、13和2，來建立二元堆積（binary heap）的結果。
📝 此題為申論題，共 4 小題
小題 (一)
請問下列遞迴（recursive）演算法的解為何？
T(n) = 2 if n = 2,
T(n) = 2T(n/2) + n if n = 2^k, for k > 1
思路引導 VIP
看到遞迴方程式求解，應立即想到可使用「主定理（Master Theorem）」來快速判斷時間複雜度，但若需寫出精確解，則建議使用「疊代法（Telescoping）」或「代入法」將遞迴式展開，找出一般規律並推導至邊界條件。
小題 (二)
請畫出將2、1、4、5、9、3、6、7插入最初為空的 AVL 樹中的結果。
思路引導 VIP
面對 AVL 樹（高度平衡二元搜尋樹）的建構題，首先需銘記其核心定義：『任何節點的左右子樹高度差（平衡因子, Balance Factor）絕對值不得大於 1』。解題策略為逐一插入節點，每次插入後務必『由下往上』檢查祖先節點的平衡因子；一旦發現失衡，立即根據失衡路徑判定屬於 LL、RR、LR 或 RL 型態，並執行對應的旋轉（Rotation）操作恢復平衡後，再繼續插入下一個節點。
小題 (三)
在下圖的展開樹（splay tree）中，請畫出用鍵值（key）6刪除元素（deleting the element）的結果。
思路引導 VIP
Splay Tree（展開樹）的刪除操作需遵循四個步驟：(1)將目標節點Splay至根節點；(2)移除根節點並分成左右子樹；(3)將左子樹的最大節點Splay至左子樹的根；(4)將右子樹接至新根節點的右側。本題核心在於準確執行Zig-Zag與Zig旋轉，維持二元搜尋樹的性質。
小題 (四)
請畫出使用線性時間演算法（linear time algorithm），將10、12、1、14、6、5、8、15、3、9、7、4、11、13和2，來建立二元堆積（binary heap）的結果。
思路引導 VIP
看到「線性時間演算法建立二元堆積（Build-Heap）」，應立刻想到「由下而上（Bottom-up）」的建堆積方法。從最後一個非葉節點（索引 ⌊n/2⌋）開始，依次向根節點反向執行 Sift-Down（向下篩選）操作，將每個子樹調整為合法堆積。此題未指定最大或最小堆積，作答時建議明示假設或兩者皆列出以確保完整得分。