经典指数          
原因
3109
浏览数
0
收藏数
 

设有五个数据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。 do       for        if          repeat       while q0 p1 q1 p2 q2 p3 q3 p4       q4 p5 q5 (1) 试画出对该有序表采用顺序查找时的判定树和采用折半查找时的判定树。 (2) 分别计算顺序查找时的查找成功和不成功的平均查找长度,以及折半查找时的查找成功和不成功的平均查找长度。 (3) 判定是顺序查找好?还是折半查找好?

     举报   纠错  
 
切换
1 个答案
解析: (1)顺序查找判定树 (2)ASL 顺序成功 =(1p1 +2p2+3p3+4p4+5p5)=0.97 ASL 折半成功 = (1p3+2(p1+p4 )+3(p2+p5)=1.04 ASL 折半失败 = (2q0+3q1+3q2+2q3+3q4+3q5)=1.30 ASL 顺序失败 = (1q0+2q1+3q2+4q3+5q4+5q5)=1.07 (3)本题中顺序检索好。
 
切换
撰写答案
扫描后移动端查看本题