2024安徽農(nóng)商行秋季招聘計(jì)算機(jī)練習(xí)題（3）

　　下列對(duì)順序存儲(chǔ)的有序表（長(zhǎng)度為 n）實(shí)現(xiàn)給定操作的算法中平均時(shí)間復(fù)雜度為 O（1）的是（ ）。

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

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

　　C.刪除第 i 個(gè)元素的算法

　　D.獲取第 i 個(gè)值的算法













 

　　【答案】D

　　【考點(diǎn)】本題考查順序表的基本操作。

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

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

　　對(duì)于 C，刪除第 i 個(gè)元素需要將第 i 元素之后的所有元素向前移動(dòng)一個(gè)單位，因此該刪除操作的平均時(shí)間復(fù)雜度為 O（n），因此 C 錯(cuò)誤。

　　對(duì)于 D，順序表具有隨機(jī)存儲(chǔ)的特點(diǎn)，可以通過下標(biāo)直接訪問該值，因此獲取第 i 個(gè)值的算法的平均時(shí)間復(fù)雜度為 O（1）。故本題選 D。