对于n元素的向量,将其建立为一个有序单链表的时间复杂度为( )。
A.O(1)
B.O(n)
C.O(n2)
D.O(nlog2n)
第1题:
●在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 (53) 。
(53) A.O(1)
B.O(n)
C.O(nlogn)
D.O(n2)
【解析】本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此,在有序单链表中插入一个新结点后,仍然要保持它的有序性。
插入操作的关键是查找插入位置,主要时间也是花在插入位置的查找上。n个结点的单链表,有,n+1个可能插入的位置,即第一个结点之前和每一个结点之后。在第一个结点之前插入,需比较一次;在第一个结点之后插入需比较两次;…;在第,n个结点之后插入需查找次。如果在每一个位置上作插入的概率相等,即 ,则在有序单链表上查找插入位置的平均比较次数为:
第2题:
使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()
A.O(N)
B.O(logN)
C.O(N*N)
D.O(N*logN)
第3题:
直接选择排序的时间复杂度为()。(n为元素个数)
A.O(n)
B.O(log2n)
C.O(nlog2n)
D.O(n2)
第4题:
A.O(1)
B.O(n)
C.O(m)
D.O(m+n)
第5题:
下列程序段的时间复杂度为()。
A.O(n)
B.O(n-1)
C.O(n2)
D.O(log2n)
第6题:
下面程序段的时间复杂度为()。
A.O(n)
B.O(n2)
C.O(1)
D.O(nlog2n)
第7题:
一个算法的语句执行次数为(2n2+2nlog2n+4n-7),则其时间复杂度为()。
A.O(n2)
B.O(nlog2n)
C.O(n)
D.O(2n2)
第8题:
在有序双向链表中定位删除一个元素的平均时间复杂度为()
A.O(1)
B.O(N)
C.O(logN)
D.O(N*logN)
第9题:
从二叉搜索树中查找一个元素时,其时间复杂度大致为______。
A.O(n)
B.O(1)
C.O(log2n)
D.O(n2)
第10题:
在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为
A.O(n)
B.O(1)
C.O(n2)
D.O(log2n)