平均不成功查找次數(shù)怎么求 數(shù)據(jù)結(jié)構中,查找不成功的平均查找長度怎么求?

盼一舊2022-08-22 21:06:061345

二叉排序樹的不成功的平均查找長度怎么求?求檢索不成功時的平均查找次數(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ù)的問題?!」1碇性厥怯晒:瘮?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只考慮所給元素的位置,不考慮空位置。

掃描二維碼推送至手機訪問。

版權聲明:本文由尚恩教育網(wǎng)發(fā)布,如需轉(zhuǎn)載請注明出處。

本文鏈接:http://codetoknow.com/view/53498.html

標簽: 數(shù)學
分享給朋友:

“平均不成功查找次數(shù)怎么求 數(shù)據(jù)結(jié)構中,查找不成功的平均查找長度怎么求?” 的相關文章

數(shù)學類專業(yè)有哪些 與數(shù)學專業(yè)相近的專業(yè)有哪些

數(shù)學類專業(yè)有哪些 與數(shù)學專業(yè)相近的專業(yè)有哪些

數(shù)學類的大學專業(yè)有哪些,大學中與數(shù)學有關的專業(yè)有哪些,和數(shù)學有關的專業(yè)有什么?數(shù)學類一級學科有哪些,和數(shù)學有關的大學專業(yè)有哪些,數(shù)學類專業(yè)有哪些。本文導航數(shù)學專業(yè)是最好的專業(yè)嗎數(shù)學相關專業(yè)有哪些與數(shù)學專業(yè)相近的專業(yè)有哪些數(shù)學一級學科是什么意思大學文科有哪些與數(shù)學有關的專業(yè)數(shù)學相關專業(yè)包括哪些數(shù)學專業(yè)...

數(shù)學與應用數(shù)學專業(yè) 數(shù)學與應用數(shù)學專業(yè)目前如何

數(shù)學與應用數(shù)學專業(yè) 數(shù)學與應用數(shù)學專業(yè)目前如何

數(shù)學與應用數(shù)學專業(yè)的就業(yè)方向有哪些?求職,數(shù)學與應用數(shù)學是什么專業(yè)?數(shù)學與應用數(shù)學專業(yè)的就業(yè)前景,數(shù)學與應用數(shù)學專業(yè)就業(yè)方向有哪些,數(shù)學與應用數(shù)學(師范)專業(yè)以后能做什么?數(shù)學與應用數(shù)學專業(yè)怎么樣?本文導航數(shù)學和應用數(shù)學系最好就業(yè)的專業(yè)數(shù)學與應用數(shù)學專業(yè)目前如何數(shù)學專業(yè)應用數(shù)學方向就業(yè)方向數(shù)學與應用...

信息與計算科學 信息與計算科學專業(yè)有前途嗎

信息與計算科學 信息與計算科學專業(yè)有前途嗎

什么是信息與計算科學?什么是信息與計算科學專業(yè)?信息與計算科學專業(yè)的現(xiàn)狀與前景,信息與計算科學專業(yè)學什么?信息與計算科學好就業(yè)嗎?信息與計算科學專業(yè)怎么樣?本文導航信息與計算科學與技術是學什么信息與計算科學專業(yè)怎么樣信息與計算科學專業(yè)能干什么信息與計算科學專業(yè)好不好信息與計算科學的就業(yè)方向信息與計算...

難什么結(jié)構分析 迎上去的迎是左右結(jié)構嗎

一個很難的英語句子的結(jié)構分析,一個很難的英語句子結(jié)構的分析----高手進,一個很難的英語句子結(jié)構分析----------務必精英人士進,難字是什么結(jié)構?"難"是左中右,灘是什么結(jié)構?在現(xiàn)代漢語中有點兒難是什么結(jié)構類型?本文導航英語句子結(jié)構分析54個英語句子結(jié)構分析及例子英語句子最基本的三種結(jié)構難字在...

什么是無界函數(shù) 常見的有界函數(shù)

什么是無界函數(shù) 常見的有界函數(shù)

什么叫有界函數(shù)和無界函數(shù)?什么是無界函數(shù)?函數(shù)無界是什么意思?怎樣證明函數(shù)無界?函數(shù)無界的定義是什么?無界函數(shù)的定義是什么?本文導航常見的有界函數(shù)怎么判斷是否是無界函數(shù)無界函數(shù)定義函數(shù)無界的判斷函數(shù)在定義域內(nèi)有界存在極限嗎無界函數(shù)的極限都不存在嗎常見的有界函數(shù)有界函數(shù)是指有最值,無界函數(shù)則無最值。例...

信息與計算科學屬于什么類 信息與計算科學是不是計算機專業(yè)

信息與計算科學屬于什么類 信息與計算科學是不是計算機專業(yè)

信息與計算科學屬于什么類的專業(yè)?信息與計算科學屬于什么專業(yè)類?信息與計算科學專業(yè)是屬于計算機類的還是數(shù)學類的,信息與計算科學專業(yè)屬于什么類的專業(yè)?是數(shù)學類還是計算機類?信息與計算科學專業(yè)考國家公務員屬于哪一類,信息與計算科學屬于哪一類。本文導航信息與計算科學的本科專業(yè)信息與計算科學專業(yè)有什么用信息與...

發(fā)表評論

訪客

◎歡迎參與討論,請在這里發(fā)表您的看法和觀點。