長度為10的表，采用順序查找法，平均查找長度ASL是。緊急，在線等？假設內部節(jié)點總數(shù)為n=2h-1，則決策樹是深度h=LG（n1）的完全二叉樹（深度h不包括外部節(jié)點）。樹的第k層上的節(jié)點數(shù)為2k-1，

長度為10的表，采用順序查找法，平均查找長度ASL是。緊急，在線等？

假設內部節(jié)點總數(shù)為n=2h-1，則決策樹是深度h=LG（n1）的完全二叉樹（深度h不包括外部節(jié)點）。樹的第k層上的節(jié)點數(shù)為2k-1，查找它們所需的比較次數(shù)為k，因此在等概率假設下，成功二叉搜索的平均長度如下：

aslbn≈LG（n1）-1

二叉搜索失敗時需要比較的關鍵字數(shù)不超過決策樹的深度，最壞情況下，成功比較的關鍵字數(shù)不超過決策樹的深度。二進制搜索的最差性能和平均性能非常接近。

對22個數(shù)據(jù)元素的有序順序表進行折半查找,當查找失敗時,至少需要比較()次關鍵字……急急急？

至少需要4次，第一次與第11位數(shù)字比較，mid=（0，21）/2=10，第二次與第5位數(shù)字比較，mid=（0，9）/2=4，第三次與第2位數(shù)字比較，mid=（0，3）/2=1，第三次與第二位數(shù)字比較，第四次與第一位數(shù)字比較，中間=（0，3）/2=1，關鍵字不存在