填空题使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（），在最坏情况下，搜索的时间复杂性为O（）。

题目

填空题

使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（），在最坏情况下，搜索的时间复杂性为O（）。

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()

A.O(N)

B.O(logN)

C.O(N*N)

D.O(N*logN)

正确答案：B

第2题：

对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为______。

A．n/2

B．(n+1)/2

C．(n-1)/2

D．n/4

正确答案：B
解析：由于链表不能随机访问，要访问某个节点，必须从它的直接前驱的指针域出发才能找到。因此，链式存储的线性表，即使是有序表，也只能使用顺序查找。顺序查找时，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。
假设在每个位置查找概率相等，即P1=P2=…=Pn=1/n，若是从表头向表尾方向查找，则每个位置上查找比较次数为C1＝1，C2＝2，…，Cn＝n。于是，查找成功的平均查找长度为[*]

第3题：

在长度为n的顺序存储结构的线性表中，插入(或删除)一个元素，在平均情况下需要移动表中的________个元素，在最坏情况下需要移动表中的________个元素。

正确答案：

n/2 n

第4题：

从具有n个结点的二叉查找树中查找一个元素时，在最坏情况下进行成功查找的时间复杂度为(51)。

A．O(n)

B．O(1)

C．O(log2n)

D．O(n2)

正确答案：A
解析：当二叉查找树严重不平衡时，二叉查找树有n层，最坏情况就是把n个结点都比较一遍才查找成功。

第5题：

从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为(18)。

A．O(1)

B．O(n)

C．

D．O(n2)

正确答案：C
解析：从一棵二叉搜索树中查找一个元素时，大约需要树的寓度次比较，即时间复杂度大致为。

第6题：

从二叉搜索树中查找一个元素时，其时间复杂度大致为______。

A．O(n)

B．O(1)

C．O(log2n)

D．O(n2)

正确答案：C

第7题：

在长度为n的顺序存储的线性表中删除一个元素，最坏情况下需要移动表中的元素个数为【 1 】。

正确答案：
【答案】：n-1
【知识点】：线性表中元素的删除
【解析】：在顺序存储线性表中删除一个元素，实际就是让后面的元素向前移动，在长度为n的顺序存储线性表中删除一个元素，最坏情况下需要移动表中n-1个元素。

第8题：

对于n个元素，下列哪种操作时间复杂度不是O(nlogn)()

A.凸包计算

B.LC搜索

C.有序序列数字查找

D.基于比较的排序

正确答案：C

第9题：

在一个长度为n的线性表中插入一个元素，以下说法不正确的是( )。

A．最好情况下需要移动的数据元素数目为0

B．最坏情况下需要移动的数据元素数目为n

C．在平均情况下需要移动的数据元素数目为n/2

D．最坏情况下需要移动的数据元素数目为n/2

正确答案：D
解析：在一般情况下，要在第i个元素之前插入一个新元素时，首先是从最后一个元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置。最好情况指的是性表的最后的元素之后插入一个新元素，则不需要移动表中元素，A是正确的。最坏情况指的是性表的第一个元素之前插入一个新元素，则需要移动表中所有的元素，B是正确的。在平均清况下需要移动的数据元素数目为n/2，C是正确的。

第10题：

对具有n个元素的有序表采用二分查找，则算法的时间复杂性为______。

A．O(n)

B． O(n2)

C． O(1)

D． O(log2n)

正确答案：D
解析：参见有序表采用二分查找时，算法的时间复杂性定义。二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等) 。当有序线性表为顺序存储时才能采用二分法查找，并且二分法查找的效率要比顺序查找高得多。

使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（），在最坏情况下，搜索的时间复杂

题目

相似问题和答案

更多相关问题

相关内容