平均不成功查找次數(shù)怎么求 數(shù)據(jù)結(jié)構中，查找不成功的平均查找長度怎么求？
二叉排序樹的不成功的平均查找長度怎么求？求檢索不成功時的平均查找次數(shù)，鏈式處理沖突怎么求不成功的平均查找長度？哈希表查找失敗平均次數(shù)計算，哈希函數(shù)鏈地址法查找不成功的平均長度如何求？？數(shù)據(jù)結(jié)構中，查找不成功的平均查找長度怎么求？
本文導航
- 二叉排序樹的不成功的平均查找長度怎么求?
- 求檢索不成功時的平均查找次數(shù)
- 鏈式處理沖突怎么求不成功的平均查找長度
- 哈希表查找失敗平均次數(shù)計算
- 哈希函數(shù)鏈地址法查找不成功的平均長度如何求？？
- 數(shù)據(jù)結(jié)構中，查找不成功的平均查找長度怎么求？
二叉排序樹的不成功的平均查找長度怎么求?
找到所有的外結(jié)點，也就是查找失敗的點，然后計算ASL
就你的BST，結(jié)果如下：
15的左右子樹都為空，也就是左右子樹都是外結(jié)點，失敗時需要比較62、30、15一共3次
48的左右子樹都為空，也就是左右子樹都是外結(jié)點，失敗時需要比較62、30、15、48一共4次
56的右子樹為空，也就是右子樹是外結(jié)點，失敗時需要比較62、30、56一共3次
74的左右子樹都為空，也就是左右子樹都是外結(jié)點，失敗時需要比較62、74一共2次
因此外結(jié)點總數(shù)為2 *3 + 1 = 7 （其實這個數(shù)量一定是關鍵字個數(shù)加1）
所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3
求檢索不成功時的平均查找次數(shù)
鏈式處理沖突怎么求不成功的平均查找長度
一、分析問題：這是一個建立哈希函數(shù)的問題?！」１碇性厥怯晒：瘮?shù)確定的。將數(shù)據(jù)元素的關鍵字K作為自變量，通過一定的函數(shù)關系（稱為哈希函數(shù)），計算出的值，即為該元素的存儲地址。表示為： Addr = H（key） 為此在建立一個哈希表之前需要解決兩個主要問題： ?、艠嬙煲粋€合適的哈希函數(shù) 均勻性 H（key）的值均勻分布在哈希表中； 簡單 以提高地址計算的速度 ?、茮_突的處理 沖突：在哈希表中，不同的關鍵字值對應到同一個存儲位置的現(xiàn)象。即關鍵字K1≠K2，但H（K1）= H（K2）。均勻的哈希函數(shù)可以減少沖突，但不能避免沖突。發(fā)生沖突后，必須解決；也即必須尋找下一個可用地址。 本題是用除留余數(shù)法構造散列函數(shù)（哈希函數(shù)），用鏈接法（拉鏈法）處理沖突。1、除留余數(shù)法：取關鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)為哈希地址。 H(key)=key MOD p (p<=m)2、拉鏈法：拉出一個動態(tài)鏈表代替靜態(tài)順序存儲結(jié)構，可以避免哈希函數(shù)的沖突，不過缺點就是鏈表的設計過于麻煩，增加了編程復雜度。此法可以完全避免哈希函數(shù)的沖突。確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度(Average Search Length)，ASL成功。 對于含有n個數(shù)據(jù)元素的查找表，查找成功的平均查找長度為：ASL=∑PiCi (i=1,2,3,…,n),可以簡單以數(shù)學上的期望來這么理解。其中：Pi 為查找表中第i個數(shù)據(jù)元素的概率，Ci為找到第i個數(shù)據(jù)元素時已經(jīng)比較過的次數(shù)。 在查找表中查找不到待查元素，但是找到待查元素應該在表中存在的位置的平均查找次數(shù)稱為查找不成功時的平均查找長度，ASL不成功。二、解答問題散列地址空間為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ù)計算
查找失敗就是說要找的那個值沒有在哈希表里面。你放上來的題沒給哈希函數(shù)沒法給你分析，我給你舉個例： 假如你的哈希函數(shù)是key=x mod 10，填充后的哈希表如下所示： 0 1 2 3 4 5 6 7 8 9 10 1110 1 12 15 25 18 19 29 如果你要查找這個哈希表里面有沒有0這個數(shù)，那你就會去序號0下面找，這個地方被10填充了，那就往后找，后面依次是1、12，都不等于0，再往后就為空，說明這個表里面沒有0?？偣膊檎伊?次。如果你要查找這個哈希表里面有沒有2這個數(shù)，那你就會去序號2下面找，做一次比較，下面是12，不相等，往后面找，后面是空，那查找結(jié)束?？偣膊檎伊?次。如果你要找29，那就會在序號9下面找，這里被19填充了，于是往后，找到29。總共查找了2次。所以，每次查找不成功的查找長度就等于從序號找到第一個空的格子的距離。在我舉的這個例子里面，ASL=（4+3+2+1+1+3+2+1+4+3+2+1）/12 不知道你明白了沒~
哈希函數(shù)鏈地址法查找不成功的平均長度如何求？？
查找不成功，即找不到要查找的數(shù)。所以，要遍歷完一個鏈表才能確定。
對于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é)構中，查找不成功的平均查找長度怎么求？
查找不成功的ASL的大概意思就是從散列表的第一個位置開始依次向后比較，遇到空的位置或者直到表尾都沒有與之相匹配的就算查找失敗，然后從第二個位置再進行以上操作，以此類推，一直到第n個位置（表的最后一個位置）。這時候，從表頭到表尾的每一個位置都會有一個比較失敗的次數(shù)，將他們依次相加后除以表長，得到的就是查找失敗的平均查找長度（ASL）
與查找成功相比，查找失敗在計算ASL時，是將散列表中的所有位置都計算在內(nèi)，遇到空位置時比較次數(shù)就為1；而查找成功時的ASL只考慮所給元素的位置，不考慮空位置。
