平均不成功查找次數(shù)怎么求 數(shù)據(jù)結(jié)構(gòu)中，查找不成功的平均查找長(zhǎng)度怎么求？

二叉排序樹(shù)的不成功的平均查找長(zhǎng)度怎么求？求檢索不成功時(shí)的平均查找次數(shù)，鏈?zhǔn)教幚頉_突怎么求不成功的平均查找長(zhǎng)度？哈希表查找失敗平均次數(shù)計(jì)算，哈希函數(shù)鏈地址法查找不成功的平均長(zhǎng)度如何求？？數(shù)據(jù)結(jié)構(gòu)中，查找不成功的平均查找長(zhǎng)度怎么求？

本文導(dǎo)航

• 二叉排序樹(shù)的不成功的平均查找長(zhǎng)度怎么求?
• 求檢索不成功時(shí)的平均查找次數(shù)
• 鏈?zhǔn)教幚頉_突怎么求不成功的平均查找長(zhǎng)度
• 哈希表查找失敗平均次數(shù)計(jì)算
• 哈希函數(shù)鏈地址法查找不成功的平均長(zhǎng)度如何求？？
• 數(shù)據(jù)結(jié)構(gòu)中，查找不成功的平均查找長(zhǎng)度怎么求？

二叉排序樹(shù)的不成功的平均查找長(zhǎng)度怎么求?

找到所有的外結(jié)點(diǎn)，也就是查找失敗的點(diǎn)，然后計(jì)算ASL

就你的BST，結(jié)果如下：

15的左右子樹(shù)都為空，也就是左右子樹(shù)都是外結(jié)點(diǎn)，失敗時(shí)需要比較62、30、15一共3次

48的左右子樹(shù)都為空，也就是左右子樹(shù)都是外結(jié)點(diǎn)，失敗時(shí)需要比較62、30、15、48一共4次

56的右子樹(shù)為空，也就是右子樹(shù)是外結(jié)點(diǎn)，失敗時(shí)需要比較62、30、56一共3次

74的左右子樹(shù)都為空，也就是左右子樹(shù)都是外結(jié)點(diǎn)，失敗時(shí)需要比較62、74一共2次

因此外結(jié)點(diǎn)總數(shù)為2 *3 + 1 = 7 （其實(shí)這個(gè)數(shù)量一定是關(guān)鍵字個(gè)數(shù)加1）

所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3

求檢索不成功時(shí)的平均查找次數(shù)

鏈?zhǔn)教幚頉_突怎么求不成功的平均查找長(zhǎng)度

一、分析問(wèn)題：這是一個(gè)建立哈希函數(shù)的問(wèn)題。　哈希表中元素是由哈希函數(shù)確定的。將數(shù)據(jù)元素的關(guān)鍵字K作為自變量，通過(guò)一定的函數(shù)關(guān)系（稱(chēng)為哈希函數(shù)），計(jì)算出的值，即為該元素的存儲(chǔ)地址。表示為： 　　Addr = H（key） 　　為此在建立一個(gè)哈希表之前需要解決兩個(gè)主要問(wèn)題： 　?、艠?gòu)造一個(gè)合適的哈希函數(shù) 　　均勻性 H（key）的值均勻分布在哈希表中； 　　簡(jiǎn)單　以提高地址計(jì)算的速度 　?、茮_突的處理 　　沖突：在哈希表中，不同的關(guān)鍵字值對(duì)應(yīng)到同一個(gè)存儲(chǔ)位置的現(xiàn)象。即關(guān)鍵字K1≠K2，但H（K1）= H（K2）。均勻的哈希函數(shù)可以減少?zèng)_突，但不能避免沖突。發(fā)生沖突后，必須解決；也即必須尋找下一個(gè)可用地址。 本題是用除留余數(shù)法構(gòu)造散列函數(shù)（哈希函數(shù)），用鏈接法（拉鏈法）處理沖突。1、除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址。 　　H(key)=key MOD p (p<=m)2、拉鏈法：拉出一個(gè)動(dòng)態(tài)鏈表代替靜態(tài)順序存儲(chǔ)結(jié)構(gòu)，可以避免哈希函數(shù)的沖突，不過(guò)缺點(diǎn)就是鏈表的設(shè)計(jì)過(guò)于麻煩，增加了編程復(fù)雜度。此法可以完全避免哈希函數(shù)的沖突。確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱(chēng)為查找算法在查找成功時(shí)的平均查找長(zhǎng)度(Average Search Length)，ASL成功。 　　對(duì)于含有n個(gè)數(shù)據(jù)元素的查找表，查找成功的平均查找長(zhǎng)度為：ASL=∑PiCi (i=1,2,3,…,n),可以簡(jiǎn)單以數(shù)學(xué)上的期望來(lái)這么理解。其中：Pi 為查找表中第i個(gè)數(shù)據(jù)元素的概率，Ci為找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過(guò)的次數(shù)。 　　在查找表中查找不到待查元素，但是找到待查元素應(yīng)該在表中存在的位置的平均查找次數(shù)稱(chēng)為查找不成功時(shí)的平均查找長(zhǎng)度，ASL不成功。二、解答問(wèn)題散列地址空間為HT[11] p=11所以32%11＝10......80%11=3。所以散列地址為（10，1，7，8，4，6，3，3，7，4，5，3） ASL=∑PiCi (i=1,2,3,…,n),在這里n=12p1=1/12,C1=0;P2=1/12,C2=1;然后你自已求解吧

哈希表查找失敗平均次數(shù)計(jì)算

查找失敗就是說(shuō)要找的那個(gè)值沒(méi)有在哈希表里面。你放上來(lái)的題沒(méi)給哈希函數(shù)沒(méi)法給你分析，我給你舉個(gè)例： 假如你的哈希函數(shù)是key=x mod 10，填充后的哈希表如下所示： 0 1 2 3 4 5 6 7 8 9 10 1110 1 12 15 25 18 19 29 如果你要查找這個(gè)哈希表里面有沒(méi)有0這個(gè)數(shù)，那你就會(huì)去序號(hào)0下面找，這個(gè)地方被10填充了，那就往后找，后面依次是1、12，都不等于0，再往后就為空，說(shuō)明這個(gè)表里面沒(méi)有0?？偣膊檎伊?次。如果你要查找這個(gè)哈希表里面有沒(méi)有2這個(gè)數(shù)，那你就會(huì)去序號(hào)2下面找，做一次比較，下面是12，不相等，往后面找，后面是空，那查找結(jié)束?？偣膊檎伊?次。如果你要找29，那就會(huì)在序號(hào)9下面找，這里被19填充了，于是往后，找到29。總共查找了2次。所以，每次查找不成功的查找長(zhǎng)度就等于從序號(hào)找到第一個(gè)空的格子的距離。在我舉的這個(gè)例子里面，ASL=（4+3+2+1+1+3+2+1+4+3+2+1）/12 不知道你明白了沒(méi)~

哈希函數(shù)鏈地址法查找不成功的平均長(zhǎng)度如何求？？

查找不成功，即找不到要查找的數(shù)。所以，要遍歷完一個(gè)鏈表才能確定。

對(duì)于1，3，6，7，10，11鏈表要分別查找4，2，2，1，2，1次，其它鏈表為0次。所以，總的查找次數(shù)為4+2+2+1+2+1=12次。平均查找12/13次。

數(shù)據(jù)結(jié)構(gòu)中，查找不成功的平均查找長(zhǎng)度怎么求？

查找不成功的ASL的大概意思就是從散列表的第一個(gè)位置開(kāi)始依次向后比較，遇到空的位置或者直到表尾都沒(méi)有與之相匹配的就算查找失敗，然后從第二個(gè)位置再進(jìn)行以上操作，以此類(lèi)推，一直到第n個(gè)位置（表的最后一個(gè)位置）。這時(shí)候，從表頭到表尾的每一個(gè)位置都會(huì)有一個(gè)比較失敗的次數(shù)，將他們依次相加后除以表長(zhǎng)，得到的就是查找失敗的平均查找長(zhǎng)度（ASL）

與查找成功相比，查找失敗在計(jì)算ASL時(shí)，是將散列表中的所有位置都計(jì)算在內(nèi)，遇到空位置時(shí)比較次數(shù)就為1；而查找成功時(shí)的ASL只考慮所給元素的位置，不考慮空位置。