北航計算機考研材料第9章查找答案

1、第9章集合.選擇題1.C2. A3. ID3. 2C4.D5.B6.D7.D8.C9. A10. D11.B12.12.13.13.13.13.14. IE14.14. 3E14.14.15. IBA1C C1D C毎C2H D21.B2B. C23. B2B. C5B. IB25. 2F2聽126. A27. D28. C29.29.30. B31. D32. D33. C34. D35. ID35.36. C1A2C2（判斷題1. V2. V3. X4. X5. X6. V7. V8. X9. X10.X11.X12.V13.V14.X15.X16.X17.V18.X19.V20.X21.

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

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

4、衡的二叉排序樹），或為空二叉樹，或二叉樹中任意結點左子樹高度與右子樹高度差的絕對值小于等于Io12. 小于等于表長的最大素數或不包含小于20的質因子的合數13. 1614. Lbg2nJ +115. （ 1） 45 （ 2） 45 （3） 46 （塊內順序查找）16. k （ k+l） /2 17. 30, 31. 5 （塊內順序查找）18. （1）順序存儲或鏈式存儲（2）順序存儲且有序（3）塊內順序存儲，塊間有序散列存儲19. （n+1）/220. （n+1）/n*log 2（n+l）-l21.結點的左子樹的高度減去結點的右子樹的高度22. (1)順序表(2)樹表(3)哈希表(4)開放定址方

5、法(5)鏈地址方法(6)再哈希(7)建立公共溢岀區(qū)n + 123.直接定址法24logM (2 )+125. 0(N)26. n(n+l)/227. 5428. 31樹29. 37/1230.主關鍵字31.左子樹右子32.插入刪除33. 1434. (1)126(2)64(3)33(4)6535.low二 high(low+hig) DIV 2(3) bin srch:=mid (4)b in srch:=O36. k (2) Q< n+(2)37. (l)rear=mid-l (2)head=mid+l (3)head>rear38. (l)p!=null (2)pf=p (3)

6、p!=*t(4)*t=null四.應用題1. 概念是基本知識的主要部分，要牢固掌握。這里只列岀一部分，目的是引起重視，解答略。2. (1)散列表存儲的基本思想是用關鍵字的值決定數據元素的存儲地址(2) 散列表存儲中解決碰撞的基本方法：%1開放定址法 形成地址序列的公式是：比=(H (key) +di) % m,其中m是表長，心是增量。根據d,取法不同，又分為三種：a. 山=1,2,m-1稱為線性探測再散列，其特點是逐個探測表空間，只要散列表中有空閑空間，就可解決碰撞，缺點是容易造成“聚集”，即不是同義詞的關鍵字爭奪同散列地址。b. di =12, -I2, 22, -22,，±<

7、;2 (kWm/2)稱為二次探測再散列，它減少了聚集，但不容易探測到全部表空間，只有當表長為形如4j+3 (j為整數)的素數時才有可能。c. 4 =偽隨機數序列，稱為隨機探測再散列。%1再散列法 HFR乩(key) i=l, 2,，k,是不同的散列函數，即在同義詞產生碰撞時，用另一散列函數計算散列地址，直到解決碰撞。該方法不易產生“聚集”，但增加了計算時間。%1鏈地址法將關鍵字為同義詞的記錄存儲在同一鏈表中，散列表地址區(qū)間用HO.m-l表示，分量初始值為空指針。凡散列地址為i (OWiWm-1)的記錄均插在以 Hi為頭指針的鏈表中。這種解決方法中數據元素個數不受表長限制，插入和刪除操作方便，但

8、增加了指針的空間開銷。這種散列表常稱為開散列表，而中的散列表稱閉散列表，含義是元素個數受表長限制。%1建立公共溢出區(qū)設H為基本表，凡關鍵字為同義詞的記錄，都填入溢出區(qū)00. . ml o(3) 用分離的同義詞表和結合的同義詞表解決碰撞均屬于鏈地址法。鏈地址向量空間中的每個元素不是簡單的地址，而是關鍵字和指針兩個域，散列地址為i (OWiWm-1)的第個關鍵字存儲在地址空間向量第i個分量的“關鍵字”域。前者的指針域是動態(tài)指針，指向同義詞的鏈表，具有上面的優(yōu)缺點；后者實際是靜態(tài)鏈表，同義詞存在同一地址向量空間(從最后向前找空閑單元)，以指針相連。節(jié)省了空間，但易產生“堆積”，查找效率低。(4) 要

9、在被刪除結點的散列地址處作標記，不能物理的刪除。否則，中斷了查找通路。(5) 記錄負載因子3. 評價哈希函數優(yōu)劣的因素有：能否將關鍵字均勻影射到哈?？臻g上，有無好的解決沖突的方法，計算哈希函數是否簡單高效。由于哈希函數是壓縮映像，沖突難以避免。解決沖突的方法見上面2題。4. 哈希方法的平均查找路長主要取決于負載因子(表中實有元素數與表長之比)，它反映 了哈希表的裝滿程度，該值一般取0.650.9。解決沖突方法見上面2題。5. 不一定相鄰。哈希地址為i (OWiWm-1)的關鍵字，和為解決沖突形成的探測序列i的同義詞，都爭奪哈希地址i。6.散列地址0123456789關鍵/p>

10、5520比較次數11123412平均查找長度：ASL ECF (1+1 + 1+2+3+4+1+2) /8=15/8以關鍵字 27 為例：H (27) =27%7=6 (沖突)Hi= (6+1) %10=7 (沖突)H 尸(6+22) %10=0 (沖突)H3= (6+3 3) %10=5 所以比較了 4 次。7.由于裝填因子為 0.8，關鍵字有8個，所以表長為 8/0. 8=10,pj用除宦余數鈦.唔希顒數為衛(wèi)(key) -key 7(2)散列地址0123456789關鍵字21厲3D36254Q37比較歡數11 j31 .126計算畫找失敗甘的平均査扌戈長度，泌嫌計算不柱表中的關鍵字WiWm

11、-1)時的查找次數。本例中m=10o故查找失敗時的平均查找長度為：ASLunsucc- (9+8+7+6+5+4+3+2+1+1) /10二 4. 6 ASL succ -16/8-2(4) int Delete (int hn, int k)/從哈希表hn中刪除元素k,若刪除成功返回1,否則返回0i 二 k%7 ； / 哈希函數用上面(1),即 H (key)二 key % 7if (hi= maxi nt) /maxi nt解釋成空地址printf ("無關鍵字 n” k) ； return (0) ； if (hi二二k) hi=-maxint ； return (1) ； /

12、被刪元素換成最大機器數的負數else /采用線性探測再散列解決沖突j-i ；for (d 二 1 ； dWnT ； d+)i二(j+d) %n ；/ n為表長，此處為10if (hi= maxi nt) return (0) ; /maxi nt 解釋成空地址 if (hi=k) hi 二-maxi nt ； return(1) ； /forprintf ("無關鍵字 %dn" , k) : return (0)散列地址0123456789關鍵字1524101917381840比較次數TT2I4555哈希表 a: ASLs"? =24/8=3 ；散列地址0I234

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

14、定址法下，不能物理 地刪除, 只能作刪除標記。該地址可能是該記錄的同義詞查找路徑上的地址，物理的刪除就 中斷了查找路徑。 因為查找時碰到空地址就認為是查找失敗。散列地址0I2345678910II12131415關鍵字14016827551920847923II10比較次數I2I43II39II313. (1)散列地址0I2345678910關鍵字412493813243221比較次數III2I2I2ASL suce = (1 + 1+1+2+1+2+1+2) /8=11/8ASL u, succ= (1+2+1+8+7+6+5+4+3+2+1)/11=40/110 12345678912A4

15、9>1 13 14>1 32 14?| 2,36AiI A|21A-3322A.1? 1213AA A?38AI27 I AA A A A AI飼 34 |A|13 題圖 ASLsucc =11/8 ASL unsucc=19/ll14題(2) ASLsucc=13/8值得指出，對用拉鏈法求查找失敗時的平均查找長度有兩種觀點。其一，認為比較到空指針算失敗。以本題為例，哈希地址0、2、5、7、9和10均為比較1次失敗，而哈希地址1和3比較2次失敗，其余哈希地址均為比較3次失敗，因此，查找失敗時的平均查找長度為19/11,我們持這種觀點。還有另一種理解，他們認為只有和關鍵字比較才計算比

16、較次數,而和空指針比較不計算。照這種觀點，本題的 ASLunsucc- (1+1+2+2+2)/11=8/1114.由hashf(x)=x mod 11可知，散列地址空間是0到10,由于有8個數據，裝載因子取0. 7o(1)散列地址關鍵字1C21if1 ；、ASLsucc 21/82345678910"131A34* -38?| Al27gbAI2213IM/i 28AASLu ns.47AINov(1) ASL=42/12 a :67890123AAAAanMarMay* WovN>|Jul A|散列地址012345678910121314 .1516關鍵字AADFJMMJu

17、J u|SeNov比較次數12111124526a: ASLsucc=31/12b : ASL succ=18/12 (注：本題兇取小于等于 x的最大整 數)COCXITo600'w 氷oCXIT卜<6CO<<一 L 士<<<flITssns_ls<05- H oonslsv<r<plco CNXTL gT 寸L 111r<ASLsuco =21/11散列地址012345678910關鍵字223346130167415330比較次數121245113散列解決沖突，根據公式Sn l(1+1/ (1-a) ) /222.散列 地址

18、01234567891011121314151617關鍵字3217634924401030314647比較 次數11631211133(2) 查找關鍵字63, H (k) =63 MOD 16=15,依次與 31,46, 47, 32,17, 63 比較 查找關鍵字 60, H (k) =60 MOD 16=12,散列地址12內為空，查找失敗。散列地hl012345678y1011121314151617181920n22址鍵字YA NGL ICHANCAW EYUCH ENZH AOSN GCAwL I比較次1111U1G21N1N1111O 13u2(4) ASL sucC=23/II23.設用線性探測再可求出負載因子為a =0. 67o再根據數據個數和裝載因子，可求岀表長 m=15/0. 67,取m=23。設哈希函 數H(key)=(關鍵字首尾字母在字母表中序號之和)MOD 23從上表求岀查找成功時的平均查找長度為ASLsUcc=19/15<2. 0,滿足要求。24.(1)哈希函數 H (key)=(關鍵字各字符編碼之和)MOD 7散列地址0123456789關鍵字becdaaabacadbdbeaece比較次數121111133925. a=0. 7,所以表長取 m=7/0. 7=10散列地址012