既希望较快地查找,又便于线性表动态变化的查找方法是______。A.顺序查找B.折半查找C.Hash查找D.索

Question

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

A．顺序查找

B．折半查找

C．Hash查找

D．索引顺序查找

Answer 1

正确答案：D
解析：查找是根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素的过程。若表中存在这样的记录，则查找成功，此时或者给出整个记录的信息，或者给出记录在查找表中的位置；若表中不存在关键字等于给定值的记录。则称查找不成功。此时查找结果用一个“空”记录或“空”指针表示。
  (a)顺序查找。从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用。
  (b)折半查找。设查找表的元素存储在一维数组r[1..n]中，首先将待查的key值与表r中间位置上(下标为mid)的记录的关键字进行比较，若相等，则查找成功；若key＞r[mid].key，则说明待查记录只可能在后半个子表r[mid+1…n](注意：是mid+1，而不是mid)中，下一步应在后半个子表中再进行折半查找，若key  (c)索引顺序查找(又称分块查找)，是对顺序查找方法的一种改进，其性能介于顺序查找与折半查找之间。其基本思想是，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的，即后一块中所有记录的关键字均大于前一个块中最大的关键字；此外，还建立了一个索引表，索引表按关键字有序。因此，分块查找分两步，第一步在索引表中确定待查记录所在的块，第二步在块内顺序查找。