单选题某顺序存储的表格，其中有90000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。用顺序查找法查找时，平均比较次数约为__（1）__，最大比较次数为__（2）__。现把90000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是__（3）__，此时的平均比较次数

题目
单选题
某顺序存储的表格，其中有90000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。 用顺序查找法查找时，平均比较次数约为__（1）__，最大比较次数为__（2）__。 现把90000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是__（3）__，此时的平均比较次数是__（4）__。当g的值大于等于90000时，此方法的查找速度接近于__（5）__。 空白（2）处应选择（）
A

25000

B

30000

C

45000

D

90000

相似考题

1.对线性表进行折半查找时,要求线性表必须_______。A、以顺序方式存储B、以链式方式存储C、以顺序方式存储且表中元素按关键字有序排列D、以链式方式存储且表中元素按关键字有序排列

2.● 折半（二分）查找方法对查找表的要求是（42）。（42）A.链表存储结构，元素有序排列B.链表存储结构，元素无序排列C.顺序存储结构，元素有序排列D.顺序存储结构，元素无序排列

3.在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。A.相同，元素的存储顺序与逻辑顺序一致B.相同，但其元素的存储顺序可以与逻辑顺序不一致C.不同，但元素的存储顺序与逻辑顺序一致D.不同，且其元素的存储顺序可以与逻辑顺序不一致

4.对长度为10的顺序表进行查找,若查找前面5个元素的概率相同,均为1／8,查找后面5个元素的概率相同,均为3／40,则查找任一元素的平均查找长度为()。A.5.5B.5C.39/8D.19/4

更多“某顺序存储的表格，其中有90000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的”相关问题

  • 第1题：

    若在线性表中采用折半查找法查找元素，该线性表应该()

    A.元素按值有序

    B.构采用顺序存储结

    C.元素按值有序且采用顺序存储结构

    D.元素按值有序且采用链式存储结构


    正确答案：C

  • 第2题：

    从供选择的答案中选出应填入下列叙述中()内的正确答案：

    某顺序存储的表格，其中有90 000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查询的概率是相同的，并且各个元素的关键项的值皆不相同。用顺序查找法查找是，平均比较次数约为(A) ，最大比较次数为(B) 。

    现把90000个元素按排列顺序划分成若干组，使每组有g个元素(最后一组可能不足 8个)。查找时，先从头一组开始，通过比例各组的最后一个元素的关键项的值，找到预查找的元素所在的组，然后再用顺序查找找到预找的元素。在这种查找法中，使总的平均比较次数最小为(C) ，此时的平均比较次数是(D) 。

    当8的值大于等于90，000时，此方法的查找速度接近于(E)。

    供选择的答案

    A、B：①25 000 ②30 000

    ③45000 ④90 000

    C、D：①100 ②200

    ③300 ④400

    E：①快速分类法 ②斐波那契查找法

    ③二分法 ④顺序查找法


    正确答案：A：③ B：④ C：③ D：③
    A：③ B：④ C：③ D：③

  • 第3题：

    对长度为10顺序表进行顺序查找，若查找前5个元素的概率相同，均为1/8，查找后5个元素的概率相同，均为3/40，则查找到表中任一元素的平均查找长度为______。

    A．55

    B．5

    C．39/8

    D．19/4


    正确答案：C
    解析：查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的节点。
      平均查找长度：为确定记录在查找表中的位置，须与给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度。对含有n个记录的表，查找成功时的平均查找长度定义为：，其中，Pi为对表中第i个记录进行查找的概率，且。
      在此，

  • 第4题：

    折半(二分)查找法适用的线性表应该满足（ ）的要求。

    A.链接方式存储、元素有序B.链接方式存储、元素无序C.顺序方式存储、元素有序D.顺序方式存储、元素无序


    正确答案：C

  • 第5题：

    在一个线性表上可以进行二分查找(折半查找)的充分必要条件是( )。

    A. 线性表采用顺序存储且元素有序排列B. 线性表采用顺序存储且元素无序排列C. 线性表采用单链表存储且元素有序排列D. 线性表采用单链表存储且元素无序排列


    正确答案：A

  • 第6题：

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

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

    正确答案:C

  • 第7题：

    适用于折半查找的表的存储方式及元素排列要求为（）

    • A、链接方式存储，元素无序
    • B、链接方式存储，元素有序
    • C、顺序方式存储，元素无序
    • D、顺序方式存储，元素有序

    正确答案:D

  • 第8题：

    若在线性表中采用折半查找法查找元素，该线性表应该（）。

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

    正确答案:C

  • 第9题：

    单选题
    某顺序存储的表格，其中有90000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。用顺序查找法查找时，平均比较次数约为__（1）__，最大比较次数为__（2）__。 现把90000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。 在这种查找法中，使总的平均比较次数最小的g是__（3）__，此时的平均比较次数是__（4）__。当g的值大于等于90000时，此方法的查找速度接近于__（5）__。 空白（5）处应选择（）
    A

    快速分类法

    B

    斐波那契查找法

    C

    二分法

    D

    顺序查找法


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

  • 第10题：

    单选题
    某顺序存储的表格，其中有90000个元素，已按关键字递增有序排列，现假定对各个元素进行查找的概率是相同的，并且各个元素的关键字皆不相同。用顺序查找法查找时，平均比较次数约为__（1）__，最大比较次数为__（2）__。 现把90000个元素按排列顺序划分成若干组，使每组有g个元素（最后一组可能不足g个）。查找时，先从第一组开始，通过比较各组的最后一个元素的关键字，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。 在这种查找法中，使总的平均比较次数最小的g是__（3）__，此时的平均比较次数是__（4）__。当g的值大于等于90000时，此方法的查找速度接近于__（5）__。 空白（4）处应选择（）
    A

    100

    B

    200

    C

    300

    D

    400


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

  • 第11题：

    单选题
    对线性表进行二分查找时，要求线性表必须（）。
    A

    以顺序存储方式

    B

    以顺序存储方式，且数据元素有序

    C

    以链接存储方式，且数据元素有序

    D

    以链接存储方式


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

  • 第12题：

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

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

    B

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

    C

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

    D

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


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

  • 第13题：

    对线性表进行二分查找时,要求线性表必须( )。

    A、以顺序方式存储

    B、以顺序方式存储,且数据元素有序

    C、以链接方式存储

    D、以链接方式存储,且数据元素有序


    正确答案:B

  • 第14题：

    折半(二分)查找方法对查找表的要求是( )。

    A．链表存储结构，元素有序排列

    B．链表存储结构，元素无序排列

    C．顺序存储结构，元素有序排列

    D．顺序存储结构，元素无序排列


    正确答案：C
    解析：二分查找也叫折半查找，其基本思想是：以处于中间位置元素的关键字和给定值比较，如果相等，则查找成功。如果给定值大于中间位置元素，则下一次在后半个子表进行二分查找。如果给定值小于中间位置元素，则下一次在前半个子表进行二分查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。显然，如果要查找的表是无序排列，则查找就没有意义。另外，查找需要能直接定位表中间位置的元素，即实现随即访问，因此只有顺序存储结构能满足此要求，在链表上只能顺序查找。【总结与扩展】二分查找在查找成功时和给定值进行比较的关键字格式至多为[log2n]+1。二分查找在查找不成功时和给定值进行比较的关键字格式最多也不会超过[log2n]+l。当查找的表元素值较大时，二分查找的平均查找长度为log2(n+1)-1。二分查找要求查找表进行顺序存储并且按照关键字有序排列，因此当对表进行元素插入或删除时，需要移动大量的元素。所以二分查找适用于表不易变动，且又经常进行查找的情况。

  • 第15题：

    某顺序存储的表格，其中有90000个元素，已按关键字的值的上升顺序排列。现假定对各个元素进行查拢的概率是相同的，并且各个元素的关键字的值皆不相同。用顺序查找法查找时，平均比较次数约为(56)，最大比较次数是(57)。

    现把90000个元素按排列顺序划分成若干组，使每组有g个元素(最后一组可能不足g个)。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的8是(58)，此时的平均比较次数是(59)，当s的值大于90000时，此方法的查找速度接近于(60)。

    A．25000

    B．30000

    C．45000

    D．90000


    正确答案：C

  • 第16题：

    性表中采用折半查找法(二分查找法)查找一个数据元素，线性表应(54)。

    A．数据元素按值有序

    B．采用顺序存储结构

    C．据元素按值有序，并且采用顺序存储结构

    D．据元素按值有序，并且采用链式存储结构


    正确答案：C
    解析：只有当线性表中数据元素按值大小有序排列，并且采用顺序存储结构时才能使用折半查找方法查找元素。即使线性表中数据元素按值大小有序排列，但采用的不是顺序存储结构(如链式)，仍然不能够采用折半查找方法。本题应选C。

  • 第17题：

    适用于折半查找的表的存储方式及元素排列要求为()。

    A.链接方式存储，元素无序
    B.链接方式存储，元素有序
    C.顺序方式存储，元素无序
    D.顺序方式存储，元素有序

    答案：D
    解析：
    折半查找的线性表中的结点必须已按关键字值的递增或递减顺序排列，而且为顺序存储。

  • 第18题：

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

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

    正确答案:C

  • 第19题：

    假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。假定每个元素的查找概率相等，求查找成功时的平均查找长度。


    正确答案:求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
    但最后一层未满，不能用8×4，只能用5×4=20次，
    所以ASL＝1/12（17＋20）＝37/12≈3.08

  • 第20题：

    单选题
    适用于折半查找的表的存储方式及元素排列要求为（）
    A

    链接方式存储，元素无序

    B

    链接方式存储，元素有序

    C

    顺序方式存储，元素无序

    D

    顺序方式存储，元素有序


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

  • 第21题：

    单选题
    若在线性表中采用折半查找法查找元素，该线性表应该（）。
    A

    元素按值有序

    B

    采用顺序存储结构

    C

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

    D

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


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

  • 第22题：

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

    元素按值有序排列

    B

    采用顺序结构

    C

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

    D

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


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

  • 第23题：

    单选题
    进行二分法查找，则线性表（）
    A

    必须以顺序方式存储

    B

    必须以链接方式存储

    C

    必须以链接方式存储，且数据元素已按值排好序

    D

    必须以顺序方式存储，且数据元素已按值排好序


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

  • 第24题：

    问答题
    假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找。假定每个元素的查找概率相等，求查找成功时的平均查找长度。

    正确答案： 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；
    但最后一层未满，不能用8×4，只能用5×4=20次，
    所以ASL＝1/12（17＋20）＝37/12≈3.08
    解析： 暂无解析

相关内容