具有12个关键字的有序表中,对每个关键字的查找概率相同,折半查找算法查找成功的平均查找长度为(),折半查找查找失败的平均查找长度为()。 37/12 B .35/12 C .39/13 D. 49/13,这个是怎么计算的
时间: 2024-03-31 22:38:16 浏览: 115
对于有序表的折半查找算法,成功的平均查找长度为`log2(n+1)-1`,失败的平均查找长度为`log2(n+1)`,其中`n`为表长。
根据题意可知,有序表中有12个关键字,所以`n=12`。因为每个关键字的查找概率相同,所以成功和失败的概率都是`1/12`。
将`n`和成功、失败的概率代入公式可得:
成功的平均查找长度 = `log2(12+1)-1 ≈ 2.58496`
失败的平均查找长度 = `log2(12+1) ≈ 3.58496`
所以答案为B. 35/12。
相关问题
具有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]
```
其中,树的节点表示一个子问题,包括目标元素的可能位置和已经排除的位置。根节点表示整个数组,左子树表示左半部分数组,右子树表示右半部分数组。每个节点有两个子节点,分别表示目标元素可能存在于左半部分或右半部分。如果目标元素不存在于当前子数组中,则将该子数组排除,并且不再对该子数组进行搜索。最终,如果找到目标元素,则返回其下标;否则,返回不存在的信息。
在有序表中利用折半查找查找关键字并输出查找位置
折半查找(二分查找)是一种在有序表中查找关键字的算法,其基本思想是每次将查找区间缩小一半,直到找到目标元素或者区间为空为止。
假设我们要在一个有序表arr中查找关键字key,初始时查找区间为整个表,即[0, n-1],其中n为表中元素个数。具体的查找过程如下:
1. 将查找区间的下标范围[left, right]初始化为[0, n-1]。
2. 计算区间中间位置mid,即mid = (left + right) / 2。
3. 如果arr[mid]等于key,则查找成功,返回mid。
4. 如果arr[mid]大于key,则说明key可能在左半边,将查找区间缩小为[left, mid-1]。
5. 如果arr[mid]小于key,则说明key可能在右半边,将查找区间缩小为[mid+1, right]。
6. 重复步骤2~5,直到找到目标元素或者区间为空为止。
下面是一个示例代码实现:
```python
def binary_search(arr, key):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == key:
return mid
elif arr[mid] > key:
right = mid - 1
else:
left = mid + 1
return -1 # 没有找到目标元素
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 5
pos = binary_search(arr, key)
print("关键字位置:", pos)
```
输出结果为:
```
关键字位置: 4
```
说明在有序表arr中,关键字5位于下标为4的位置。