【正文】 突。并分別計(jì)算出在等概率情況下查找成功與不成功的平均查找長(zhǎng)度?！疚鞅贝髮W(xué) 2000 (5分)】【解答】α=，所以表長(zhǎng)取m=7/=10散列地址0123456789關(guān)鍵字SATWEDSUNMONTUETHUFRI比較次數(shù)6111234ASLsucc=18/7 ASLunsucc=32/1018. 設(shè)散列表為HT [0..12],即表的大小為m=13?，F(xiàn)采用雙散列法解決沖突。散列函數(shù)和再散列函數(shù)分別為： H0(key)=key % 13。 注:%是求余數(shù)運(yùn)算(=mod) Hi=(Hi1+REV(key+1)%11+1) % 13。 i=1,2,3,…,m1其中，函數(shù)REV（x）表示顛倒10進(jìn)制數(shù)x的各位，如REV（37）=73，REV（7）=7等。若插入的關(guān)鍵碼序列為(2,8,31,20,19,18,53,27)。(1)(8分)試畫(huà)出插入這8個(gè)關(guān)鍵碼后的散列表；(2)(5分)計(jì)算搜索成功的平均搜索長(zhǎng)度ASL。 【清華大學(xué)2000八(13分）】【解答】(1)散列地址0123456789101112關(guān)鍵字27532311920818比較次數(shù)31111112(2)ASLsuss =11/8+樹(shù)中查找關(guān)鍵字時(shí)，有什么不同？【東北大學(xué) 2002 一 .5 (2分)】【解答】在B樹(shù)中查找關(guān)鍵字從根結(jié)點(diǎn)開(kāi)始，從根往下查找結(jié)點(diǎn)，然后在結(jié)點(diǎn)內(nèi)查找關(guān)鍵字，得出查找成功與否的結(jié)論。B+樹(shù)的非終端結(jié)點(diǎn)是索引部分，其查找從根開(kāi)始，從根往下查到關(guān)鍵字后，要繼續(xù)查到最下層結(jié)點(diǎn)，得到查找成功與否的結(jié)論。另外，B+樹(shù)還可以在最下層從最小關(guān)鍵字開(kāi)始，從左往右進(jìn)行順序查找，B樹(shù)則不能作順序查找。20. 含9個(gè)葉子結(jié)點(diǎn)的3階B樹(shù)中至少有多少個(gè)非葉子結(jié)點(diǎn)？含10個(gè)葉子結(jié)點(diǎn)的3階B樹(shù)中至多有多少個(gè)非葉子結(jié)點(diǎn)？【(5分）】【北京輕工業(yè)學(xué)院2000八(10分）】【解答】含9個(gè)葉子結(jié)點(diǎn)的3階B樹(shù)至少有4個(gè)非葉子結(jié)點(diǎn)，當(dāng)每個(gè)非葉子結(jié)點(diǎn)均含3棵子樹(shù)，第三層是葉子結(jié)點(diǎn)時(shí)就是這種情況。當(dāng)4層3階B樹(shù)有10個(gè)葉子結(jié)點(diǎn)時(shí)，非葉子結(jié)點(diǎn)達(dá)到最大值8個(gè)：其中第一層1個(gè)，第二層2個(gè)，第三層5個(gè)。,各結(jié)點(diǎn)的值從小到大依次為19，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。【廈門(mén)大學(xué) 2002 （5分）】【解答】22. 在查找和排序算法中，監(jiān)視哨的作用是什么？【解答】監(jiān)視哨的作用是免去查找過(guò)程中每次都要檢測(cè)整個(gè)表是否查找完畢，提高了查找效率。23. 輸入一個(gè)正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。（1）按次序構(gòu)造一棵二叉排序樹(shù)BS。(2) 依此二叉排序樹(shù)，如何得到一個(gè)從大到小的有序序列？（2）畫(huà)出在此二叉排序樹(shù)中刪除“66”后的樹(shù)結(jié)構(gòu)?！就瑵?jì)大學(xué)2001一(10分)】【解答】24. 設(shè)二叉排序樹(shù)中關(guān)鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)鍵字序列哪一個(gè)不可能是在二叉排序樹(shù)中查到的序列？說(shuō)明原因。（1）51,250,501,390,320,340,382,363 （2）24,877,125,342,501,623,421,363【東北大學(xué) 2002 一 .3 (4分)】【解答】25. 用分塊查找法，有2000項(xiàng)的表分成多少塊最理想？每塊的理想長(zhǎng)度是多少？若每塊長(zhǎng)度為25 ，平均查找長(zhǎng)度是多少？【解答】分成45塊，每塊的理想長(zhǎng)度為45(最后一塊長(zhǎng)20)。若每塊長(zhǎng)25，則平均查找長(zhǎng)度為ASL=(80+1)/2+(25+1)/2=(順序查找確定塊)，或ASL=19(折半查找確定塊)。 五、應(yīng)用題1. 設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。【解答】2,ASL=91*1+2*2+3*4+4*2)=25/92．設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹(shù)并給出構(gòu)造過(guò)程。略3．已知待散列的線(xiàn)性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）= K mod 7，若發(fā)生沖突采用線(xiàn)性探查法處理，試：（1）計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫(xiě)出散列表： ` 0 1 2 3 4 5 6（2）求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。【解答】H(36)=36 mod 7=1。 H１(22)=(1+1) mod 7=2。 ….沖突H(15)=15 mod 7=1?！?沖突 H2(22)=(2+1) mod 7=3。 H１(15)=(1+1) mod 7=2。H(40)=40 mod 7=5。H(63)=63 mod 7=0。H(22)=22 mod 7=1。 ….沖突（1） 0 1 2 3 4 5 66336152240（2）ASL=4．設(shè)散列表的地址范圍是[ 0..9 ]，散列函數(shù)為H（key）= （key 2 +2）MOD 9,并采用鏈表處理沖突，請(qǐng)畫(huà)出元素9依次插入散列表的存儲(chǔ)結(jié)構(gòu)?！窘獯稹縃(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=65．設(shè)一組初始記錄關(guān)鍵字序列為(15，17，18，22，35，51，60)，要求計(jì)算出成功查找時(shí)的平均查找長(zhǎng)度?！窘獯稹緼SL=(1*1+2*2+3*4)/7=17/76．設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線(xiàn)性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度?！窘獯稹緼SL1=7/6，ASL2=4/37．設(shè)有順序表中的元素依次為017，094，154，170，275，503，512，553，612，677，675，897，908。試畫(huà)出對(duì)其進(jìn)行折半搜索時(shí)做性能分析用的擴(kuò)充二叉搜索樹(shù)（判定樹(shù)），并計(jì)算搜索成功時(shí)的平均搜索長(zhǎng)度和搜索不成功進(jìn)的平均搜索長(zhǎng)度。搜索成功時(shí)的平均搜索長(zhǎng)度ASLsucc=搜索不成功時(shí)的平均搜索長(zhǎng)度ASLunsucc= 【解答】其判定樹(shù)為：　　　　　　　 519 154 677 017 275 553 897 094 170 503 512 612 765 908 搜索成功時(shí)的平均搜索長(zhǎng)度為：ASLsucc=(1+2*2+3*4+4*7)/14=45/14搜索不成功時(shí)的平均搜索長(zhǎng)度為：ASLunsucc=(3+4*14)/15=59/158．已知關(guān)鍵字序列為：（75, 33, 52, 41, 12, 88, 66, 27）哈希表長(zhǎng)為10，哈希函數(shù)為：H(k)=K MOD 7, 解決沖突用線(xiàn)性探測(cè)再散列法，構(gòu)造哈希表，求等概率下查找成功的平均查找長(zhǎng)度。 9．設(shè)散列表為HT[13]，散列函數(shù)為H(key)=key%13，用閉散列法解決沖突，對(duì)下列關(guān)鍵碼序列12，23，45，57，20，3，78，31，15，36造表。采用線(xiàn)性探查法尋找下一個(gè)空位，畫(huà)出相應(yīng)的散列表，并計(jì)算等概率下查找成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度?！窘獯稹?123456789101112Key7815357452031233612成功時(shí)的比較次數(shù)1111114121不成功時(shí)的比較次數(shù)2132154321543ASLsucc＝（1＋1＋1＋1＋1＋1＋4＋1＋2＋1）/10＝ASLunsucc=（2＋1＋3＋2＋1＋5＋4＋3＋2＋1＋5＋4＋3）/13＝36/1310．設(shè)散列表長(zhǎng)13，散列函數(shù)為H(key) = key % 13，對(duì)關(guān)鍵碼序列93, 63, 81, 78, 17, 8, 85, 7, 30, 22造表，用線(xiàn)性探測(cè)法解決沖突，畫(huà)出相應(yīng)的散列表，并計(jì)算等概率下查找成功時(shí)的平均查找長(zhǎng)度。 【解答】散列表 ( 按關(guān)鍵碼數(shù)組位置， )下標(biāo)0123456789101112關(guān)鍵碼789381173085872263查找次數(shù)1111211321ASLsucc = ( 7 1 + 2 2 + 1 3 ) / 10 = 14 / 10　　　　　(1分)11．依次輸入表{ 30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55 }中的元素，生成一棵二叉搜索樹(shù)。①試畫(huà)出生成之后的二叉搜索樹(shù)；②對(duì)該二叉搜索樹(shù)進(jìn)行中序遍歷，試寫(xiě)出遍歷序列。③假定每個(gè)元素的查找概率相等，試計(jì)算該二叉搜索樹(shù)的平均查找長(zhǎng)度?！窘獯稹浚?）（2）中序序列：10, 12, 15, 20, 28, 30, 35, 46, 50, 55, 68（3）ASLsucc = ( 1 1 + 2 2 + 4 3 + 4 4 ) / 11=312．假定一個(gè)待散列存儲(chǔ)的線(xiàn)性表為 (37,65,25,73,42,91,45,36,18,75)， 散列地址空間為HT[12]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫(huà)出最后得到的散列表，求出平均查找長(zhǎng)度?！窘獯稹?123456789101173652537189145364275∧∧∧∧∧平均查找長(zhǎng)度ASL=( 7*1+2*2+3*1)/10=13．題32圖所示二叉樹(shù)是否為平衡二叉樹(shù)？若是，說(shuō)明理由；若不是，將其轉(zhuǎn)換為平衡二叉樹(shù)。題32圖【解答】不是AVL樹(shù)。是LR型14．設(shè)散列函數(shù)H（key）=key mod 11，給定鍵值序列為1414612346，試畫(huà)出相應(yīng)的開(kāi)散列表，并計(jì)算在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。【解答】Asl=（5+2*3+3*2）/10=15．從一個(gè)空的二叉排序樹(shù)開(kāi)始，依次插入關(guān)鍵字211337，試分別畫(huà)出每次插入關(guān)鍵字后的二叉排序樹(shù)?！窘獯稹?6．請(qǐng)按照數(shù)列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序樹(shù)?！窘獯稹?7．假定查找有序表A[25]中每一元素的概率相等，試分別求出進(jìn)行順序、二分查找每一元素時(shí)的平均查找長(zhǎng)度?！窘獯稹?1) 順序查找： ASL = ( 1+2+3+…+25)/25 = 13(2) 二分查找： ASL = ( 1+2*2+4*3+8*4+10*5 )/25 = 99/25 = ( 參見(jiàn)上圖的二分查找樹(shù) )18．假定一個(gè)待散列存儲(chǔ)的線(xiàn)性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線(xiàn)性探查法處理沖突，試求出每一元素的散列地址，畫(huà)出最后得到的散列表，求出平均查找長(zhǎng)度?！窘獯稹可⒘泻瘮?shù)：H(K) = k % m 其中依題意得 m = 13 H( 32 ) = 32 % 13 = 6 H( 75 ) = 75 % 13 = 10 H( 29 ) = 29 % 13 = 3 H( 63 ) = 63 % 13 = 11 H( 48 ) = 48 % 13 = 9H( 94 ) = 94 % 13 = 3 (沖突) 設(shè) d0 = H(K) = H(94) = 3 d1 = ( d0+1 ) % m = (3+1)%13 = 4 H( 25 ) = 25 % 13 = 12 H( 46 ) = 46 % 13 = 7 H( 18 ) = 18 % 13 = 5 H( 70 ) = 70 % 13 = 5 (沖突) 設(shè) d0 = H(K) = H(70) = 5 d1 = ( d0+1 ) % m = (5+1)%13 = 6 (沖突) d2 = ( d1+1 ) % m = (6+1)%13 = 7 (沖突) d3 = ( d2+1 ) % m = (7+1)%13 = 8 ASL = ( 8*1+1*2+1*4 )/10 = 19．假定一個(gè)待散列存儲(chǔ)的線(xiàn)性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[11]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和鏈接法處理沖突，試求出每一元素的散列地址，畫(huà)出最后得到的散列表，求出平均查找長(zhǎng)度。【解答】散列函數(shù)：H(K) = k % m 其中依題意得 m = 11H( 32 ) = 32 % 11 = 10H( 75 ) = 75 % 11 = 9H( 29 ) = 29 %