2024安徽農商行秋季招聘計算機練習題（3）

　　下列對順序存儲的有序表（長度為 n）實現給定操作的算法中平均時間復雜度為 O（1）的是（ ）。

　　A.查找包含指定值元素的值

　　B.插入包含指定值元素的算法

　　C.刪除第 i 個元素的算法

　　D.獲取第 i 個值的算法













 

　　【答案】D

　　【考點】本題考查順序表的基本操作。

　　【解析】本題是針對順序有序表的基本操作。對于 A，若采用順序查找則平均時間復雜度為 O（n），若采用折半查找則平均時間復雜度為 O（logn），因此 A 錯誤。

　　對于 B，若要在順序有序表中插入指定值的元素，首先需要查找該值待插入的位置，之后再在該位置插入值。查找操作的時間復雜度如選項 A，插入操作由于需要移動待插入位置之后的所有元素，因此其時間復雜度為 O（n），綜上插入包含指定值元素的算法的平均時間復雜度為 O（n），因此 B 錯誤。

　　對于 C，刪除第 i 個元素需要將第 i 元素之后的所有元素向前移動一個單位，因此該刪除操作的平均時間復雜度為 O（n），因此 C 錯誤。

　　對于 D，順序表具有隨機存儲的特點，可以通過下標直接訪問該值，因此獲取第 i 個值的算法的平均時間復雜度為 O（1）。故本題選 D。