14. 对 50 个记录的有序表作折半查找,当查找失败时,至少需要比较( )次关键字。 A.4 B.5 C.6 D.7
时间: 2024-03-31 17:37:44 浏览: 14
对于 $n$ 个记录的有序表作折半查找,当查找失败时,需要比较的次数为 $\lceil \log_2(n+1)\rceil$。其中,$\lceil x \rceil$ 表示不小于 $x$ 的最小整数。因此,对于 50 个记录的有序表,查找失败时至少需要比较 $\lceil \log_2(50+1)\rceil = \lceil 5.67\rceil = 6$ 次关键字。因此,答案为 C.6。
相关问题
对22个记录的有序表作折半查找,当查找失败时,至少需要比较_次关键字。
对于有序表的折半查找,每次比较都可以将查找区间缩小一半,因此其时间复杂度为 O(log n)。在最坏情况下,也就是查找失败时,需要将查找区间缩小到只有一个元素时,才能确定元素不存在于有序表中。
根据折半查找的思想,每次将查找区间的中间位置与目标关键字进行比较,如果中间位置的关键字小于目标关键字,则说明目标元素可能在中间位置的右侧,否则在左侧。通过这种方式不断缩小查找区间,最终可以确定目标元素的位置或者不存在于有序表中。
由于有序表中共有 22 个记录,而折半查找每次可以将查找区间缩小一半,因此在最坏情况下,需要将查找区间缩小到只有一个元素,也就是需要进行 log2(22) ≈ 4.5 次比较。因此,至少需要比较 5 次关键字。
具有12个关键字的有序表画出折半查找判定树
折半查找的判定树可以使用递归的方式来构建。首先,我们需要找到中间元素,然后根据中间元素与目标元素的大小关系,判断目标元素在左侧还是右侧子数组中。然后,我们对相应的子数组进行递归搜索,直到找到目标元素或者确定目标元素不存在。
假设关键字为:1, 3, 4, 6, 7, 8, 10, 13, 14, 16, 17, 20
折半查找的判定树如下所示:
```
[10]
/ \
[4] [16]
/ \ / \
[1] [7] [13] [20]
/ \ / \
[6] [8][14] [17]
/
[3]
```
其中,树的节点表示一个子问题,包括目标元素的可能位置和已经排除的位置。根节点表示整个数组,左子树表示左半部分数组,右子树表示右半部分数组。每个节点有两个子节点,分别表示目标元素可能存在于左半部分或右半部分。如果目标元素不存在于当前子数组中,则将该子数组排除,并且不再对该子数组进行搜索。最终,如果找到目标元素,则返回其下标;否则,返回不存在的信息。