民國111年 第2梯次 電腦軟體設計(C++)乙級 學科
第7題
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
題目
從一個擁有n 個節點的鏈結串列刪除一個值為x 之節點,在最壞情況下所需時間複雜度為多少?
- (1) θ(1)
- (2) θ(n)
- (3) θ(n log n)
- (4) θ(log n)
官方答案
(2) θ(n)
解析
單向鏈結串列不支援以索引直接定位，刪除值為 x 的節點時必須從頭節點開始逐一比對，並保留前一個節點的指標以便改接。最壞情況是 x 位於串列尾端或根本不存在，需走訪全部 n 個節點，故時間複雜度為 θ(n)。θ(1) 只有在已持有前驅節點指標時才成立；θ(log n) 與 θ(n log n) 需要額外的有序結構或排序，並非一般鏈結串列刪除節點的成本。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。