采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为A．O（n2）B．O（log2n）C．O（n log2n）D．O（n）

题目

采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为

A．O（n2）

B．O（log2n）

C．O（n log2n）

D．O（n）

相似考题

1.●采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 (36) 。(36) A．nB．n／2C．(n-1)／2D．(n+1)／2

2.采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为()。AnBn/2C(n-1)/2D(n+1)/2

3.在长度为n的有序表中折半查找一个元素的平均查找长度是()。A.O(n2)B.O(nlogn)C.O(n)D.O(logn)

4.采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为()。A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）

参考答案和解析
O（log 2 n）
更多“采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为”相关问题

  • 第1题：

    利用折半查找方法在长度为n的有序表中查找一个元素的平均查找长度是()。

    A.O(n2)

    B.O(nlogn)

    C.O(n)

    D.O(logn)


    参考答案：D

  • 第2题：

    采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为(36)。

    A．n

    B．n/2

    C．(n-1)/2

    D．(n+1)/2


    正确答案：D
    解析：n个位置共需要搜索1+2+…+n次，即n*(n+1)/2。平均长度为(n+1)/2。

  • 第3题：

    对长度为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。于是，查找成功的平均查找长度为[*]

  • 第4题：

    采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为______。

    A．n

    B．n/2

    C．(n+1)/2

    D．(n-1)/2


    正确答案：C

  • 第5题：

    类比二分搜索算法，设计k分搜索算法(k为大于2的整数)如下：首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值，然后检查2n/k处的元素，……，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为(57)，在最好情况下搜索失败的时间复杂度为(58)。

    A．O(logn)

    B．O(nlogn)

    C．O(logkn)

    D．O(nlogkn)


    正确答案：C

  • 第6题：

    采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

    A（n-1）/2

    B（n+1）/2

    Cn

    Dn/2


    B
    略

  • 第7题：

    长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。


    正确答案:4

  • 第8题：

    对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。

    • A、20
    • B、18
    • C、25
    • D、22

    正确答案:C

  • 第9题：

    长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。


    正确答案:37/12；62/13

  • 第10题：

    采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（）。

    • A、n
    • B、n/2
    • C、（n-1）/2
    • D、（n+1）/2

    正确答案:D

  • 第11题：

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

    正确答案： 1,logn
    解析： 暂无解析

  • 第12题：

    填空题
    长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。

    正确答案： 4
    解析： 暂无解析

  • 第13题：

    对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8；搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为(57)。

    A．5.5

    B．5

    C．39/8

    D．19/4


    正确答案：C
    解析：搜索到表中任一元素的平均搜索长度为：(1/8)*1+(1/8)*2+(1/8)*3+(1/8)*4+(1/8)*5+[(1/8)*5+(3/40)*1]++[(1/8)*4+(3/40)*2)*[(1/8)*3+(3/40)*3]+[(1/8)*2+(3/40)*4]+[(1/8)*2+(3/40)*5]＝(1/8)*(1+2+3+4+5)*2+(3/40)*(1+2+3+4+5)=15/8*2+45/40＝30/8+9/8＝39/8。

  • 第14题：

    若对大小为N的有序顺序表进行顺序查找，当查找不成功时，平均查找长度为(59)；当查找成功且表中仅有一个关键字等于欲查找的元素时，平均查找长度为(60)。

    A．N

    B．N+1

    C．N/2

    D．(N+1)/2


    正确答案：A
    解析：当查找不成功时，会查找至最后一个元素，故平均查找长度为N。

  • 第15题：

    设有序顺序表为{10，20，30，4，50，60，70)，采用折半搜索时，搜索成功的平均搜索长度是【 】。


    正确答案：2009-7-17
    2009-7-17 解析：ASLsucc=(1×1+2×2+3×4)/7= 17/7

  • 第16题：

    对长度为10的有序表进行折半查找，设在等概率时查找成功的平均查找长度是(46)。

    A．2.9

    B．3.1

    C．3.4

    D．2.6


    正确答案：A
    解析：各元素及其对应查找长度为：因此等概率时，查找成功的平均查找长度是：(3+2+3+4+1+3+4+2+3+4)/10=(1+2*2+3*4+4*3)/10=29/10=2.9。

  • 第17题：

    采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为()。

    A.(n-1)/2
    B.(n+1)/2
    C.n
    D.n/2

    答案：B
    解析：
    搜索的最好情况是第一个元素即想要查找的元素，最坏的情况是最后一个元素即想要查找的元素，所以平均查找长度是(n+l)/2。

  • 第18题：

    使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为（）

    • A、10
    • B、11
    • C、500
    • D、1000

    正确答案:A

  • 第19题：

    对长度为n的单有序表，若查找每元素的概率相等，则查找任一元素的平均查找长度为（）

    • A、n/2
    • B、n/4
    • C、（n+1）/2
    • D、（n-1）/2

    正确答案:C

  • 第20题：

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


    正确答案:1；logn

  • 第21题：

    采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

    • A、（n-1）/2
    • B、（n+1）/2
    • C、n
    • D、n/2

    正确答案:B

  • 第22题：

    填空题
    长度为12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（），查找失败时的平均查找长度是（）。

    正确答案： 37/12,62/13
    解析： 暂无解析

  • 第23题：

    单选题
    对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。
    A

    20

    B

    18

    C

    25

    D

    22


    正确答案： D
    解析： 暂无解析

  • 第24题：

    单选题
    采用顺序搜索方法查找长度为n的顺序表示，搜索成功的平均搜索长度为（）。
    A

    n

    B

    n/2

    C

    （n-1）/2

    D

    （n+1）/2


    正确答案： B
    解析： 暂无解析

相关内容