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

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

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

aslbn≈LG（n1）-1

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

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

至少需要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，關(guān)鍵字不存在