（填空题）
对于长度为n的顺序表的删除算法，它的最坏情况时间复杂性及其量级分别是（）和（），平均时间复杂性及其量级分别为（）和（）
正确答案
n-1；O(n)；(n-1)／2；O(n)
答案解析
对于顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点移动为标准操作，其依据是：在这类问题中，移动一个结点所花费的时间往往比其他基本操作要多得多。对于删除算法，结点移动的次数不仅与表长n有关，而且还与删除的位置i有关：当i=n时，移动次数为0；当i=l时，移动次数为n-1，达到最大值。因此，删除算法的最坏情况时间复杂性为n-1，其量级为O(n)。分析平均时间复杂性需计算在各种输入下结点移动次数的加权平均值。由以上讨论可知，使结点移动次数不同的输入有n种可能，结点移动总次数为n(n-1)。假定出现各种情况的可能性(即概率)相同，均为1／n，1／n就是每种情况下的结点移动次数的权。所以，删除算法的平均时间复杂性为：(n-1)／2。
相似试题
（判断题）
若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。
（判断题）
若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。
（单选题）
若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动（）个数据元素。
（填空题）
在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。
（单选题）
对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。
（简答题）
请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。 ⑴若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 ⑵如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 ⑶描述一个城市的设计和规划。
（单选题）
删除长度为n的顺序表中的第i（1≤i≤n）个位置上的元素，元素的移动次数为：（）
（单选题）
在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。
（判断题）
在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0。
