有序表数据 do,for,if,repeat,while,其查找成功概率分别为0.2,0.15,0.14,0.03,0.01,回答如下问题: 1)画出对该有序表采用顺序查找和折半查找的判定树。 2)分别计算顺序查找时的查找成功和折半查找时的查找成功的平均查找长度。 3)判定折半查找好还是顺序查找好。
时间: 2024-02-17 12:00:57 浏览: 23
好的,我可以回答你的问题。
1)对于该有序表,采用顺序查找和折半查找的判定树如下所示:
顺序查找判定树:
```
┌──[do]───┐
┌──[for]───┐ ├──[if]───┐
[do] [for] [if] [repeat]
| | | |
0.2 0.35 0.49 0.52
```
折半查找判定树:
```
┌──[do]───┐
┌──[for]───┐ ├──[if]───┐
┌──[do] [if] [repeat] [while]
[do] [for] | | |
| | 0.14 0.29 0.43
0.2 0.15
```
2)顺序查找时的查找成功的平均查找长度为:
```
ASLs = 0.2*1 + 0.15*2 + 0.14*3 + 0.03*4 + 0.01*5 = 0.885
```
折半查找时的查找成功的平均查找长度为:
```
ASLb = log2(5)/2 = 0.86
```
其中,ASLs表示顺序查找时的平均查找长度,ASLb表示折半查找时的平均查找长度。
3)通过比较ASLs和ASLb,可以发现折半查找的平均查找长度更小,也就是说折半查找比顺序查找更好。因此,对于该有序表,采用折半查找更为适合。
相关问题
设有5个关键字do,for,if,repeat,while,他们存放在一个有序顺序表中,其查找概率分别是p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01,而查找各关键字不存在的概率分别为q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5=0.01。
根据您提供的信息,可以计算出每个关键字的查找成功概率pi和查找失败概率qi,如下所示:
| 关键字 | 查找成功概率 pi | 查找失败概率 qi |
| ------ | --------------- | --------------- |
| do | 0.2 | 0.8 |
| for | 0.15 | 0.85 |
| if | 0.1 | 0.9 |
| repeat | 0.03 | 0.97 |
| while | 0.01 | 0.99 |
接下来,可以根据二分查找算法对这个有序顺序表进行查找。二分查找是一种基于比较目标值和中间值的大小来缩小查找范围的算法。
具体实现步骤如下:
1. 初始化左右边界l和r,分别为0和4,表示查找范围为整个有序顺序表。
2. 计算中间位置mid,即mid=(l+r)/2。
3. 将中间位置mid的关键字与目标关键字进行比较,如果相等,则查找成功,返回mid。如果目标关键字小于中间位置的关键字,则在左半边继续查找,即令r=mid-1;否则在右半边查找,即令l=mid+1。
4. 重复第2步和第3步,直到找到目标关键字或者查找范围缩小到0为止。
需要注意的是,在二分查找过程中,每次比较都有可能失败。如果失败,则需要在失败的位置上插入目标关键字,同时更新每个关键字的查找概率和失败概率。
这个算法的时间复杂度为O(log n),其中n为有序顺序表的长度。如果有很多插入操作,还需要进行动态调整,以保证每个关键字的查找概率和失败概率的准确性。
分别使用for循环,while循环,do循环求1到100之间能被3整除的的整数和
使用for循环求1到100之间能被3整除的整数和:
```
sum = 0
for i in range(1, 101):
if i % 3 == 0:
sum += i
print(sum)
```
使用while循环求1到100之间能被3整除的整数和:
```
sum = 0
i = 1
while i <= 100:
if i % 3 == 0:
sum += i
i += 1
print(sum)
```
使用do循环求1到100之间能被3整除的整数和:
```
sum = 0
i = 1
repeat
if i % 3 == 0 then
sum = sum + i
end
i = i + 1
until i > 100
print(sum)
```
注意:以上三段代码分别使用了Python、Java和Lua语言编写,可以根据需要选择其中一种语言来运行。