🏷️ 知识点：数组查找
下列数据结构中，不适合直接使用折半查找的是（）
I 有序链表 II 无序数组 III 有序静态链表 IV 无序静态链表
A. 仅 1、II B. 仅 II、IV C. 仅、II、IV D. I、II、III、IV
[tag_link]
正确答案：D
折半查找需要数据结构支持随机访问才能发挥作用，对于链表，无法随机访问其中某个下标的元素。
下列选项中，不能构成折半查找中关键字比较序列的是（）。
A. 500,200,450,180 B. 500,450,200,180 C. 180,500,200,450 D. 180,200,500,450
[tag_link] 正确答案：A画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。显然，选项 A 的查找路径不满足。
已知查找表中有 400 个元素，查找元素概率相同。采用分块查找法且均匀分块。若采用顺序查找法确定元素所在块，且块内也采用顺序查找法，为效率最高，每块包含元素应为（ ）。
A. 8 B. 10 C. 20 D. 25
[tag_link]
正确答案：C
设块大小为m，块数为mn。查找复杂度为O(n/m+m)。根据高中数学的知识可以得知，m=n =20时，查找复杂度最低，所以m=20。
在关键字随机分布的情况下，用二分查找树的方法进行查找，其平均查找长度与（ ）量级相当。
A. 顺序查找 B. 折半查找 C. 分块查找 D. 散列查找
[tag_link]
正确答案：B
在关键字随机分布的情况下，构建的二分查找树（BST）通常趋于平衡，树的高度平均为 O(log n)，其中 n 是关键字的数量。 因此，使用二分查找树进行查找的平均查找长度（ASL）量级为 O(log n)。 折半查找（即二分查找）在有序数组上进行，每次比较后将搜索范围减半，其平均查找长度也是 O(log n) 量级。 顺序查找的 ASL 为 O(n)，分块查找的 ASL 介于顺序查找和折半查找之间，通常优于 O(n) 但不如 O(log n)，而散列查找在理想情况下 ASL 为 O(1)。 因此，二分查找树在随机分布下的平均查找长度与折半查找同属于对数量级。
对含有 600 个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（ ）。
A. 9 B. 10 C. 30 D. 300
[tag_link]
正确答案：B
在含有 600 个元素的有序表进行折半查找时，其关键字比较次数最多的情况发生在目 标元素不在表中的情况下。在这种情况下，折半查找会进行到最后一步，直到左边界和右边界 相遇。因此，关键字比较次数最多的情况是在查找过程中遍历整个表的情况。在进行折半查找 时，每次比较会将查找范围缩小一半，直到找到目标元素或确定目标元素不在表中。对于 600 个元素的有序表，因为log2 (600)≈9.22，采用 9 次遍历并不能查找完成，因此需要 10 次查找。 本题答案选 B。
折半查找有序表 (2,10,25,35,40,65,70,75,81,82,88,100)，若查找元素 75，需依次与表中元素（ ）进行比较。
A. 65,82,75 B. 70,82,75 C. 65,81,75 D. 65,81,70,75
[tag_link]
正确答案：D
考查折半查找的查找过程。 有序表长度为 12，依据折半查找的思想：
- 第一次查找第 个元素，即 65； >
- 第二次查找第 个元素，即 81； >
- 第三次查找第 个元素，即 70； >
- 第四次查找第 个元素，即 75。 >
比较的元素依次为 65、81、70、75。 > 对应的折半查找判定树如下图所示。 >
` 65
/ \
25 81
/ \ / \
2 35 70 88
/ \ \ / \
10 40 75 82 100
`>已知一个长度为16的顺序表 L, 其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在 的元素，则关键字的比较次数最多是()。
A.4 B.5 C.6 D.7
[tag_link]
正确答案：B
折半查找 在查找成功时进行的关键字比较次数最多为 ⌊ l o g 2 n ⌋ + 1 ，即判定树的高度；
折半查找法在查找不成功时进行的关键字比较次数最多为 ⌊ l o g 2 n ⌋ + 1 。
题中 n = 16 ,因此最多比较 ⌊ l o g 2 16 ⌋ + 1 = 5 次。
也可以画出草图求解。
在有 n(n>1000) 个元素的升序数组 A 中查找关键字 x。查找算法的伪代码如下所示。
k = 0;
while (k < n 且 A[k] < x) k = k + 3;
if (k < n 且 A[k] == x) 查找成功；
else if (k - 1 < n 且 A[k - 1] == x) 查找成功；
else if (k - 2 < n 且 A[k - 2] == x) 查找成功；
else 查找失败；
本算法与折半查找算法相比，有可能具有更少比较次数的情形是（）
A. 当 x 不在数组中 B. 当 x 接近数组开头处 C. 当 x 接近数组结尾处 D. 当 x 位于数组中间位置
[tag_link]
正确答案：B
此题为送分题。该程序采用跳跃式的顺利查找法查找升序数组中的 X, 显然是 x 越靠前，比较次数才会越少。