對長度為n的有序單鏈表,若搜索每個元素的概率相等,則順序搜索到表中任一元素的平均搜索長度為___
對長度為n的有序單鏈表，若搜索每個元素的概率相等，則順序搜索到表中任一元素的平均搜索長度為______。
A．n/2
B．(n+1)/2
C．(n-1)/2
D．n/4
正確答案：B解析：由于鏈表不能隨機訪問，要訪問某個節(jié)點，必須從它的直接前驅(qū)的指針域出發(fā)才能找到。因此，鏈式存儲的線性表，即使是有序表，也只能使用順序查找。順序查找時，從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。假設(shè)在每個位置查找概率相等，即P1=P2=…=Pn=1/n，若是從表頭向表尾方向查找，則每個位置上查找比較次數(shù)為C1＝1，C2＝2，…，Cn＝n。于是，查找成功的平均查找長度為[*]
詞條內(nèi)容僅供參考，如果您需要解決具體問題
（尤其在法律、醫(yī)學(xué)等領(lǐng)域），建議您咨詢相關(guān)領(lǐng)域?qū)I(yè)人士。