采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为()。A、O(n2)B、O(nlog2n)C、O(n)D、O(log2n)
题目
A、O(n2)
B、O(nlog2n)
C、O(n)
D、O(log2n)
相似考题
更多“采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为()。 A、O(n2)B、O(nlog2n)C、O(n)D、O(log2n)”相关问题
-
第1题：
●对长度为n的顺序表进行顺序查找的时间复杂度为 (50) 。
(50) A．O(n)
B．O(［log2n］)
C．O(［log2］(n+1))
D．O(n2)
正确答案：A
【解析】因为对长度为n的顺序表进行顺序查找的平均查找长度为(n+1)／2，故时间复杂度为O(n)。 -
第2题：
（3）在长度为 n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是
A）O(n)
B）O(n2)
C）O(log2n)
D）O(nlog2n)
正确答案：C（3）【答案】C)
【解析】二分查找法也称折半查找法，它的基本思想是：将n个元素分成个数相同的两组，取a[n/2]与欲查找的X作比较。如果X=a[n/2],刚找到x，算法终止。如果x<a[n/2],则只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列）；如果x>a[n/2]则只要在数组a的右半部继续搜索x。每次余下n/(2r)个元素待比较时，即n/(2r)=1.故，n=2i,i=long2n. -
第3题：
用二分查找法对具有n个节点的线性表查找一个节点所需的平均比较次数为( )。
A．O(n2)
B．O(nlog2n)
C．O(n)
D．O(log2n)
正确答案：D
解析：二分查找对应的判定树为平衡树，其树的高度达到最小，因此其平均比较次数为O(log2n)。 -
第4题：
利用折半查找方法在长度为n的有序表中查找一个元素的平均查找长度是()。A.O(n2)
B.O(nlogn)
C.O(n)
D.O(logn)
参考答案：D
-
第5题：
在长度为z的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
正确答案：C
解析： 对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。 -
第6题：
对具有n个元素的有序表采用二分查找，则算法的时间复杂性为______。
A．O(n)
B． O(n2)
C． O(1)
D． O(log2n)
正确答案：D
解析： 参见有序表采用二分查找时，算法的时间复杂性定义。二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等) 。当有序线性表为顺序存储时才能采用二分法查找，并且二分法查找的效率要比顺序查找高得多。 -
第7题：
设平衡的二叉排序树(AVL树)的结点个数为n，则其平均查找长度的数量级为________。
A．O(1)
B．O(log2n)
C．O(n)
D．O(nlog2n)
正确答案：B
解析：平衡二叉树又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。因为AVL树上任何结点的左右子树的深度之差都不超过1，则可以证明它的深度和logN是同数量级的(N为结点个数)。由此，它的平均查找长度也和logN同数量级。 -
第8题：
顺序查找一个具有n个元素的线性表，二分查找一个具有n个元素的有序表，其时间复杂性为______。
A．O(n)
B．O(log2n)
C．O(n2)
D．O(nlog2n)
正确答案：B
-
第9题：
在长度为n的有序线性表中进行二分查找，在最坏的情况下需要比较的次数是( )。
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
正确答案：C
解析： 二分查找法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]，则找到x，算法终止；如果x2n。 -
第10题：
设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。
- A、O（1）
- B、O（log2n）
- C、O（n4）
- D、O（n2）
正确答案:B -
第11题：
在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。
- A、O（0）
- B、O（1）
- C、O（n）
- D、O（n2）
正确答案:C -
第12题：
对含n个记录的有序表进行折半查找，设每个记录的查找概率相等，则平均查找长度的数量级为（）。
- A、O（n）
- B、O（n2）
- C、O（log2n）
- D、O（1）
正确答案:C -
第13题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是( )。
A．O(n)
B．O(n2)
C．O(log2n)
D．O(nlog2n)
正确答案：C
解析：对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，而顺序查找需要比较n次。 -
第14题：
用顺序查找法对具有n个节点的线性表查找一个节点所需的平均比较次数为( )。
A．O(n2)
B．O(nlog2n)
C．O(n)
D．O(log2n)
正确答案：C
解析：根据要找的元素存在的位置，其比较次数依次为1、2…n，所以平均比较次数为(1+n)n/2/n=(1+n)/2，所以其时间复杂度为O(n)。 -
第15题：
在长度为n的有序表中折半查找一个元素的平均查找长度是()。A.O(n2)
B.O(nlogn)
C.O(n)
D.O(logn)
参考答案：D
-
第16题：
在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是
A．O(n)
B．o(n2)
C．O(10g2n)
D．O(nlog2n)
正确答案：C
解析：二分查找法也称为折半查找法。它的基本思想是：将n个元素分成个数大致相同的两组，取a[n／2]与欲查找的x作比较。如果x=a[／2]，则找到x，算法终止；如果x -
第17题：
从具有n个结点的二叉查找树中查找一个元素时，在最坏情况下进行成功查找的时间复杂度为(51)。
A．O(n)
B．O(1)
C．O(log2n)
D．O(n2)
正确答案：A
解析：当二叉查找树严重不平衡时，二叉查找树有n层，最坏情况就是把n个结点都比较一遍才查找成功。 -
第18题：
采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为______。
A．O(log2n)
B．O(n)
C．O(nlog2n)
D．O(n2)
正确答案：A
-
第19题：
在长度为 n 的有序线性表中进行顺序查找，最坏情况下需要比较的次数是A．O(n) B．O(n2) C．O(log2n) D．O(nlog2n)
正确答案：A
在有序的线性表中进行查找，最差的情况为从表头查找到表尾都没有所需要的值。长度为n的线性表从表头开始每次取出一个值比较，若不符合，再取下一个值，依次比较，一直到最后一个，需要比较n次。 -
第20题：
二分查找一个具有n个元素的有序表，其时间复杂度为______。
A．O(n)
B．O(n2)
C．O(log2n)
D．(nlog2n)
正确答案：C
解析：二分法中查找时间t与查找次数m呈比例关系，2m=n(n为极限查找个数)，m=log2n，所以查找时间复杂度与log2n相关。 -
第21题：
对具有n个元素的有序表采用二分查找法，则算法的时间复杂性为（）
- A、O（n）
- B、O（n2）
- C、O（1）
- D、O（log2n）
正确答案:D -
第22题：
对包含n个元素的哈希表进行查找，平均查找长度为（）
- A、O（log2n）
- B、O（n）
- C、O（nlog2n）
- D、不直接依赖于n
正确答案:D -
第23题：
对具有n个元素的有序表采用折半查找，则算法的时间复杂度为（）。
- A、 O（n）
- B、 O（n2）
- C、 O（1）
- D、 O（log2n）
正确答案:D