時間複雜度與排序演算法中，快速排序（Quick Sort）的最差狀況與穩定性考點為何？

快速排序最差狀況時間複雜度為平方階，且屬於不穩定排序。 * 最差狀況之成因：當原始資料已經是「完全正序」或「完全逆序」，且基準點（Pivot）不幸都選到最左端或最右端的極端值時，快速排序會退化成類似泡沫排序的行為。此時時間複雜度會從平均的 $O(N \log N)$ 暴跌至最差的 O(N²)。解決方法是採取三數取中法來挑選基準點。 * 穩定性（Stability）定性：快速排序屬於「不穩定排序」。這代表當原始資料中存在兩個數值相同的元素時，經過快速排序之後，這兩個元素的相對先後順序可能會被對調。考場上常考的其餘不穩定排序還包括：堆積排序（Heap Sort）與選擇排序（Selection Sort）。

二元搜尋樹（BST）、平衡二元樹（AVL）與堆積（Heap），在結構與搜尋效率上有何根本差異？

二元搜尋樹左小右大用於高速搜尋，平衡二元樹防範退化，堆積則是完全二元樹用於求極值。 * 二元搜尋樹（BST）：規則為「左子樹節點小於根節點，右子樹節點大於根節點」。其優點是平均搜尋只需要 $O(\log N)$。但致命缺點是如果依序輸入遞增數值，樹狀結構會退化成一條直線（如鏈結串列），搜尋複雜度退化成 O(N)。 * 平衡二元樹（AVL Tree / 紅黑樹）：為了解決 BST 的退化問題。AVL 樹嚴格限制左右子樹的高度差絕對不能超過一，一旦超過就會透過「單旋轉或雙旋轉（LL, RR, LR, RL）」進行結構重組。這能強迫維持樹的高度在 $\log N$，確保不論任何極端狀況下，搜尋時間必定維持在最穩定的 $O(\log N)$。 * 堆積（Heap）：屬於一種完全二元樹（Complete Binary Tree）。其規則與 BST 完全不同，分為最大堆積（根節點大於等於子節點）與最小堆積。堆積不具備左小右大的搜尋順序，它的核心功能是讓大腦能在 O(1) 的極速時間內直接抓出全系統的最大值或最小值，常應用於優先佇列（Priority Queue）與戴克斯特拉演算法中。

圖形走訪中，深先搜尋（DFS）與廣先搜尋（BFS）所使用的資料結構與應用有何不同？

DFS 使用堆疊（或遞迴），BFS 使用佇列。DFS 用於拓撲排序，BFS 用於找無權重圖的最短路徑。走訪圖形（Graph）時，依據探索節點的策略不同，在記憶體行為與應用上徹底截斷： * 深度優先搜尋（DFS）：策略是一條路走到黑，遇到死胡同再回溯。在程式實作上，必須利用「堆疊（Stack）」來記錄走訪路徑，或直接寫成遞迴函式。DFS 在資訊處理的經典應用包括：尋找圖形的連通元件、偵測是否有環路、以及進行「拓撲排序（Topological Sort）」。 * 廣度優先搜尋（BFS）：策略是像同心圓一樣，先將鄰近的第一層節點全部掃描完，再往下一層推進。在程式實作上，必須利用「佇列（Queue）」來記錄等待探索的節點，遵循先進先出的原則。BFS 最核心的應用，就是在所有邊權重皆相同的圖形中，能夠最快找出兩點之間的「最短路徑（Shortest Path）」。

資料結構｜完整考科介紹、準備方向與適用考試｜大東海雲端

Q: 圖形走訪中，深先搜尋（DFS）與廣先搜尋（BFS）所使用的資料結構與應用有何不同？

DFS 使用堆疊（或遞迴），BFS 使用佇列。DFS 用於拓撲排序，BFS 用於找無權重圖的最短路徑。 走訪圖形（Graph）時，依據探索節點的策略不同，在記憶體行為與應用上徹底截斷： * 深度優先搜尋（DFS）：策略是一條路走到黑，遇到死胡同再回溯。在程式實作上，必須利用「堆疊（Stack）」來記錄走訪路徑，或直接寫成遞迴函式。DFS 在資訊處理的經典應用包括：尋找圖形的連通元件、偵測是否有環路、以及進行「拓撲排序（Topological Sort）」。 * 廣度優先搜尋（BFS）：策略是像同心圓一樣，先將鄰近的第一層節點全部掃描完，再往下一層推進。在程式實作上，必須利用「佇列（Queue）」來記錄等待探索的節點，遵循先進先出的原則。BFS 最核心的應用，就是在所有邊權重皆相同的圖形中，能夠最快找出兩點之間的「最短路徑（Shortest Path）」。

01資料結構是什麼？

所謂資料結構，係指在電腦中以特定方式組織與儲存資料，使其能被有效存取與處理之學問。其內涵不僅包括各種資料儲存形式之設計，如陣列、堆疊、佇列及鏈結串列，亦涵蓋樹狀結構、圖形結構及其相關操作與應用，強調資料組織方式對運算效率之影響。其目的在於提升資料存取與運算效率，優化程式執行效能，並支援各類複雜資訊系統之設計與實作。

02資料結構命題大綱

高考考試、各類(三等)特考的資料結構之命題大綱：
資料結構基礎
演算法與效率分析(algorithm and performance analysis)
陣列(arrays)、指標概念(pointers)與字串處理(string manipulation)
遞迴(recursion)
堆疊(stacks)、佇列(queues)與串列(lists)
樹狀結構(trees)及其應用
包括二元樹(binary trees)、m 路樹(m-way trees)與查找樹(tries)等
圖(graphs)及其應用
包括圖的表示方式與圖形演算法(graph algorithms)
排序與搜尋
排序演算法(sorting algorithms)
搜尋演算法(searching algorithms)
雜湊(hashing)
優先佇列(priority queues)
綜合應用
外部儲存的資料處理(processing data in external storage)
資料壓縮(data compression)
選擇適當資料結構的策略

06資料結構準備方法

●建立（複雜度與排序性能）的不倒翁核心對照表：

資料結構有高達 30% 的基本分數落在一眼定生死的表格題。強烈建議在複習初期，就自己動手整理一張包含（泡沫、選擇、插入、快速、合併、堆積、基數排序）的橫向對照表，橫軸包含：最好/最壞/平均時間複雜度、空間複雜度、是否為穩定排序（Stability）。考前一個月每天默寫一遍，確保在考場上能瞬間秒殺這類題型。

●拒絕(唯讀主義），每一棵樹與圖形都要動手畫過：

資料結構是一門幾何視覺感極強的學門。看課本上的 AVL 樹旋轉、Heap 調整、B 樹分裂時，用眼睛看都會覺得理所當然，但在考場的高壓環境下，沒有親手畫過的人極易發生（轉錯方向）或（漏掉子樹鏈結）的慘劇。平時練習歷屆試題時，務必拿原子筆一動一動在草稿紙上把樹狀圖的變化（刻）出來。

●將四大核心資料結構的常考程式碼練到（盲寫）：

雖然有專門的程式設計考科，但（資料結構）考科中一樣會出現 25~50 分的手寫程式題。備考時，應準備一個（核心程式口袋清單），將：(1) 單向鏈結串列的反轉（Reverse）；(2) 二元搜尋樹的插入與刪除節點；(3) 二元樹的前/中/後序遞迴走訪；(4) 堆疊的 Push 與 Pop 操作，這四類的程式碼（或虛擬碼）背到能一字不漏地在白紙上默寫出來。只要基礎模板穩固，遇到變形題也能輕鬆修改拿分。

●利用歷屆試題進行（解題步驟模組化訓練）：

資料結構的題型重複率非常高（特別是 Dijkstra 最短路徑、Kruskal/Prim 最小生成樹、中序轉後序、AVL旋轉）。務必將近 5 到 10 年高考三級、地方特考三等、關務特考、調查特考等所有資訊類科的（資料結構）考古題完整刷過 3 遍以上。答題時採用 （標題化（明確列出當前步驟）→圖表化（繪製出清晰的矩陣表或樹狀圖）→結論化（清楚寫出最終答案，如總權重或走訪序列）） 的三部曲結構，最能拿到閱卷委員的滿分評價。

網站導覽

資料結構｜完整考科介紹、準備方向與適用考試

一分鐘看懂資料結構

01資料結構是什麼？

02資料結構命題大綱

03資料結構考試範圍

04資料結構考試重點

05資料結構常見題型

06資料結構準備方法

07常見問題

一分鐘看懂資料結構

01資料結構是什麼？

02資料結構命題大綱

03資料結構考試範圍

04資料結構考試重點

05資料結構常見題型

06資料結構準備方法

07常見問題

Q時間複雜度與排序演算法中，快速排序（Quick Sort）的最差狀況與穩定性考點為何？

Q二元搜尋樹（BST）、平衡二元樹（AVL）與堆積（Heap），在結構與搜尋效率上有何根本差異？

Q圖形走訪中，深先搜尋（DFS）與廣先搜尋（BFS）所使用的資料結構與應用有何不同？