第9章查找答案

1、第9章 集合選擇題1.C2.A3.1D3.2C4.D5.B6.D7.D8.C9.A10.D11.B12.1C12.2C13.1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.C25.1B25.2F25.3I26.A27.D28.C29.1A29.2C30.B31.D32.D33.C34.D35.1D35.2C36.C判斷題1. V2. V3. X4. X5. X6. V7. V8. X9. X10.X11.X12.V13.V14.X15.X16.X17.V18.X19.V

2、20.X21.X22.X23.X24.X25.V26.X27.X28.V29.V30.X31.X32.V33.V34.X35.V36.V部分答案解釋如下。4不能說哪種哈希函數的選取方法最好，各種選取方法有自己的適用范圍。&哈希表的結點中可以包括指針，指向其元素。11 單鏈表不能使用折半查找方法。20. 按插入后中序遍歷是遞增序列的原則， 若某結點只有右子樹， 而插入元素的關鍵字小于 該結點的關鍵字，則會插入到該結點的左側， 成為其左孩子。這種插入就不是插入到葉子下 面。21. 從平衡因子定義看， 完全二叉樹任一結點的平衡因子的絕對值確實是小于等于1。但是,平衡二叉樹本質上是二叉排序樹，完全二叉

3、樹不一定是排序樹。故不能說完全二叉樹是平衡二叉樹。23. 某結點的左子樹根結點不一定是它的中序前驅，其右子樹根結點也不一定是它的中序后 繼。24. 在等概率下，查找成功時的平均查找長度相同，查找失敗時的平均查找長度不相同。26.只有被刪除結點是葉子結點時命題才正確。三.填空題5.1,3,6,8,11,13,16,192,4,3處理沖突的方法（5）均勻1. n n+12. 43. 6,9,11,124* J JF5. 26 （第4層是葉子結點，每個結點兩個關鍵字）67. 5,968. m-1,m/2 -19 10 . （1）哈希函數（2）解決沖突的方法（3）選擇好的哈希函數簡單或為空二叉樹，或二

4、叉樹中任意結點11 . AVL樹（高度平衡樹，高度平衡的二叉排序樹）， 左子樹高度與右子樹高度差的絕對值小于等于1。12 .小于等于表長的最大素數或不包含小于20的質因子的合數13. 1614.噸2nj +115 . （1）45 （2）45 （3）46 （塊內順序查找） 16 . k（k+1）/217. 30, 31.5 （塊內順序查找）18 . （1）順序存儲或鏈式存儲（2）順序存儲且有序（3）塊內順序存儲，塊間有序（4）散列存儲19. (n +1)/2 20. (n+1)/n*log 2(n+1)-121.結點的左子樹的高度減去結點的右子樹的高度22. (1)順序表(2)樹表(3)哈希表(

5、4)開放定址方法(5)鏈地址方法(6)再哈希(7)建立公共溢 出區(qū)23.直接定址法24. log m/2 (2)+125.O(N)26.n(n+1)/227.5428. 3129.37/1230.主關鍵字31.左子樹 右子樹32.插入刪除33.1434.(1)126 (2)64(3)33(4)6535.(1)low=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=036.(1) k lrear38. (1)p!=null (2)pf=p (3)p!=*t (4)*t=null四應用題 1概念是基本知識的主要部分，要牢固掌握。這里只列出

6、一部分，目的是引起重視，解答 略。2. ( 1 )散列表存儲的基本思想是用關鍵字的值決定數據元素的存儲地址(2) 散列表存儲中解決碰撞的基本方法： 開放定址法形成地址序列的公式是：H= ( H( key) +di) % m其中m是表長，di是增量。根據di取法不同，又分為三種：a. di =1 , 2，m-1稱為線性探測再散列，其特點是逐個探測表空間，只要散列表 中有空閑空間，就可解決碰撞，缺點是容易造成“聚集”，即不是同義詞的關鍵字爭奪同一 散列地址。b. di=12,-1 2,22,-2 2,y,k2(k m/2)稱為二次探測再散列，它減少了聚集，但不容易探測到全部表空間，只有當表長為形如

7、4j+3 (j為整數)的素數時才有可能。c. di =偽隨機數序列，稱為隨機探測再散列。 再散列法 H i=RH (key) i=1 , 2,，k，是不同的散列函數，即在同義詞產生 碰撞時，用另一散列函數計算散列地址，直到解決碰撞。該方法不易產生“聚集”，但增加 了計算時間。 鏈地址法將關鍵字為同義詞的記錄存儲在同一鏈表中，散列表地址區(qū)間用H0.m-1表示，分量初始值為空指針。凡散列地址為i (0 i m-1 )的記錄均插在以 Hi為頭指針的鏈表中。這種解決方法中數據元素個數不受表長限制，插入和刪除操作方便，但增加了指針的空間開銷。這種散列表常稱為開散列表，而中的散列表稱閉散列表，含義是元素個

8、數受表長限制。 建立公共溢出區(qū)設H0.m-1為基本表，凡關鍵字為同義詞的記錄，都填入溢出區(qū)O0.m-1。(3) 用分離的同義詞表和結合的同義詞表解決碰撞均屬于鏈地址法。鏈地址向量空間中的每個元素不是簡單的地址，而是關鍵字和指針兩個域，散列地址為i (0 i w m-1)的第一個關鍵字存儲在地址空間向量第i個分量的“關鍵字”域。前者的指針域是動態(tài)指針， 指向同義詞的鏈表，具有上面的優(yōu)缺點；后者實際是靜態(tài)鏈表，同義詞存在同一地址向量空間(從最后向前找空閑單元)，以指針相連。節(jié)省了空間，但易產生“堆積”，查找效率低。(4 )要在被刪除結點的散列地址處作標記，不能物理的刪除。否則，中斷了查找通路。(5

9、)記錄負載因子3評價哈希函數優(yōu)劣的因素有：能否將關鍵字均勻影射到哈希空間上，有無好的解決沖突的方法，計算哈希函數是否簡單高效。由于哈希函數是壓縮映像，沖突難以避免。解決沖突 的方法見上面2題。4哈希方法的平均查找路長主要取決于負載因子(表中實有元素數與表長之比)，它反映 了哈希表的裝滿程度，該值一般取0.650.9。解決沖突方法見上面2題。5.不一定相鄰。哈希地址為i (0故查找失敗時的平均查找長度為：ASLunsucc= (9+8+7+6+5+4+3+2+1 + 1) /10=4.6ASLsucc =16/8=2(4) int Delete (int hn , int k/ 從哈希表hn中刪

10、除元素k，若刪除成功返回1,否則返回0i=k%7; / 哈希函數用上面(1),即卩 H( key) =key % 7if (hi= maxi nt ) /maxi nt 解釋成空地址printf(無關鍵字 %dn ”，k); return (0); (1); /被刪元素換成最大機器數的為表長，此處為10;/maxi nt解釋成空地址;return (1); if (hi=k ) hi=-max int ; return 負數else /采用線性探測再散列解決沖突 j=i ；for (d=1; dw n-1 ； d+)i=(j +d) %n/ nif (hi= maxi nt) return (

11、0)if (hi=k ) hi=-maxint/ forprintf (無關鍵字 %dn”，k); return (0)散列地址0123456789關鍵字1524101917381840比較次數11214555哈希表 a: ASL succ=24/8=3 ;散列地址0123456789關鍵字1517241019403818比較次數13121244哈希表b: ASL succ =18/89.( 1)散列地址0123456789101112關鍵字13225314167465130比較次數111212111(2)裝填因子=9/13=0.7( 3) ASLucc =11/9( 4) ASGsucc =

12、29/13101110.1112常用構造哈希函數的方法有:AScc=19/1212(1) 數字分析法 該法事先需知道關鍵字集合，且關鍵字位數比散列表地址位數多，應選 數字分布均勻的位。(2) 平方取中法 將關鍵字值的平方取中間幾位作哈希地址。(3) 除留余數法 H (key) =key%p,通常p取小于等于表長的最大素數。(4) 折疊法 將關鍵字分成長度相等(最后一段可不等)的幾部分，進行移位疊加或間界 疊加，其值作哈希地址。(5) 基數轉換法 兩基數要互素，且后一基數要大于前一基數。在哈希表中刪除一個記錄， 在拉鏈法情況下可以物理 地刪除。在開放定址法下， 不能物理 地刪除，只能作刪除標記。

13、 該地址可能是該記錄的同義詞查找路徑上的地址，物理的刪除就中斷了查找路徑。因為查找時碰到空地址就認為是查找失敗。散列地址0123456789101112131415關鍵字140168275519208479231110比較次數12143113911313. ( 1)散列地址012345678910關鍵字412493813243221比較次數11121212ASGcc = ( 1 + 1+1+2+1+2+1+2) /8=11/8ASLunsucc = (1+2+1+8+7+6+5+4+3+2+1) /11= 40/1122A劌18A18. ASLsucc =15/1019. ASLsuss =1

14、6/114578gfiro1散列地址01234567891011關鍵字231897925471638825139151比較次數11112123243ASLsucc =21/11 21.散列地址012345678910關鍵字223346130167415330比較次數12124511322.(1)散列 地址01234567891011121314151617關鍵字3217634924401030314647比較 次數116312111；33(2) 查找關鍵字 63, H (k) =63 MOD 16=15,依次與 31, 46, 47, 32, 17, 63 比較。(3) 查找關鍵字 60, H

15、( k)=60 MOD 16=12,散列地址12內為空，查找失敗。(4) ASLsucc=23/11散列地址012345G7g1011121314151G171619202122訊TANGUUCAI恒runCHENZHAOLONGCAOTttU口1111121111LT1223.設用線性探測再散列解決沖突，根據公式Snl1 + 1/ (1- a) /2 ?？汕蟪鲐撦d因子為a =0.67。再根據數據個數和裝載因子，可求出表長m=15/0.67，取m=23設哈希函數H( key)=(關鍵字首尾字母在字母表中序號之和)MOD 23從上表求出查找成功時的平均查找長度為ASLucc=19/152.0，滿足要求。24.( 1)哈希函數 H ( key)=(關鍵字各字符編碼之和)MOD 7(2)散列地址0123456789關鍵字becdaaabacadbdbcaece比較次數121111133925.a =0.7，所以表長取 m=7/0.7=10散列地址0123456789關鍵字SATWEDSUNMONTUETHUFRI比較次數6111234ASLsucc