中六ICT｜數據結構：陣列、連結串列、堆疊、佇列、樹與圖

數據結構是中六 ICT 把「資料怎樣放」與「程式怎樣跑得快」連起來的一章。同一個問題，用陣列與用連結串列去解，寫法可以一樣，但執行時間與記憶體相差幾十倍。這一章考的不是背名稱，而是用操作次數說明為甚麼某個結構在某個情境較快。

這一章考甚麼

• 線性結構：陣列索引由 0 起、記憶體連續；連結串列以指標串連，隨機存取要逐個走，但頭部插入只需改一條指標。
• 受限線性結構：堆疊後進先出，用於撤銷、括號配對與深度優先搜尋；佇列先進先出，用於打印機排隊與廣度優先搜尋。
• 樹：二元搜尋樹的左子樹全部小於根、右子樹全部大於根，所以中序遍歷必得升序；第 n 層最多 2 的 n−1 次方個節點，n 層滿樹共 2 的 n 次方減 1 個。
• 圖：鄰接矩陣佔 n × n 格，查詢快但稀疏圖浪費；鄰接表佔 2E 條記錄（無向圖），省記憶體但要逐條找。

三條主線

第一條是次序：LIFO 與 FIFO 不是習慣，而是由出入口數目決定——堆疊只有一個口，所以後入先出；佇列一進一出，所以先入先出。第二條是成本：任何操作都問三個數字——要搬幾多個元素、要走幾多個節點、要比較幾多次。第三條是退化：有序資料插入二元搜尋樹會退化成鏈，高度由 log n 變成 n，1 000 個節點的最差搜尋由 10 次變成 1 000 次。

做題時養成三個動作：先寫出資料的實際狀態（push、pop 之後剩下甚麼），再把 Big-O 換成具體次數（n = 1 000 時 O(n²) 是一百萬、O(n log n) 約一萬），最後檢查單位——矩陣問「格」、鄰接表問「條記錄」、佇列問「個元素」，三者不能混。

常見失分

• 把陣列索引當由 1 起，於是把 5 個元素的最大索引寫成 5。
• 混淆 LIFO 與 FIFO，把堆疊說成先進先出。
• 以為環形佇列的元素數是 rear 減 front，忘記加 1。
• 只寫「連結串列較快」而沒有說明是頭部插入 O(1)、隨機存取 O(n)。

練習與答案

下面三份練習按難度遞進，每份 10 題，附答案與一句解說，數值全部由程式計算核對，適合作為課堂後的獨立練習或導師備課材料。

想找導師跟進這一章？按此登記，我們會按學生的學校進度配對導師。

常見問題

問：為甚麼二分搜索一定要已排序？
答：二分搜索靠「中間值大於目標就丟右半」這個判斷，若資料未排序，被丟的一半可能含有答案，結果會漏找。

問：鄰接矩陣與鄰接表應該怎樣選？
答：看圖的稠密程度。100 個頂點、300 條邊的圖，矩陣要 10 000 格而鄰接表只需 600 條記錄，稀疏圖用鄰接表明顯省位。