某一维数组中依次存放了数据元素12,23,30,38,41,52,54,76,85,在用折半(二分)查找方法(向上取整)查找元素54时,所经历“比较”运算的数据元素依次为()。
A.41,52,54
B.41,76,54
C.41,76,52,54
D.41,30,76,54
参考答案:B
解析:
[分析]: 本题考查数据结构基础知识。
设查找表的元素存储在一维数组r[1..n]中,那么在表中的元素已经按关键字递增(或递减)的方式排序的情况下,进行折半查找的方法是:首先将待查元素的关键字(key)值与表r中间位置上(下标为mid)的记录的关键字进行比较,若相等,则查找成功。若key>r[mid].key,则说明待查记录只可能在后半个子表r[mid+1..n]中,下一步应在后半个子表中再进行折半查找:若key<r[mid].key,说明待查记录只可能在前半个子表 r[1..mid-1]中,下一步应在r的前半个子表中进行折半查找,这样通过逐步缩小范围,直到查找成功或子表为空时失败为止。 在题中,以中间元素41为界将数组元素分为12,23,30,38和52,54,76,85两部分,显然54在后半部分,该部分的中间元素为54(向下取整)或76(向上取整),在52、54构成的子查找表中,向上取整的中间元素为54,因此查找元素54所经历“比较”运算的数据元素依次为41,76,54。