admin 管理员组文章数量: 1086019
2024年3月14日发(作者：js定义全局变量)
第9章 查找
教材中练习题及参考答案
1. 设有5个数据do、for、if、repeat、while，它们排在一个有序表中，其查找概率分别
是p
1
=0.2，p
2
=0.15，p
3
=0.1，p
4
=0.03，p
5
=0.01。而查找它们之间不存在数据的概率分别为
q
0
=0.2，q
1
=0.15，q
2
=0.1，q
3
=0.03，q
4
=0.02，q
5
=0.01，该有序表如下：
do
q
0
p
1
for
q
1
p
2
if
q
2
p
3
repeat
q
3
p
4
while
q
4
p
5
q
5
（1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。
（2）分别计算顺序查找的查找成功和不成功的平均查找长度。
（3）分别计算折半查找的查找成功和不成功的平均查找长度。
答：（1）对该有序表分别采用顺序查找和折半查找时的判定树分别如图9.2和9.3所示。
（2）对于顺序查找，成功查找到第i个元素需要i次比较，不成功查找需要比较的次
数为对应外部结点的层次减1：
ASL
成功
=(1p
1
+2p
2
+3p
3
+4p
4
+5p
5
)=0.97。
ASL
不成功
=(1q
0
+2q
1
+3q
2
+4q
3
+5q
4
+5q
5
)=1.07。
（3）对于折半查找，成功查找需要比较的次数为对应内部结点的层次，不成功查找需
要比较的次数为对应外部结点的层次减1：
ASL
成功
=(1p
3
+2(p
1
+p
4
)+3(p
2
+p
5
))=1.04。
ASL
不成功
=(2q
0
+3q
1
+3q
2
+2q
3
+3q
4
+3q
5
)=1.3。
do
q
0
(-∞,do)
q
1
(do,for)
q
2
(for,if)
q
3
p
1
for
p
2
p
3
p
4
repeat
(if,repeat)
while
p
5
if
q
4
(repeat,while)
(while,∞)
q
5
2 数据结构教程学习指导
图
9.2
有序表上顺序查找的判定树
if
p
1
do
p
2
q
0
(-∞,do)
for
q
3
(if,repeat)
q
4
q
1
(do,for)
q
2
(for,if)
(repeat,while)
p
3
repeat
p
4
p
5
while
q
5
(while,∞)
图
9.3
有序表上折半查找的判定树
2. 对于A[0..10]有序表，在等概率的情况下，求采用折半查找法时成功和不成功的平
均查找长度。对于有序表（12，18，24，35，47，50，62，83，90，115，134），当用折半
查找法查找 90时，需进行多少次查找可确定成功；查找47时需进行多少次查找可确定成
功；查找100时，需进行多少次查找才能确定不成功。
答：对于A[0..10]有序表构造的判定树如图9.4（a）所示。因此有：
ASL
成功
=
11224344
=3
11
4384
=3.67
12
ASL
不成功
=
对于题中给定的有序表构造的判定树如图9.4（b）所示。查找 90时，关键字比较次
序是50、90，比较2次。查找47时，关键字比较次序是50、24、35、47，比较4次。查
找100时，关键字比较次序是50、90、115，比较3次。
5 50
2 8 24 90
0 3 6 9 12 35 62 115
1 4 7 10 18 47 83 134
（a）
图
9.4
两棵判定树
（b）
3. 有以下查找算法：
int fun(int a[],int n,int k)
版权声明：本文标题：数据结构教程李春葆课后答案第9章查找 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1710383170a570615.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论