1、第八章第八章查找查找重點難點重點難點要求理解“查找表“的結(jié)構(gòu)特點以及各種表示方法的適用性；熟練掌握順序查找和折半查找的方法；熟悉描述折半查找過程的判定樹的構(gòu)造方法；熟練掌握二叉排序樹的構(gòu)造和查找方法；理解二叉平衡樹的構(gòu)造過程；理解B和B樹的特點、基本操作和二者的區(qū)別。熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實質(zhì)性的差別；掌握各種不同查找方法之間的區(qū)別和各自的適用情況，能按定義計算各種查找方法在等概率情況下查找成功時的平均

2、查找長度。典型例題典型例題1.若對具有n個元素的有序的順序表和無序的順序表分別進行順序查找，試在下述兩種情況下分別討論兩者在等概率時的平均查找長度：(1)查找不成功，即表中無關(guān)鍵字等于給定值K的記錄；(2)查找成功，即表中有關(guān)鍵字等于給定值K的記錄。【解】查找不成功時，需進行n1次比較才能確定查找失敗。因此平均查找長度為n1，這時有序表和無序表是一樣的。查找成功時，平均查找長度為(n1)2有序表和無序表也是一樣的。因為順序查找與表的初始

3、序列狀態(tài)無關(guān)。2.畫出對長度為18的有序的順序表進行二分查找的判定樹，并指出在等概率時查找成功的平均查找長度，以及查找失敗時所需的最多的關(guān)鍵字比較次數(shù)?！窘狻康雀怕是闆r下，查找成功的平均查找長度為：ASL=(122344853)18=3.556查找失敗時，最多的關(guān)鍵字比較次樹不超過判定樹的深度，此處為5.3.為什么有序的單鏈表不能進行折半查找├──┤6│∧│├──┤7│∧│├──┤8│∧│├──┤9│∧│├──┤10│∧│└──┘(2)

4、線性探查法如下圖：下標012345678910┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐T[0..10]│33│1│13│12│34│38│27│22││││└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘探查次數(shù)11134178用拉鏈法的查找成功平均查找長度為：ASLsucc=(142331)8=1.625查找失敗時平均查找長度為：ASLunsucc=(23100020000)11=0.73用線性探查法查找成功時平均查找長度為：AS

5、Lsucc=(11134178)8=3.25查找失敗時平均查找長度為：ASLunsucc=(98765432111)11=4.3裝填因子α拉鏈=411=0.36α線性探查=811=0.737.試寫一算法判別給定的二叉樹是否為二叉排序樹，設(shè)此二叉樹以二叉鏈表為存儲結(jié)構(gòu)，且樹中結(jié)點的關(guān)鍵字均不相同?！窘狻坑啥媾判驑涞亩x可得：二叉排序樹中左子樹的所有結(jié)點的值都小于根結(jié)點的值，所有右子樹中結(jié)點的值都大于根結(jié)點的值。那么只要對待判定的二叉樹中