若對(duì)大小均為n的有序順序表和無(wú)序順序表分別進(jìn)行順序查

《若對(duì)大小均為n的有序順序表和無(wú)序順序表分別進(jìn)行順序查》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第九章查找9.1若對(duì)大小均為n的有序順序表和無(wú)序順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概率時(shí)平均查找長(zhǎng)度是否相同？（1）查找不成功，即表中沒(méi)有關(guān)鍵字等于給的值K的記錄；（2）查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值K的記錄；（3）查找成功，且表中有若干關(guān)鍵字等于給定值K的記錄，要求找出所有這些記錄。答：(1)相同，有序n+1;無(wú)序n+1(2)相同，有序；無(wú)序(3)不相同，對(duì)于有序表，找到了第一個(gè)與K相同的元素后，只要再找到與K不同的元素，即可停止查找；對(duì)于無(wú)序表，則要一直查找到最后一個(gè)元素。9.3畫(huà)出對(duì)長(zhǎng)度為13的有序表進(jìn)行折半查找的判定樹(shù)，并分別求其等

2、概率時(shí)查找成功和查找不成功的ASL。答：查找成功：查找失?。海≒220:查找不成功的過(guò)程就是走了一條從根節(jié)點(diǎn)到外部節(jié)點(diǎn)的路徑，和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)等于該路徑上內(nèi)部結(jié)點(diǎn)個(gè)數(shù)）注：在折半查找判定樹(shù)中，查找不成功時(shí)的比較次數(shù)即是查找相應(yīng)外結(jié)點(diǎn)時(shí)與內(nèi)結(jié)點(diǎn)的比較次數(shù)。整個(gè)判定樹(shù)代表的有序表在查找失敗時(shí)的平均查找長(zhǎng)度即為查找每個(gè)外結(jié)點(diǎn)的比較次數(shù)之和除以外結(jié)點(diǎn)的個(gè)數(shù)。例如，長(zhǎng)度為10的有序表在查找失敗時(shí)的平均查找長(zhǎng)度為：　　ASL=(3×5+4×6)/11=39/11第二次作業(yè)9.4已知如下所示長(zhǎng)度為12的表(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Se

3、p,Oct,Nov,Dec)每個(gè)元素的查找概率分別為（0.1，0.25，0.05，0.13，0.01，0.06，0.11，0.07，0.02，0.03，0.1，0.07）（1），Pi為查找表中第i個(gè)記錄的概率，ASL=0.1+0.25*2+3*0.05+4*0.13+5*0.01+6*0.06+7*0.11+8*0.07+9*0.02+10*0.03+11*0.1+12*0.07=5.43或者ASL=12*0.1+11*0.25+10*0.05+9*0.13+8*0.01+7*0.06+6*0.11+5*0.07+4*0.02+3*0.03+0.1*2+0.07=7.57（

4、2）畫(huà)出初始為空，依次插入結(jié)點(diǎn)，生成的二叉排序樹(shù)（3）該二叉排序樹(shù)查找成功的平均查找長(zhǎng)度。ASL=0.1+2*(0.25+0.05)+3*(0.13+0.01+0.06)+4*(0.11+0.07+0.02)+(0.03+0.07)*5+6*0.1=3.2（4）將二叉排序樹(shù)中的結(jié)點(diǎn)Mar刪除，畫(huà)出經(jīng)過(guò)刪除處理后的二叉排序樹(shù)方法（1）方法（2）9.5在地址空間為0~16的散列區(qū)中，對(duì)以下關(guān)鍵字序列構(gòu)造兩個(gè)哈希表：(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec)（1）用線性探測(cè)開(kāi)放定址法處理沖突；（2）用鏈地址法處理。分別求這

5、兩個(gè)哈希表在等概率情況下查找成功和不成功時(shí)的平均查找長(zhǎng)度。設(shè)哈希表函數(shù)為H(x)=︱i/2︳,其中i為關(guān)鍵字中第一個(gè)字母在字母表中的序號(hào)。（1）線性探測(cè)法當(dāng)發(fā)生沖突時(shí)，線性探測(cè)法從沖突位置的下一個(gè)位置起，依次尋找空的散列地址，即：Hi=(H(key)＋di)%m（di=1，2，…，m-1）。012345678910111213141516AprAugFebDecJanJunMarMayJulySepOctNov等概率情況查找成功的ASL=（5*1+3*2+5+4+6+3）/12=29/12查找不成功的ASL定義：查找不成功是需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值。等概率情況

6、查找不成功的ASL=（13+12+…+1+4*1）/17=95/17（2）拉鏈法（鏈地址法）用拉鏈法處理沖突構(gòu)造的散列表叫做開(kāi)散列表等概率情況查找成功的ASL=（7*1+3*2+2*3）/12=19/12等概率情況查找不成功的ASL=（10*1+4*2+1*3+2*4）/17=29/179.7寫(xiě)出判斷一棵二叉樹(shù)是否是二叉排序樹(shù)的算法，設(shè)二叉排序樹(shù)中不存在關(guān)鍵字值相同的結(jié)點(diǎn)二叉排序樹(shù)定義如下，二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有下列性質(zhì)的樹(shù)。??1，若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值??2，若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值

7、??3，它的左右子樹(shù)也分別為二叉排序樹(shù)intlast=0,flag=1;intIs_BSTree(BitreeT)//判斷二叉樹(shù)T是否二叉排序樹(shù),是則返回1,否則返回0{??if(T->lchild&&flag)Is_BSTree(T->lchild);??if(T->datadata;??if(T->rchild&&flag)Is_BSTree(T->rchild);??returnflag;}//Is_BSTree??根據(jù)遞規(guī)定義，如下的遞規(guī)算