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

题目

判断题

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

对

错

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

相似问题和答案

第1题：

对具有n个元素的有序序列进行二分查找时，(61)。

A．元素位置越靠近序列前端，查找该元素所需的比较次数越少

B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]

C．查找元素所需的比较次数与元素的位置无关

D．元素位置越靠近序列后端，查找该元素所需的比较次数越少

正确答案：B
解析：二分查找过程是：以处于中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或查找区间的大小为零时(表明查找不成功)为止。对于有11个元素的有序表进行二分查找的过程可用一个二叉树表示，如图6-12所示(结点中的数字表示元素在序列中的序号)。

图6-12所示二叉树表明，若需要查找序列中的第6个元素，则仅需一次元素间的比较。若需查找第3个或第9个元素，则分别需要两次比较。依此类推，查找第1、4、7、10个元素时，分别需要三次比较，查找第2、5、 8、11个元素时，分别需要四次比较。因此，查找元素所需的比较次数与元素在序列中的位置是有关的。显然，选项A或D的说法也是错误的。若序列中有n个元素，则根据二分查找法构造的二叉树的高度不会超过[log₂(n+1)]，因此选项B是正确的。

第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题：

在索引顺序表中查找一个元素,可用的且最快的方法是()。

A.用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找

B.用顺序查找法确定元素所在块，再用二分查找法在相应块中查找

C.用二分查找法确定元素所在块，再用顺序查找法在相应块中查找

D.用二分查找法确定元素所在块，再用二分查找法在相应块中查找

参考答案：C

第4题：

● 已知一个线性表（16, 25, 35, 43, 51, 62, 87, 93），采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则构造的哈希表为（57），在该散列表上进行等概率成功查找的平均查找长度为（58）（为确定记录在查找表中的位置，需和给定关键字值进行比较的次数的期望值称为查找算法在查找成功时的平均查找长度）。

正确答案：C,A

第5题：

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

A、8

B、9

C、10

D、11

正确答案：D

第6题：

设查找表为(50,60,75,85,96,98,105,110,120,130)

(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较?

(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到?

(3)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)。

参考答案(1)3次
　　(2 )4次
　　(3)

第7题：

对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的______个元素进行比较操作(包括与第5个元素的比较)。

A．5

B．4

C．3

D．2

A．

B．

C．

D．

正确答案：B

第8题：

对于长度为11的顺序存储的有序表，若采用折半查找(向下取整)，则找到第5个元素需要与表中的(39)个元素进行比较操作(包括与第5个元素的比较)。

A．5

B．4

C．3

D．2

正确答案：B
解析：本题考查折半(二分)查找。折半查找判定树可以用于描述折半查找过程，在有11个元素的有序顺序表中进行折半查找的判定树如下图所示，结点中的数字表示元素的序号。该判定树表示，首先将待查找的元素与表中的中间元素比较(第6个元素)，若相等，则找到，若大于中间位置元素，则下一步到后半个子表进行折半查找，否则，下一步到前半个子表进行折半查找。因此，要找表中的第5个元素，需要与第6、3、4和5个元素依次比较，查找成功。

第9题：

●对n 个元素的有序表A[1．．n]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为__(58)。

(58)

A． n

B． (n+1)／2

C． lOg2 n

D． n2

正确答案：B

第10题：

在下列查找方法中，平均查找长度与元素的个数无关的方法是(53)。

A．顺序查找法

B．折半查找法

C．散列表查找法

D．无论哪种查找法

正确答案：C
解析：顺序查找方法和折半查找方法的平均查找长度都与元素的个数有关，由于散列结构是由事先准备好的散列函数关系与处理＞中突的方法来确定数据元素在散列表中的存储位置的，因此散列表查找方法的平均查找长度与元素的个数无关。故选C。

在1000个大小有序的列表中查找某给定元素。用顺序查找法至多需要比较1000次（平均需要500次）可以找到该元素或确定列

题目

相似问题和答案

更多相关问题

相关内容