民國110年 第2梯次 電腦軟體設計(C++)乙級 學科
第54題
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
題目
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
- (1) θ(n log n)
- (2) θ(log n)
- (3) θ(1)
- (4) θ(n)
官方答案
(4) θ(n)
解析
從含 n 個節點的鏈結串列刪除值為 x 的節點，需先從表頭逐一走訪比對，最壞情況該節點位於串列末端或不存在，必須檢查全部 n 個節點，搜尋時間 θ(n)；找到後修改指標刪除僅需 θ(1)。整體由搜尋主導，故最壞情況時間複雜度為 θ(n)。選項 θ(1) 僅適用於已知節點位置，θ(log n)、θ(n log n) 不適用於線性串列，故選 4。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。