违法和不良信息举报 联系客服
免费注册 登录

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

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

快速分类法

B

斐波那契查找法

C

二分法

D

顺序查找法

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

第1题：

● 折半（二分）查找方法对查找表的要求是（42）。

（42）

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

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

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

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


正确答案：C


第2题：

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

A.元素按值有序

B.构采用顺序存储结

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

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


正确答案：C

第3题：

对线性表进行折半查找时,要求线性表必须_______。

A、以顺序方式存储

B、以链式方式存储

C、以顺序方式存储且表中元素按关键字有序排列

D、以链式方式存储且表中元素按关键字有序排列


正确答案：C

第4题：

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

A．55

B．5

C．39/8

D．19/4


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

第5题：

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

某顺序存储的表格，其中有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：③

第6题：

在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。

A.相同，元素的存储顺序与逻辑顺序一致

B.相同，但其元素的存储顺序可以与逻辑顺序不一致

C.不同，但元素的存储顺序与逻辑顺序一致

D.不同，且其元素的存储顺序可以与逻辑顺序不一致


正确答案：A
本题考查知识点是线性表的顺序存储结构。线性表的顺序存储结构具有两个基本特点：1.线性表中所有元素所占的存储空间是连续的;2.线性表中各元素在存储空间中是按逻辑顺序依次存放的。

第7题：

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

A、以顺序方式存储

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

C、以链接方式存储

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


正确答案:B

第8题：

对长度为10的顺序表进行查找,若查找前面5个元素的概率相同,均为1／8,查找后面5个元素的概率相同,均为3／40,则查找任一元素的平均查找长度为()。

A.5.5

B.5

C.39/8

D.19/4


参考答案：C

第9题：

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

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

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

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

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


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

第10题：

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

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

A．25000

B．30000

C．45000

D．90000


正确答案：C

更多相关问题
相关内容