首页 > 试题广场 >

既希望较快的查找又便于线性表动态变化的查找方法是 (

[单选题]

既希望较快的查找又便于线性表动态变化的查找方法是 (    )

  • 顺序查找
  • 折半查找
  • 索引顺序查找
  • 哈希法查找
推荐
选C
查找是根据给定的某个值,在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素的过程。若表中存在这样的记录,则查找成功,此时或者给出整个记录的信息,或者给出记录在查找表中的位置;若表中不存在关键字等于给定值的记录。则称查找不成功。此时查找结果用一个“空”记录或“空”指针表示。
(a)顺序查找。从表中的一端开始,逐个进行记录的关键字和给定值的比较,若找到一个记录的关键字与给定值相等,则查找成功;若整个表中的记录均比较过,仍未找到关键字等于给定值的记录,则查找失败。顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。
(b)折半查找。设查找表的元素存储在一维数组r[1..n]中,首先将待查的key值与表r中间位置上(下标为mid)的记录的关键字进行比较,若相等,则查找成功;若key>r[mid].key,则说明待查记录只可能在后半个子表r[mid+1…n](注意:是mid+1,而不是mid)中,下一步应在后半个子表中再进行折半查找,若key[mid].key,则说明待查记录只可能在前半个子表r[1…mid-1](注意:是mid-1,而不是mid)中,下一步应在前半个子表中再进行折半查找,这样通过逐步缩小范围,直到查找成功或子表为空时失败为止。在表中的元素已经按关键字递增(或递减)的方式排序的情况下,才可进行折半查找。折半查找比顺序查找的效率高,但它要求查找表进行顺序存储并且按关键字有序排列,因此,当对表进行元素的插入或删除时,需要移动大量的元素,所以折半查找适用于表不易变动且又经常进行查找的情况。
希望较快而不是很快,并且希望便于动态变化,这个用D而不是C,如果哈希法的存储不是链式,一般的情况下随着关键字的增多,冲突频繁发生,查找性能会急剧下降,其实并不是太利于动态变化,索引顺序由于一般块内可以无序,因此块内可以方便地减少增加。
编辑于 2017-08-16 17:42:53 回复(0)
从题目中可以看出数据结构为线性表。
1.顺序查找。便于线性表动态变化,但查找平均查找长度为O(n).
2.折半查找。平均查找长度O(logn),但由于要求线性表有序,所以不利于动态变化。
4.哈希查找。哈希查找时间为O(1),但由于哈希结构依赖于线性表,故不利于线性表动态变化。

3.索引顺序查找。当每块元素个数取到sqrt(n)时,平均查找长度最小为sqrt(n)+1。至于动态变化性能,我也不太清晰,等待大神解析。
发表于 2017-07-24 21:29:22 回复(1)
索引顺序查找又称为分块查找,效率在顺序查找和折半查找之间
发表于 2017-06-25 10:34:21 回复(0)
PYQ头像 PYQ
折半查找要求元素有序,因此面对动态变化时,性能会较差;索引顺序查找,又称分块查找,是对折半查找和顺序查找的改进——只要求索引表有序,块内可无序。查找时先对索引表使用二分查找,找到范围,然后在特定块中使用顺序查找。
发表于 2019-10-09 18:26:39 回复(0)
哈希表的链地址法不能实现动态查找吗?而且哈希查找的复杂度远远低于折半查找。
发表于 2018-10-23 21:59:18 回复(0)
三种静态查找算法的比较。http://blog.csdn.net/u011489043/article/details/78683856
发表于 2017-12-09 15:53:02 回复(0)
哈希法查找快但不利于线性变化
发表于 2019-03-05 17:20:36 回复(0)
索引顺序查找,即分块查找。
就类似于图书馆的索引,我们先找到几楼几馆,在找第几个书架,然后再找书。

分块查找是折半查找和顺序查找的一种改进方法,折半查找虽然具有很好的性能,但其前提条件时线性表顺序存储而且按照关键码排序,这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求,但查找效率很低。如果既要保持对线性表的查找具有较快的速度,又要能够满足表元素动态变化的要求,则可采用分块查找的方法。

由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时,只需将该节点调整到所在的块即可。 --- 百度百科
发表于 2018-12-08 21:03:35 回复(0)
便于线性表动态变化是什么意思呢?
发表于 2018-10-08 13:16:02 回复(0)

顺序查找在查找和变更时都低效;折半查找查找效率相对高一些,但因为按顺序存储,变更时效率仍然较低;哈希查找在数据较多时可能会遇到哈希碰撞。

发表于 2018-09-14 14:58:39 回复(0)
分块查找换了个“索引查找”的名字就看蒙了。。
发表于 2018-08-31 17:00:37 回复(0)
便于查找,有序 便于动态变化,意思就是方便增删 那就用有序树,或者有序堆
发表于 2018-07-15 12:05:26 回复(0)
分块查找是将元素进行分块,快间有序,并且快间以块内最大值(或最小)为索引,故又称索引查找。 而索引顺序查找就是快间也是顺序查找的分块查找。
发表于 2018-03-09 08:18:05 回复(0)

好吧。。。

发表于 2017-09-17 15:05:11 回复(0)