單元8一、選擇題12345CCDCC678910CCDBC1112131415CBACD二、簡答題1.答：查找某個元素的時間復(fù)雜度下限，如果理解為最短查找時間，則當(dāng)關(guān)鍵值與表頭元素相同時，比較1次即可。要想降低時間復(fù)雜度，可以改用哈希查找法。此方法對表內(nèi)每個元素的比較次數(shù)都是O（1）。2.答：哈希法就是在記錄（數(shù)據(jù)元素）的關(guān)鍵字的值與其存儲地址之間建立某種函數(shù)關(guān)系H，通過函數(shù)計算，就能得到關(guān)鍵字的地址。按這個思想構(gòu)造的表稱為哈希表。3.答：哈希函數(shù)的構(gòu)造要求如下：函數(shù)應(yīng)是簡單的，能在較短時間內(nèi)計算出結(jié)果。函數(shù)計算出來的地址應(yīng)能均勻分布在整個地址空間中，以減少沖突。4.答：哈希沖突是指：不同關(guān)鍵字值對應(yīng)到相同的存儲地址。常用的解決沖突的方法有：開發(fā)定址法(線性探測法、二次探測法)和鏈表法。5.哈希表如下所示：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因為12號單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。對于黑色數(shù)據(jù)元素，各比較1次；共6次；對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55三、算法設(shè)計題1.注意此題給出的條件：裝載因子a〈1,則哈希表未填滿。由此可寫出下列形式簡明的算法：publicstaticvoidPrintWord(HashTableht){ intj; for(inti=1;i<=26;i++){ j=i; while(ht.hashItemArray[j].key){ if(Hash(ht.hashItemArray[j].key)==i) System.out.println(ht.hashItemArray[j].key); j=(j+1)%m;//m是表長 } } }2.publicvoidredo(intkey)throwsException{ this.tableSize=2*this.tableSize+1;//至少增加雙倍+1的存儲空間 while(true){//循環(huán)得到大于等于原哈希表長兩倍以上的最小素數(shù) inti; for(i=2;i<Math.sqrt(this.tableSize);i++) if(this.tableSize%i==0){ break; } if(i>Math.sqrt(this.tableSize)){//找到素數(shù)退出循環(huán) break; }else{ this.tableSize=this.tableSize+2;//繼續(xù)查找 } } HashItem[]tempHashItems; //tempHashItems暫存原來哈希表中的所有元素 tempHashItems=newHashItem[hashItemArray.length]; for(inti=0;i<hashItemArray.length;i++){ tempHashItems[i]=hashItemArray[i]; } this.currentSize=0; this.hashItemArray=newHashItem[this.tableSize]; for(inti=0;i<hashItemArray.length;i++){//對哈希表數(shù)組中的每個元素初始化 hashItemArray[i]=newHashItem(0); } for(inti=0;i<tempHashItems.le