单项选择(2012北京工业大学)

在含有n个元素的顺序表中,算法时间复杂度为O(1)的操作是【 】

A、将n个元素按照从小到大的顺序重新排列

B、在第i个元素之后插入一个新元素(1≤i≤n)

C、访问第i个元素(1≤i≤n)

D、删除第i个元素(1≤i≤n)

答案解析

C

【解析】

顺序表支持随机访问,其时间复杂度和问题规模n无关,即为O(1);

插入和删除算法和操作位置有关,时间复杂度为O(n);

排序算法的时间复杂度也和n有关,根据算法不同时间复杂度也不同。

讨论

设A是一个线性表(a1,a1,...,an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为多少?若元素插在ai与ai+1之间(0≤i≤n-1)的概率为,则平均每插入一个元素所要移动的元素个数又是多少?

表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为_______,删除一个元素需要移动元素的平均个数为_______。供选择的答案:A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

顺序表存储方式只能用于存储线性结构。

假设线性表的长度为n,且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时,插入一个数据元素需要移动元素的平均个数为【 】。

若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法时间复杂度为【 】。(1≤i≤n+1)

若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是【 】。

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构(数组存储),则在等概率下,删除一个元素平均需要移动的元素数为【 】。

线性表选用顺序存储结构表示的适用场合是____________________。

含有n个元素的线性表采用顺序存储,等概率删除其中任一个元素,平均需要移动【 】个元素。

设A是一个线性表(a1,a1,...,an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为多少?若元素插在ai与ai+1之间(0≤i≤n-1)的概率为,则平均每插入一个元素所要移动的元素个数又是多少?

表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为_______,删除一个元素需要移动元素的平均个数为_______。供选择的答案:A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

顺序表存储方式只能用于存储线性结构。

假设线性表的长度为n,且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时,插入一个数据元素需要移动元素的平均个数为【 】。

若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法时间复杂度为【 】。(1≤i≤n+1)

若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是【 】。

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构(数组存储),则在等概率下,删除一个元素平均需要移动的元素数为【 】。

线性表选用顺序存储结构表示的适用场合是____________________。

含有n个元素的线性表采用顺序存储,等概率删除其中任一个元素,平均需要移动【 】个元素。