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。