Q19.
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點，在最壞情況下所需時間複雜度為多少？
電腦軟體設計共同科目 · 乙級 · Q19
難易度分析
2 / 5
本題屬於基礎概念考查，要求考生能正確區分不同資料結構在特定操作下的時間複雜度，只要掌握鏈結串列的基本特性即可得出結論。
正確答案：④θ(n)
④ θ(n):θ(n) 為正確答案。在單向鏈結串列中刪除指定值的節點，最壞情況下目標節點位於串列尾端或不存在，必須逐一巡覽全部 n 個節點進行比對，故時間複雜度為線性時間 θ(n)。
錯誤選項解析
- ① θ(1):θ(1) 表示常數時間，僅在已直接持有目標節點指標且無需搜尋的情況下才成立。本題需從鏈結串列頭節點開始逐一比對尋找值為 x 的節點，無法達到常數時間。
- ② θ(log n):θ(log n) 是二元搜尋法在有序陣列上的時間複雜度。鏈結串列不支援隨機存取，無法以索引直接定位中間元素，因此不適用對數時間複雜度。
- ③ θ(n log n):θ(n log n) 是合併排序或快速排序等高效排序演算法的時間複雜度。刪除單一節點僅需線性搜尋，遠低於此複雜度層級。
Learning Tip
"本題核心考點為鏈結串列的搜尋特性。鏈結串列僅支援循序存取，任何涉及「尋找特定值」的操作在最壞情況下均需 θ(n) 時間。常考陷阱是與陣列或二元搜尋樹的時間複雜度混淆：陣列可依索引 θ(1) 存取但搜尋仍為 θ(n)；二元搜尋樹在平衡狀態下搜尋為 θ(log n)。實務上若需頻繁執行搜尋刪除操作，應考慮改用雜湊表或平衡二元搜尋樹等更高效的資料結構。"
學員答題分佈
①θ(1)0%
②θ(log n)0%
③θ(n log n)0%
④θ(n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！