散列習題課ppt課件.ppt

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

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

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

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

5、為12號單元為空（應當有空標記），所以應當只比較這一次即可。 （4） 對于黑色數(shù)據(jù)元素，各比較1次；共6次； 對紅色元素則各不相同，要統(tǒng)計移位的位數(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，用線性探測法處理沖突，對下列關鍵碼序列構造一個散列地址空間為010，表長為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，采用分離鏈接法處理沖突，試構造散列表，并計算查找成功的平均查找長度。 查找成功的平均查找長度為：（4*2+8）/ 12 = 4/3,5.3設有一組關鍵字29,01,13,15,56,20,87,27,69,9,10,74，散列函數(shù)為H(key)=key%17,采用線性探測法解決沖突。試在018的散列地址空間中對該關鍵字序列構造散列表，并計

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

8、,30,11,18,9,14散列存儲到散列表中散列表的存儲空間是一個下標從0開始的一個一維數(shù)組散列函數(shù)維：H（key）=（key3）% p，處理沖突采用線性探測再散列法，要求裝填因子為0.7。 （1）請畫出所構造的散列表；（2）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。,解：表長為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)為關鍵字（標識符）的第一個字母在字母表中的序號，處理沖突的方法為線性探測開放定址法。試編寫一個按第一個字母的順序輸出哈希表中所有關鍵字的算法。 解：注意此題給出的條件：裝載因子a1, 則哈希表未填滿。由此可寫出下列形式簡明的算法： void PrintWord(Hash Table ht) /按第一個字母的順序輸出哈希表ht中的標識符。哈希函數(shù)為表示符的第一個字母在字母表中的序號，處理沖突的方法是線性探測開放定址法。 for(i=1; i=26;