首页 > 试题广场 >

如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则

[单选题]

如果要求一个线性表既能较快的查找,又能适应动态变化的要求,则可采用(    )查找法。


  • 分块查找
  • 顺序查找
  • 折半查找
  • 基于属性
分块查找是折半查找和顺序查找的一种改进方法,折半查找虽然具有很好的性能,但其前提条件时线性表顺序存储而且按照关键码排序,这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求,但查找效率很低。如果既要保持对线性表的查找具有较快的速度,又要能够满足表元素动态变化的要求,则可采用分块查找的方法。
分块查找的速度虽然不如折半查找算法,但比顺序查找算法快得多,同时又不需要对全部节点进行排序。当节点很多且块数很大时,对索引表可以采用折半查找,这样能够进一步提高查找的速度。[1] 
分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时,只需将该节点调整到所在的块即可。在空间复杂性上,分块查找的主要代价是增加了一个辅助数组。
发表于 2017-07-31 16:47:52 回复(0)
分块查找是折半查找和顺序查找的一种改进方法,分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。 分块查找要求把一个数据分为若干块,每一块里面的元素可以是无序的,但是块与块之间的元素需要是有序的。
发表于 2019-09-11 00:43:02 回复(0)