N个元素的线性表L以链式方式存储，访问第i个位置的数据元素的时间复杂度是（）。A．O（1）B．O（n）C．O(i)D．O（i -1）

第1题：

第2题：

第3题：

第4题：

答案：A

解析：

本题考查数据结构基础知识。
线性表(a1，a2，…，an)采用顺序存储方式如下图所示，其逻辑上相邻的元素物理位置也是相邻的，因此，按照序号访问元素的速度是很快的。

访问第i个元素(1≤i≤n)的元素，仅需计算出ai的存储位置再进行内存的随机访问操作即可，以LOC(a1)表示线性表中第一个元素的存储位置，L表示每个元素所占存储单元的个数，则计算LOC(ai)的方式如下：
LOC(ai)=LOC(a1)+(i-1)×L
再分析其他运算，不在表尾插入或删除时就需要移动其他元素，这是比较耗时的。查找与特定值相匹配的元素时，需要经过一个与表中多个元素进行比较的过程，相对于随机访问第i个元素，消耗更多时间。

第5题：

第6题：

在具有n个元素的顺序存储结构的线性表中删除某个元素的时间复杂度是（）。

第7题：

在具有n个元素的顺序存储结构的线性表中，若给定的是某个元素的关键字值，要访问该元素的其它信息的时间复杂度是（）。

第8题：

设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。

• A、n-i
• B、n+l-i
• C、n-1-i
• D、i

第9题：

设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中（）个数据元素；删除第i个位置上的数据元素需要移动表中（）个元素。

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

第16题：

答案：B

解析：

本题考查数据结构基础知识。
线性表（a1，a2，…，an）采用顺序存储时占用一段地址连续的存储单元，元素之间没有空闲单元，如下图所示。在这种存储方式下，插入和删除元素都需要移动一部分元素，这是比较耗时的操作。按照序号来查找元素，实际上是直接计算出元素的存储位置，例如，第i个元素ai的存储位置为LOC（ai）=LOC（a1）+（i-1）×L，其中L是每个元素所占用的存储单元数。按照值来查找元素时，需要与表中的部分元素进行比对，相对于按照序号来查找元素，需要更多的时间

第17题：

在一个长度为n的顺序存储结构的线性表中，向第i（1£i£n+1）个元素之前插入新元素时，需向后移动（）个数据元素。
n-i+1
略

第18题：

在具有n个元素的顺序存储结构的线性表中要访问第i个元素的时间复杂度是（）。

第19题：

顺序存储结构的线性表中，访问第i个元素与其位置（）关。（填有或无）

第20题：

设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为（）在链式存储结构上实现顺序查找的平均时间复杂度为（）

第21题：

第22题：

第23题：

第24题：