散列習(xí)題課ppt課件.ppt

1、散列習(xí)題課,一、判斷正誤,（ ）1. p 是小于或等于 TableSize的最大素?cái)?shù) 。 （ ）2.取11位手機(jī)號(hào)碼key的后4位作為地址的 散列函數(shù)為：h(key) = atoi(key+9) 。 （ ）3.選擇合適的 h(key) ，散列法的查找效率期望是常數(shù)O(1)，它幾乎與關(guān)鍵字的空間的大小n無(wú)關(guān)！ （ ）4.散列方法是一個(gè)以空間換時(shí)間。 （ ）5.太小的可能導(dǎo)致空間浪費(fèi)，太大的又將付出更多的時(shí)間代價(jià)。,二、填空,1 .常用的處理沖突的方法有兩種：開(kāi)放地址法和鏈地址法。 2 . 發(fā)生了第 i 次沖突，試探的下一個(gè)地址將增加di，基本公式是：hi(key) = (h(key)+di) m

2、od TableSize ,其中di 取決于不同的解決沖突方案：線(xiàn)性探測(cè)時(shí)di i 、平方探測(cè)時(shí)di i2 、雙散列時(shí)di i*h2(key)。 3 .在開(kāi)放地址散列表中，刪除操作通常只能“懶惰刪除”，即需要增加一個(gè) “刪除標(biāo)記(Deleted)”，而并不是真正刪除它。 4.當(dāng)裝填因子過(guò)大時(shí)，解決的方法是加倍擴(kuò)大散列表，這樣可以減小一半，這個(gè)過(guò)程叫做“再散列”。 5.可能將不同的關(guān)鍵字映射到同一個(gè)散列地址上，即h(keyi) = h(keyj)（當(dāng)keyi keyj），這種現(xiàn)象稱(chēng)為“沖突”， keyi 和keyj稱(chēng)為“同義詞”。,三、選擇題,1.散列法存儲(chǔ)的基本思想是根據(jù) A 來(lái)決定 B ，碰

3、撞（沖突）指的是 C ，處理碰撞的兩類(lèi)主要方法是 D 。 供選擇的答案 A，B： 存儲(chǔ)地址 元素的符號(hào) 元素個(gè)數(shù) 關(guān)鍵碼值 非碼屬性 平均檢索長(zhǎng)度 負(fù)載因子 散列表空間 C: 兩個(gè)元素具有相同序號(hào) 兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同 不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址 負(fù)載因子過(guò)大 數(shù)據(jù)元素過(guò)多 D： 線(xiàn)性探查法和雙散列函數(shù)法 建溢出區(qū)法和不建溢出區(qū)法 除余法和折疊法 拉鏈法和開(kāi)地址法 答案：A B C D . ,四、簡(jiǎn)答題,1.簡(jiǎn)述為手機(jī)號(hào)碼建立一個(gè)散列表的方法。 2.簡(jiǎn)述影響產(chǎn)生沖突的三個(gè)因素。,五、分析題,1. 設(shè)哈希（Hash）表的地址范圍為017，哈希函數(shù)為：H（K）K MOD 1

4、6。K為關(guān)鍵字，用線(xiàn)性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，試回答下列問(wèn)題： 畫(huà)出哈希表的示意圖； 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？ 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？ 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。,（1）畫(huà)表如下： （2） 查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63 vs 31 ,no; 然后順移，與46,47,32,17,63相比，一共比較了6次！ （3）查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因

5、為12號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。 （4） 對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次； 對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， ASL=1/11（6233）17/111.55,2. 選取散列函數(shù)H（key）=（3*key）%11，用線(xiàn)性探測(cè)法處理沖突，對(duì)下列關(guān)鍵碼序列構(gòu)造一個(gè)散列地址空間為010，表長(zhǎng)為11的散列表，22，41，53，08，46，30，01，31，66。,則(22*3)%11=60 (41*3)%11=112 (53*3)%11=145 (08*3)%11=22 (

6、46*3)%11=126 (30*3)%11=82 (01*3)%11=03 (31*3)%11=85 (66*3)%11=90,3.已知散列函數(shù)為H(K)=K mod 12,健值序列為25，37，52，43，84，99，120，15，26，11，70，82，采用分離鏈接法處理沖突，試構(gòu)造散列表，并計(jì)算查找成功的平均查找長(zhǎng)度。 查找成功的平均查找長(zhǎng)度為：（4*2+8）/ 12 = 4/3,5.3設(shè)有一組關(guān)鍵字29,01,13,15,56,20,87,27,69,9,10,74，散列函數(shù)為H(key)=key%17,采用線(xiàn)性探測(cè)法解決沖突。試在018的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表，并計(jì)

7、算成功查找的平均查找長(zhǎng)度。 5.4題目同上，采用平方探測(cè)法解決沖突。 5.5設(shè)有一組關(guān)鍵字92,81,58,21,57,45,161,38,117，散列函數(shù)為H(key)=key%13,采用雙散列探測(cè)法解決第i次沖突：H(key)=(H(key)+i* H2(key)%13,其中， H2(key)=(key%11)+1 。試在012的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造散列表。,5.6已知線(xiàn)性表關(guān)鍵字集合21,11,13,25,48,6,39,83,30,96,108，散列函數(shù)為H(key)=K % 11采用分離鏈接法處理沖突，試構(gòu)造散列表，并計(jì)算查找成功的平均查找長(zhǎng)度。 5.7將關(guān)鍵字序列7,8

8、,30,11,18,9,14散列存儲(chǔ)到散列表中散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開(kāi)始的一個(gè)一維數(shù)組散列函數(shù)維：H（key）=（key3）% p，處理沖突采用線(xiàn)性探測(cè)再散列法，要求裝填因子為0.7。 （1）請(qǐng)畫(huà)出所構(gòu)造的散列表；（2）分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長(zhǎng)度。,解：表長(zhǎng)為10,p為7。 H（key）=（key3）% 7 （1） (2) 查找成功： ASL = (1+2+1+1+1+3+3) / 7 = 12 / 7 所以ASLu= （3+2+1+2+1+8+7+6+5+4）/ 10 = 39/10。,.已知某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字（標(biāo)識(shí)符）的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法為線(xiàn)性探測(cè)開(kāi)放定址法。試編寫(xiě)一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。 解：注意此題給出的條件：裝載因子a1, 則哈希表未填滿(mǎn)。由此可寫(xiě)出下列形式簡(jiǎn)明的算法： void PrintWord(Hash Table ht) /按第一個(gè)字母的順序輸出哈希表ht中的標(biāo)識(shí)符。哈希函數(shù)為表示符的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法是線(xiàn)性探測(cè)開(kāi)放定址法。 for(i=1; i=26;