北航計(jì)算機(jī)考研材料第9章查找答案_第1頁(yè)
北航計(jì)算機(jī)考研材料第9章查找答案_第2頁(yè)
北航計(jì)算機(jī)考研材料第9章查找答案_第3頁(yè)
已閱讀5頁(yè),還剩6頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論