2027年408真题数据结构篇

一、单项选择题

第01~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

01.

下列对顺序存储的有序表（长度为 $n$n ）实现给定操作的算法中，平均时间复杂度为 $O\left(1\right)$O(1) 的是（ ）。

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

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

C. 删除第 $i\text{?}(1\le i\le n)$i\ (1\le i\le n) 个元素的算法

D. 获取第 $i\text{?}(1\le i\le n)$i\ (1\le i\le n) 个元素的算法

解答：

方法一：分析选项

顺序存储的有序表即有序数组。

A选项中，在有序数组中查找包含指定值的元素的位置最快的方法是用二分查找，时间复杂度为 $O(\log ?n)$O(\log n) 。该选项错误。

B选项中，在有序数组中查找包含指定值的元素最快的方法是首先用二分查找找到插入元素的位置，时间复杂度为 $O(\log ?n)$O(\log n) ，然后把位于插入元素后面的元素的位置后移一格，平均时间复杂度为 $O\left(n\right)$O(n) ，综上，总的时间复杂度为 $O\left(n\right)$O(n) 。该选项错误。

C选项中，删除第 $i$i 个元素的最快的方法是首先利用顺序表支持随机访问的性质找到第 $i$i 个元素并删除，时间复杂度为 $O\left(1\right)$O(1) ，然后把位于插入元素后面的元素的位置前移一格，平均时间复杂度为

如需高考志愿指导，可联系网站客服获取！助你成功率提升90%！

学员评价