北航計(jì)算機(jī)考研材料第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.不能說(shuō)哪種哈希函數(shù)的選取方法最好，各種選取方法有自己的適用范圍8.哈希表的結(jié)點(diǎn)中可以包括指針，指向其元素。11.單鏈表不能使用折半查找方法。20. 按插入后中序遍歷是遞增序列的原則，若某結(jié)點(diǎn)只有右子樹，而插入元素的關(guān)鍵字小于該結(jié)點(diǎn)的關(guān)鍵字，則會(huì)插入到該結(jié)點(diǎn)的左側(cè)，成為其左孩子。這種插入就不是插入到葉子下面。21. 從平衡因子定義看，完全二叉樹任結(jié)點(diǎn)的平衡因子的絕對(duì)值確實(shí)是小于等于1。但是， 平衡二叉樹本質(zhì)上是二叉排序樹，完全二叉樹不一定是排序樹。故不能

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

4、衡的二叉排序樹），或?yàn)榭斩鏄洌蚨鏄渲腥我饨Y(jié)點(diǎn)左子樹高度與右子樹高度差的絕對(duì)值小于等于Io12. 小于等于表長(zhǎng)的最大素?cái)?shù)或不包含小于20的質(zhì)因子的合數(shù)13. 1614. Lbg2nJ +115. （ 1） 45 （ 2） 45 （3） 46 （塊內(nèi)順序查找）16. k （ k+l） /2 17. 30, 31. 5 （塊內(nèi)順序查找）18. （1）順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)（2）順序存儲(chǔ)且有序（3）塊內(nèi)順序存儲(chǔ)，塊間有序散列存儲(chǔ)19. （n+1）/220. （n+1）/n*log 2（n+l）-l21.結(jié)點(diǎn)的左子樹的高度減去結(jié)點(diǎn)的右子樹的高度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.主關(guān)鍵字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四.應(yīng)用題1. 概念是基本知識(shí)的主要部分，要牢固掌握。這里只列岀一部分，目的是引起重視，解答略。2. (1)散列表存儲(chǔ)的基本思想是用關(guān)鍵字的值決定數(shù)據(jù)元素的存儲(chǔ)地址(2) 散列表存儲(chǔ)中解決碰撞的基本方法：%1開放定址法 形成地址序列的公式是：比=(H (key) +di) % m,其中m是表長(zhǎng)，心是增量。根據(jù)d,取法不同，又分為三種：a. 山=1,2,m-1稱為線性探測(cè)再散列，其特點(diǎn)是逐個(gè)探測(cè)表空間，只要散列表中有空閑空間，就可解決碰撞，缺點(diǎn)是容易造成“聚集”，即不是同義詞的關(guān)鍵字爭(zhēng)奪同散列地址。b. di =12, -I2, 22, -22,，±<

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

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

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

10、5520比較次數(shù)11123412平均查找長(zhǎng)度：ASL ECF (1+1 + 1+2+3+4+1+2) /8=15/8以關(guān)鍵字 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，關(guān)鍵字有8個(gè)，所以表長(zhǎng)為 8/0. 8=10,pj用除宦余數(shù)鈦.唔希顒數(shù)為衛(wèi)(key) -key 7(2)散列地址0123456789關(guān)鍵字21厲3D36254Q37比較歡數(shù)11 j31 .126計(jì)算畫找失敗甘的平均査扌戈長(zhǎng)度，泌嫌計(jì)算不柱表中的關(guān)鍵字WiWm

11、-1)時(shí)的查找次數(shù)。本例中m=10o故查找失敗時(shí)的平均查找長(zhǎng)度為：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 ； / 哈希函數(shù)用上面(1),即 H (key)二 key % 7if (hi= maxi nt) /maxi nt解釋成空地址printf ("無(wú)關(guān)鍵字 n” k) ； return (0) ； if (hi二二k) hi=-maxint ； return (1) ； /

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

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

14、定址法下，不能物理 地刪除, 只能作刪除標(biāo)記。該地址可能是該記錄的同義詞查找路徑上的地址，物理的刪除就 中斷了查找路徑。 因?yàn)椴檎視r(shí)碰到空地址就認(rèn)為是查找失敗。散列地址0I2345678910II12131415關(guān)鍵字14016827551920847923II10比較次數(shù)I2I43II39II313. (1)散列地址0I2345678910關(guān)鍵字412493813243221比較次數(shù)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值得指出，對(duì)用拉鏈法求查找失敗時(shí)的平均查找長(zhǎng)度有兩種觀點(diǎn)。其一，認(rèn)為比較到空指針?biāo)闶?。以本題為例，哈希地址0、2、5、7、9和10均為比較1次失敗，而哈希地址1和3比較2次失敗，其余哈希地址均為比較3次失敗，因此，查找失敗時(shí)的平均查找長(zhǎng)度為19/11,我們持這種觀點(diǎn)。還有另一種理解，他們認(rèn)為只有和關(guān)鍵字比較才計(jì)算比

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

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

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