陣列（array）與鏈結串列（linked list）皆可用來實作一已知長度序列的插入排序法（insertion sort），且各有其優缺點。下列敘述何者錯誤？

Question

陣列（array）與鏈結串列（linked list）皆可用來實作一已知長度序列的插入排序法（insertion sort），且各有其優缺點。下列敘述何者錯誤？
(A) 陣列所需的記憶體較少
(B) 陣列較有利於搜尋某一元素是否存在一已排序之序列中
(C) 在插入一元素到已排序之序列中的某一位置時，鏈結串列所需的時間複雜度較低
(D) 在最差的情形（worst case）下，鏈結串列所需的時間複雜度較低

Accepted Answer

正確答案為 D。 本題考查陣列與鏈結串列實作插入排序法的差異。選項D錯誤，因最差情況下兩者時間複雜度皆為O(n²)，鏈結串列並未較低。 (A) 【記憶體開銷】陣列僅儲存資料本身，不需額外指標欄位；鏈結串列每個節點需額外儲存next指標，故陣列所需記憶體較少，敘述正確。 (B) 【搜尋效率】陣列支援隨機存取（random access），已排序序列可用二元搜尋O(log n)；鏈結串列僅能循序走訪O(n)，故陣列較有利，敘述正確。

陣列（array）與鏈結串列（linked list）皆可用來實作一已知長度序列的插入排序法（insertion sort），且各有其優缺點。下列敘述何者錯誤？

逐選項解析

立即註冊,看完整詳解

計算機概要相關題目

想練更多計算機概要考古題？

陣列（array）與鏈結串列（linked list）皆可用來實作一已知長度序列的插入排序法（insertion sort），且各有其優缺點。下列敘述何者錯誤？

逐選項解析

立即註冊,看完整詳解

計算機概要 相關題目

想練更多計算機概要考古題？

計算機概要相關題目