【正文】 【解答】散列函數(shù)：H(K) = k % m 其中依題意得 m = 11H( 32 ) = 32 % 11 = 10H( 75 ) = 75 % 11 = 9H( 29 ) = 29 % 11 ?！窘獯稹?1) 順序查找： ASL = ( 1+2+3+…+25)/25 = 13(2) 二分查找： ASL = ( 1+2*2+4*3+8*4+10*5 )/25 = 99/25 = ( 參見上圖的二分查找樹 )18．假定一個(gè)待散列存儲(chǔ)的線性表為(32,75,29,63,48,94,25,46,18,70)，散列地址空間為HT[13]，若采用除留余數(shù)法構(gòu)造散列函數(shù)和線性探查法處理沖突，試求出每一元素的散列地址，畫出最后得到的散列表，求出平均查找長(zhǎng)度?！窘獯稹?6．請(qǐng)按照數(shù)列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序樹。是LR型14．設(shè)散列函數(shù)H（key）=key mod 11，給定鍵值序列為1414612346，試畫出相應(yīng)的開散列表，并計(jì)算在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度?！窘獯稹?123456789101173652537189145364275∧∧∧∧∧平均查找長(zhǎng)度ASL=( 7*1+2*2+3*1)/10=13．題32圖所示二叉樹是否為平衡二叉樹？若是，說(shuō)明理由；若不是，將其轉(zhuǎn)換為平衡二叉樹。③假定每個(gè)元素的查找概率相等，試計(jì)算該二叉搜索樹的平均查找長(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 }中的元素，生成一棵二叉搜索樹。采用線性探查法尋找下一個(gè)空位，畫出相應(yīng)的散列表，并計(jì)算等概率下查找成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。搜索成功時(shí)的平均搜索長(zhǎng)度ASLsucc=搜索不成功時(shí)的平均搜索長(zhǎng)度ASLunsucc= 【解答】其判定樹為：　　　　　　　 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, 解決沖突用線性探測(cè)再散列法，構(gòu)造哈希表，求等概率下查找成功的平均查找長(zhǎng)度?！窘獯稹緼SL1=7/6，ASL2=4/37．設(shè)有順序表中的元素依次為017，094，154，170，275，503，512，553，612，677，675，897，908。【解答】H(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)度。H(22)=22 mod 7=1。H(40)=40 mod 7=5?！?沖突 H2(22)=(2+1) mod 7=3。 H１(22)=(1+1) mod 7=2。略3．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）= K mod 7，若發(fā)生沖突采用線性探查法處理，試：（1）計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表： ` 0 1 2 3 4 5 6（2）求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。 五、應(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)度。（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)。(2) 依此二叉排序樹，如何得到一個(gè)從大到小的有序序列？（2）畫出在此二叉排序樹中刪除“66”后的樹結(jié)構(gòu)。23. 輸入一個(gè)正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。,各結(jié)點(diǎn)的值從小到大依次為19，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。20. 含9個(gè)葉子結(jié)點(diǎn)的3階B樹中至少有多少個(gè)非葉子結(jié)點(diǎn)？含10個(gè)葉子結(jié)點(diǎn)的3階B樹中至多有多少個(gè)非葉子結(jié)點(diǎn)？【(5分）】【北京輕工業(yè)學(xué)院2000八(10分）】【解答】含9個(gè)葉子結(jié)點(diǎn)的3階B樹至少有4個(gè)非葉子結(jié)點(diǎn)，當(dāng)每個(gè)非葉子結(jié)點(diǎn)均含3棵子樹，第三層是葉子結(jié)點(diǎn)時(shí)就是這種情況。B+樹的非終端結(jié)點(diǎn)是索引部分，其查找從根開始，從根往下查到關(guān)鍵字后，要繼續(xù)查到最下層結(jié)點(diǎn)，得到查找成功與否的結(jié)論。11112比較次數(shù)311(1)(8分)試畫出插入這8個(gè)關(guān)鍵碼后的散列表；(2)(5分)計(jì)算搜索成功的平均搜索長(zhǎng)度ASL。 i=1,2,3,…,m1其中，函數(shù)REV（x）表示顛倒10進(jìn)制數(shù)x的各位，如REV（37）=73，REV（7）=7等。散列函數(shù)和再散列函數(shù)分別為： H0(key)=key % 13。11234ASLsucc=18/7 ASLunsucc=32/1018. 設(shè)散列表為HT [0..12],即表的大小為m=13。1【西北大學(xué) 2000 (5分)】【解答】α=，所以表長(zhǎng)取m=7/=10散列地址0123456789關(guān)鍵字SAT【大連海事大學(xué)2001 八 (10分)】【解答】17. 對(duì)以下關(guān)鍵字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT)，哈希函數(shù)為H（K）=（關(guān)鍵字中第一個(gè)字母在字母表中的序號(hào)）MOD 7，用線性探測(cè)法處理沖突。【廈門大學(xué) 2001 （24%/3分）】【解答】ASLsucc=19/1216. 選取哈希函數(shù)Ｈ（key）=key mod 7,用鏈地址法解決沖突。B+樹的查找既可以順序查找，也可以隨機(jī)查找，B只能隨機(jī)查找。平均查找長(zhǎng)度：ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8以關(guān)鍵字27為例：H(27)=27%7=6(沖突) H1=(6+1)%10=7(沖突) H2=(6+22)%10=0(沖突) H3=(6+33)%10=5 所以比較了4次。比較次數(shù)1112 3 412【東北大學(xué) 2002 二 .2 （5分）】【解答】散列地址0123456789關(guān)鍵字14019238427552013. 設(shè)有一組關(guān)鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H（key）=key mod 7 ，表長(zhǎng)為10，用開放地址法的二次探測(cè)再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解決沖突。12. 在采用線性探測(cè)法處理沖突的散列表中，所有同義詞在表中是否一定相鄰？【西安電子科技大學(xué)2000計(jì)應(yīng)用 （5分）】【解答】不一定相鄰。由于哈希函數(shù)是壓縮映像，沖突難以避免。(5)記錄 負(fù)載因子11. 如何衡量hash函數(shù)的優(yōu)劣？簡(jiǎn)要敘述hash表技術(shù)中的沖突概念，并指出三種解決沖突的方法。(4)要在被刪除結(jié)點(diǎn)的散列地址處作標(biāo)記，不能物理的刪除。前者的指針域是動(dòng)態(tài)指針，指向同義詞的鏈表，具有上面③的優(yōu)缺點(diǎn)；后者實(shí)際是靜態(tài)鏈表，同義詞存在同一地址向量空間(從最后向前找空閑單元)，以靜態(tài)指針(下標(biāo))相連。 (3)用分離的同義詞表和結(jié)合的同義詞表解決碰撞均屬于鏈地址法。這種散列表常稱為開散列表，而①中的散列表稱閉散列表，含義是元素個(gè)數(shù)受表長(zhǎng)限制。凡散列地址為i(0≤i≤m1)的記錄均插在以H[i]為頭指針的鏈表中。該方法不易產(chǎn)生“聚集”，但增加了計(jì)算時(shí)間。c．di =偽隨機(jī)數(shù)序列，稱為隨機(jī)探測(cè)再散列。b．di =12，12，22，22，… ，177?！旧綎|工業(yè)大學(xué) 1999 四 （15分）】【解答】(1)散列表存儲(chǔ)的基本思想是用關(guān)鍵字的值決定數(shù)據(jù)元素的存儲(chǔ)地址 (2)散列表存儲(chǔ)中解決碰撞的基本方法： ① 開放定址法 形成地址序列的公式是：Hi=(H(key)+di)% m，其中m是表長(zhǎng)，di是增量。命題得證?！窘獯稹? 0 1 2 3 4 5 6 7 8 9 10 11 1278150357452031233612查找成功的平均查找長(zhǎng)度：ASL SUCC=14/10= 9. 證明若二叉排序樹中的一個(gè)結(jié)點(diǎn)存在兩個(gè)孩子，則它的中序后繼結(jié)點(diǎn)沒有左孩子，則它的中序前趨結(jié)點(diǎn)沒有右孩子。6．對(duì)長(zhǎng)度為20的有序表進(jìn)行二分查找，試畫出它的一棵判定樹【解答】7．用二分查找法對(duì)一個(gè)長(zhǎng)度為10的有序表進(jìn)行查找，填寫查找每一元素需要的比較次數(shù)。4．給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹，畫出插入完成后的二叉排序樹。2．在哈希查找法中，為什么平均查找長(zhǎng)度與關(guān)鍵字個(gè)數(shù)無(wú)關(guān)？3．在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？【解答】主要與哈希函數(shù)、裝填因子α有關(guān)。 39．（ ）在查找樹（二叉樹排序樹）中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。√37．（ ）采用線性探測(cè)再散列法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置為空，因?yàn)檫@會(huì)影響以后的查找?！?5．（ ）隨著裝填因子α的增大，用閉散列法解決沖突，其平均搜索長(zhǎng)度比用開散列法解決沖突時(shí)的平均搜索長(zhǎng)度增長(zhǎng)得慢。反之，一棵平衡的3路搜索樹是3階B_樹。 √31．（ ）m 階B樹的任何一個(gè)結(jié)點(diǎn)的左右子樹的高度都相等。30．（ ）中根遍歷二元查找樹所得序列一定是有序序列。28．（ ）設(shè)有關(guān)鍵字n=2h1，構(gòu)成二叉排序樹，每個(gè)關(guān)鍵字查找的概率相等，查找成功的ASL最大是n?！?6．（ ）適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是分塊有序表?！?4．（ ）B樹的插入算法中，通過(guò)結(jié)點(diǎn)的向上“分裂”，代替了專門的平衡調(diào)整?！?2．（ ）二元查找樹的任何結(jié)點(diǎn)的左右子樹都是二元查找樹。20．（ ）在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。18．（ ）對(duì)于滿足折半查找和分塊查找條件的文件而言，無(wú)論它存放在何種介質(zhì)上，均能進(jìn)行順序查找、折半查找和分塊查找。16．（ ）哈希表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針?！?4．（ ）在散列檢索中，“比較”操作一般也是不可避免的?！?2．（ ）有序表的折半查找只適用于升序表。√10．( )一個(gè)單鏈表不能采用折半查找法進(jìn)行查找。F8．（ ）順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。T6．（ ）分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。T4．（ ）先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。T2．（ ）中序遍歷二叉排序樹可以得到一個(gè)有序的序列。(d+9)%m99. 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的是 。 1+ a /297. 在采用線性探測(cè)法處理沖突的閉散列表中，假定裝填因子為 a ，則進(jìn)行成功查找的平均查找長(zhǎng)度為 ______