itgle.com
在n个元素的线性表的数组表示中,时间复杂度为O（1)的操作是（）。A．访问第i(1＜i＜n)个结点和求第i(2＜i＜n）个结点的直接前驱B．在最后一个结点后插入一个新值C．删除第i个结点D．在第i(1＜i＜n)个结点后插入一个结点
题目
在n个元素的线性表的数组表示中,时间复杂度为O（1)的操作是（）。
A．访问第i(1＜i＜n)个结点和求第i(2＜i＜n）个结点的直接前驱
B．在最后一个结点后插入一个新值
C．删除第i个结点
D．在第i(1＜i＜n)个结点后插入一个结点
相似考题
参考答案和解析
更多“在n个元素的线性表的数组表示中,时间复杂度为O（1)的操作是（）。”相关问题
-
第1题：
顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。
A.O(n)
B.O(n^2)
C.O(n^1/2)
D.O(1og2n)
正确答案：A
-
第2题：
在下列对单链表进行的操作中,算法时间复杂度为O(n)的是()。A、访问第i个元素的前驱(1
B、在第i个元素之后插入一个新元素(1≤i≤n)
C、删除第i个元素(1≤i≤n)
D、对表中元素进行排序
参考答案：A
-
第3题：
对于一个长度为n的顺序存储的线性表,在表尾插入元素的时间复杂度为()A、O(n)
B、O(n*n)
C、O(1)
D、O(0)
参考答案：C
-
第4题：
若长度为n的线性表采用顺序存储结构，在第i≤1≤i≤n+1) 个位置插入一个新元素的算法时间复杂度为(1)。
A．O(0)
B．O (1)
C．O(n)
D．O(n2)
正确答案：C
解析：性表上插入元素，时间主要耗费在移动元素上。不失一般性，假定性表上的任何位置插入元素是等概率的，即：Pi=1/(n+1)，那么在插入一个元素时所需要移动元素的次数的平均值为：。因此，在长度为n的线性表中插入一个元素的时间复杂度为。 -
第5题：
快速排序算法是，在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 （ ） 算法设计策略。已知确定着基准元素操作的时间复杂度为O(n)，则快速排序算法的最好和最坏情况下的时间复杂度为 （请作答此空） 。A.O(n)和O(nlgn)
B.O(n)和O(n2)
C.O(nlgn)和O(nlgn)
D.O(nlgn)和O(n2)答案：D解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。
理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O(nlgn)。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O(n)，次操作的总复杂度为O(n2)。 -
第6题：
在具有n个元素的顺序存储结构的线性表中删除某个元素的时间复杂度是（）。
正确答案:O(n) -
第7题：
从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为（），输出一个二维数组b[m][n]中所有元素值的时间复杂度为（）。
正确答案:O（n）；O（m*n） -
第8题：
对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为（），在表尾插入元素的时间复杂度为（）。
正确答案:O（1）；O（n） -
第9题：
对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。
- A、O（1）
- B、O（n）
- C、O（n2）
- D、O（nlog2n）
正确答案:C -
第10题：
对一个具有n个元素的线性表，建立其单链表的时间复杂度为（）
- A、O（n）
- B、O（1）
- C、O（n2）
- D、O（nlog2n）
正确答案:A -
第11题：
设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
- A、O（n）
- B、O（nlog2n）
- C、O（1）
- D、O（n2）
正确答案:C -
第12题：
问答题我们通常采用大O形式来表示算法的时间复杂度。例如，在一个长度为n的顺序表中顺序查找一个数据元素的过程的时间复杂度为O（n），其中，n表示问题的规模。那么，O（1）表示什么？请举出一个例子加以说明。正确答案： O(1)表示时间复杂度与问题规模无关。例如，在堆栈或者队列中插入一个新的元素的过程的时间复杂度为O(1)。解析： 暂无解析 -
第13题：
在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是()
A.O(n)
B.O(nlogn)
C.O(n(logn)2)
D.O(n3/2)
正确答案：A
-
第14题：
在单链表中,查找第i个的元素时,其时间复杂度为()。A、O(n)
B、O(1)
C、O(n2)
D、O(n-1)
参考答案：A
-
第15题：
在顺序存储结构线性表中插入或删除一个数据元素的时间复杂度( )。
A．不同
B．都为O(n)
C．都为O(n2)
D．都为O(1)
正确答案：B
解析：在顺序存储结构线性表中插入或删除一个数据元素时间主要耗费在移动元素上，插入一个元素所需移动元素的平均次数为n/2，删除一个数据元素所需移动元素的平均次数为(n-1)/2，所以它们的时间复杂度都为O(n)。 -
第16题：
在二维数组M[0．．．n，0．．．m]中，访问某个元素的平均时间复杂度为______。
A．O(1)
B．O(nm)
C．O(m+n)
D．O(nn)
正确答案：A
解析：二维数组可以实现随机访问，因此访问时间复杂度为O(1)。 -
第17题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了（61）算法设计策略。已知确定着基准元素操作的时间复杂度为O（n），则快速排序算法的最好和最坏情况下的时间复杂度为（62）。A.O（n）和O（nlgn）
B.O（n）和O（n2）
C.O（nlgn）和O（nlgn）
D.O（nlgn）和O（n2）答案：D解析：将数据分成若干份，每份单独处理后再合并，其思想为分治。理想情况下，快速排序每次将数据划分为规模相近的两部分，并递归至不可再划分，因此其时间复杂度为O（nlgn）。在最坏情况下，每次划分都极不均匀，如一个类别中仅有一个元素，另一个类别中包含剩余所有元素。这时划分的复杂度为O（n），”次操作的总复杂度为O（n2）。 -
第18题：
在具有n个元素的顺序存储结构的线性表中要访问第i个元素的时间复杂度是（）。
正确答案:O（1） -
第19题：
若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（）。
- A、O（log2n）
- B、O（1）
- C、O（n）
- D、O（n2）
正确答案:C -
第20题：
在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。
- A、O（0）
- B、O（1）
- C、O（n）
- D、O（n2）
正确答案:C -
第21题：
对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为（），在表尾插入元素的时间复杂度为（）
正确答案:O(n)；O(1) -
第22题：
在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（）。
- A、访问第i（1＜＝i＜＝n）个结点和求第i个结点的直接前驱（1＜i＜＝n）
- B、在第i（1＜＝i＜＝n）个结点后插入一个新结点
- C、删除第i（1＜＝i＜＝n）个结点
- D、以上都不对
正确答案:A -
第23题：
单选题插入排序是一种简单实用的工具，在对数组排序时，我们可能用二分查找，对要插入的元素快速找到在已经排好元素序列中的位置。下面的描述中正确的是（）。A二分查找的时间复杂度为O（lgN），因此排序的时间复杂度为O（N*lgN）
B二分查找的时间复杂度为O（N），因此排序的时间复杂度为O（N*lgN）
C二分查找的时间复杂度为O（lgN），因此排序的时间复杂度为O（N*N）
D二分查找的时间复杂度为O（N），因此排序的时间复杂度为O（N*N）
正确答案： B解析： 暂无解析 -
第24题：
单选题在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（）。A访问第i（1＜＝i＜＝n）个结点和求第i个结点的直接前驱（1＜i＜＝n）
B在第i（1＜＝i＜＝n）个结点后插入一个新结点
C删除第i（1＜＝i＜＝n）个结点
D以上都不对
正确答案： C解析： 暂无解析