（数据结构）设线性表（a1,a2,a3,...,a500)中所有元素的值由小到大排列，对一个给定的值K，用二分法查找表中与K相等的元素，在查找不成功的情况下，至多需要比较 次。A、8B、9C、10D、11

题目

（数据结构）设线性表（a1,a2,a3,...,a500)中所有元素的值由小到大排列，对一个给定的值K，用二分法查找表中与K相等的元素，在查找不成功的情况下，至多需要比较 次。

A、8

B、9

C、10

D、11

相似考题

1.设有一个已按各元素的值排好序的顺序表(长度大于2) ，现分别用顺序查找法和二分查找法查找与给定值k相等的元素，比较的次数分别是，和b，在查找不成功的情况下s和b的关系是A．s=bB．s＞bC．s＜bD．s＞=b

2.设有一个已按各元素的值排好序的顺序表(长度大于2)，现分别用顺序查找法和二分查找法查找与给定值k相等的元素，比较的次数分别是s和b，在查找不成功情况下s和b的关系是A．s=bB．s＞bC．s＜bD．s＞=b

3.有一排好序的线性表，长度大于2，对给定的K值，分别用顺序查找和二分查找一个与K值相等的元素，比较的次数分别是X和Y。在查找不成功的情况下，正确的X和Y的关系是A．X，YB．X＜YC．X=YD．与K大小有关

4.在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为().AnBn/2C(n+1)/2D(n-1)/2

更多“（数据结构）设线性表（a1,a2,a3,...,a500)中所有元素的值由小到大排列，对一个给定的值K，用二分法查找表中与K相等的元素，在查找不成功的情况下，至多需要比较 次。A、8B、9C、10D、11”相关问题

  • 第1题：

    设一线性表中有a1，a2，…，a500个元素按递增顺序排列，则用二分法查找给定值K，最多需要比较______次。


    正确答案：9
    9 解析：因为29=512，故最多需要比较9次。

  • 第2题：

    设有一个已按各元素的值排好序的线性表，长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k值相等的元素，比较的次数分别为s和b，在查找不成功的情况下，正确的s和b的数量关系是

    A．总有s＞b

    B．总有s＜b

    C．总有s=b

    D．与k值大小有关


    正确答案：D
    解析：第一步，理解题意，抓住一个关键词“排好序的线性表”，对解决此题帮助甚大。第二步，着手分析，因为顺序查找并没有要求逻辑次序，即没有要求将线性按关键码排好序。而本题中恰恰是排好序的线性表，所以当顺序查找失败时，不必遍历全表，而仅是其大于或小于某个值时确定查找是否结束，这也是解题的关键。再分析一下二分查找，进行的前提即为排好序，每经过一次比较将查找范围缩小一半。第三步分析s和b的关系，待查值k的大小决定了其在表中的前后位置，而位置的这种变化直接使得顺序查找次数的大小变化，二分查找亦如此。故s和b大小关系是不确定的。

  • 第3题：

    有一个排好序的线性表，长度大于2，对给定的k值，分别用顺序查找和二分查找查找一个与k值相等的元素，比较的次数分别为x和y。在查找不成功的情况下，正确的x和y的关系是______。

    A．x＞y

    B．总是x＜y

    C．x＝y

    D．与k值大小有关


    正确答案：D
    解析：顺序查找没有要求线性表按关键词值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，则k值大小决定了线性表的位置，所以应选择D。

  • 第4题：

    设有一个己按各元素的值排好序的线性表，长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别为s和b，在查找不成功的情况下，正确的s和b的数量关系是 ______。

    A．总有s=b

    B．总有s＞b

    C．总有s＜b

    D．与k值大小有关


    正确答案：D

  • 第5题：

    若在线性表中采用折半查找方法进行查找，该线性表必须（）。

    • A、元素按值有序排列
    • B、采用顺序结构
    • C、元素按值有序排列，并且采用顺序存储结构
    • D、元素按值有序排列，并且采用链式存储结构

    正确答案:C

  • 第6题：

    线性有序表（a1，a2，a3，，，a10）按关键字从小到大排列，对一个给定的关键字值k，用二分法查找表中关键字与k相等的元素，在查找不成功的情况下，最多需要查找（）次。


    正确答案:4

  • 第7题：

    有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。


    正确答案:s；s

  • 第8题：

    设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。


    正确答案:1；7

  • 第9题：

    在具有n个元素的顺序存储结构的线性表中查找某个元素，平均需要比较（）次。


    正确答案:n+1/2

  • 第10题：

    填空题
    线性有序表（a1，a2，a3，，，a10）按关键字从小到大排列，对一个给定的关键字值k，用二分法查找表中关键字与k相等的元素，在查找不成功的情况下，最多需要查找（）次。

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

  • 第11题：

    单选题
    若在线性表中采用折半查找方法进行查找，该线性表必须（）。
    A

    元素按值有序排列

    B

    采用顺序结构

    C

    元素按值有序排列，并且采用顺序存储结构

    D

    元素按值有序排列，并且采用链式存储结构


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

  • 第12题：

    判断题
    在1000个大小有序的列表中查找某给定元素。用顺序查找法至多需要比较1000次（平均需要500次）可以找到该元素或确定列表中不存在该元素（需要比较1000次），而用折半查找法至多10次比较就可以找到该元素或者确定列表中不存在该元素。由此可以知，折半查找的效率比顺序查找的效率至少高50倍。
    A

    对

    B

    错


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

  • 第13题：

    设一线性表中有al，a2，…，a500个元素按递增顺序排列，则用二分法查找给定值K，最多需要比较【 】次。


    正确答案：9
    9 解析：因为29=512，故最多需要比较9次。

  • 第14题：

    有一排好序的线性表，长度大于2，对给定的k值，分别用顺序查找和二分查找查找一个与k值相等的元素，比较的次数分别为x和y。在查找不成功的情况下，正确的x和y的关系是 ______。

    A．x＞y

    B．总是x＜y

    C．x＝y

    D．与k值的大小有关


    正确答案：D
    解析：顺序查找没有要求线性表按关键字值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，则k值大小决定了性表的位置，所以应选择D。

  • 第15题：

    设—线性表中有a1，32，…，a500个元素按递增顺序排列，则用二分法查找给定值K，最多需要比较【 】次。


    正确答案：9
    9 解析：因为29＝512，故最多需要比较9次。

  • 第16题：

    设线性表有n个元素，以下操作中，在顺序表上实现比在链表上实现效率更高的是()。

    A.输出第i个元素值
    B.交换第1个元素与第2个元素的值
    C.顺序输出这n个元素的值
    D.输出与给定值x相等的元素存线性表中的序号

    答案：A
    解析：
    顺序表的一个主要特点就是可以直接存取任一指定序号的元素，输出第i个元素值时间复杂度为O(1)。B项需要开辟临时空间，CD两项的时间复杂度均为O(n)；

  • 第17题：

    下面关于折半查找法的叙述中，正确的是（）。

    • A、只要线性表中元素按值有序排列，就可以采用折半查找
    • B、只要线性表采用顺序存储结构，就可以采用折半查找
    • C、线性表中元素按值有序排列，并且采用顺序存储结构时才能采用折半查找
    • D、在链表中也可以采用折半查找

    正确答案:C

  • 第18题：

    在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（）。

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

    正确答案:C

  • 第19题：

    线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索（）次。设有100个结点，用二分法查找时，最大比较次数是（）。


    正确答案:8；7

  • 第20题：

    在1000个大小有序的列表中查找某给定元素。用顺序查找法至多需要比较1000次（平均需要500次）可以找到该元素或确定列表中不存在该元素（需要比较1000次），而用折半查找法至多10次比较就可以找到该元素或者确定列表中不存在该元素。由此可以知，折半查找的效率比顺序查找的效率至少高50倍。


    正确答案:错误

  • 第21题：

    单选题
    在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（）。
    A

    n

    B

    n/2

    C

    （n+1）/2

    D

    （n-1）/2


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

  • 第22题：

    填空题
    设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。

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

  • 第23题：

    单选题
    下面关于折半查找法的叙述中，正确的是（）。
    A

    只要线性表中元素按值有序排列，就可以采用折半查找

    B

    只要线性表采用顺序存储结构，就可以采用折半查找

    C

    线性表中元素按值有序排列，并且采用顺序存储结构时才能采用折半查找

    D

    在链表中也可以采用折半查找


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

相关内容