調查局三等申論題
110年
[電子科學組] 計算機概論
第 一 題
📖 題組：
請回答下列問題：
請回答下列問題：
📝 此題為申論題，共 3 小題
小題 (一)
請寫出高度為 h 的 AVL 樹中最小節點數的精確表示式（precise expression）。（6 分）
思路引導 VIP
看到「AVL樹最小節點數」，應立刻聯想到「遞迴關係式」與「費氏數列（Fibonacci sequence）」。為了使節點數最少，左右子樹的高度差必須極大化（即相差 1），列出核心公式 N(h) = N(h-1) + N(h-2) + 1。作答時需明確標示高度 h 的起始基準點（h=0 或 h=1），並同時提供遞迴式與封閉通式以確保拿取滿分。
小題 (二)
請畫出將 10、12、1、14、6、5、8、15、3、9、7、4、11、13 和 2，一次一個插入到最初為空的二進位堆積（binary heap）中的結果。（8 分）
思路引導 VIP
解此類資料結構題，首要確認二元堆積的兩大屬性：結構性（完全二元樹）與偏序性（父節點恆大於/小於子節點）。由於題目未指明最大或最小堆積，建議以主流教材預設的 Max-Heap 進行完整推導，透過『插入至尾部後向上比較交換（Up-Heapify）』的標準操作逐一寫出演算過程，最後畫出完整的樹狀圖，並建議補充 Min-Heap 的最終結果以確保萬無一失。
小題 (三)
假設鏈結串列（linked list）與堆疊（stack）用 C 程式指標（pointer）來實現，請問鏈結串列與堆疊有何差異？（8 分）
思路引導 VIP
這題考查對資料結構本質的理解。考生應先點出兩者在計算機科學上的『層次差異』（基礎實體結構 vs 抽象資料型別），接著再具體從存取規則（LIFO）、C 指標操作邏輯（Top指標 vs Head指標）及實務應用場景進行對比分析，以展現觀念的深度。