地特三等申論題
106年
[資訊處理] 資料結構
第 一 題
📖 題組：
下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下（average case），搜尋（search）、插入（insertion）、刪除（deletion）資料之時間複雜度。陣列的各項資料已事先填入作為範例。（每小題 5 分，共 20 分） | | 搜尋(search) | 插入(insertion) | 刪除(deletion) | | :--- | :---: | :---: | :---: | | 陣列 | O(n) | O(n) | O(n) | | (一)佇列（queue） | | | | | (二)雙向連結串列（doubly-linked list） | | | | | (三)二元搜尋樹（binary search tree） | | | | | (四)AVL樹（AVL tree） | | | |
下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下（average case），搜尋（search）、插入（insertion）、刪除（deletion）資料之時間複雜度。陣列的各項資料已事先填入作為範例。（每小題 5 分，共 20 分） | | 搜尋(search) | 插入(insertion) | 刪除(deletion) | | :--- | :---: | :---: | :---: | | 陣列 | O(n) | O(n) | O(n) | | (一)佇列（queue） | | | | | (二)雙向連結串列（doubly-linked list） | | | | | (三)二元搜尋樹（binary search tree） | | | | | (四)AVL樹（AVL tree） | | | |
📝 此題為申論題，共 4 小題
小題 (一)
佇列（queue）
思路引導 VIP
思考佇列（Queue）的「先進先出（FIFO）」特性與操作限制：插入（enqueue）只能在尾端、刪除（dequeue）只能在前端。因為不支援隨機存取，搜尋必須線性走訪所有元素。
小題 (二)
雙向連結串列（doubly-linked list）
思路引導 VIP
思考雙向連結串列（Doubly-linked list）的資料儲存特性：其記憶體位置不連續，因此無法隨機存取，必須循序搜尋。但優勢在於，只要掌握了目標節點的指標，其插入與刪除都只需修改相鄰節點的指標，無須像陣列一樣搬移大量資料。
小題 (三)
二元搜尋樹（binary search tree）
思路引導 VIP
看到二元搜尋樹（BST），應先思考其核心特性與樹高（height）的關係。在「一般狀況（average case）」下，樹的結構大致平衡，樹高約為 O(log n)；而搜尋、插入、刪除三種操作的執行時間皆與樹高成正比，故皆為 O(log n)。
小題 (四)
AVL樹（AVL tree）
思路引導 VIP
看到 AVL 樹，首先要想到它是「高度平衡的二元搜尋樹」，其核心特性是透過旋轉操作保證樹的高度永遠維持在 O(log n)。因此，無論是尋找節點，或是插入、刪除後的重整，其平均與最差時間複雜度皆被嚴格限制在 O(log n)。