資源描述：
《數(shù)據(jù)結(jié)構(gòu)第9章查找習(xí)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第9章習(xí)題課1.對(duì)于A[0..10]有序表,采用二分查找法時(shí),求成功和不成功時(shí)的平均查找長(zhǎng)度.并對(duì)有序表{12,18,24,35,47,50,62,83,90,115,134},當(dāng)用二分查找法查找90時(shí),需進(jìn)行多少次查找可確定成功;查找47時(shí)需進(jìn)行多少次查找可確定成功;查找100時(shí),需進(jìn)行多少次查找才能確定不成功.解首先構(gòu)造有序表A[0..10]的二分查找判定樹(shù)解首先構(gòu)造有序表A[0..10]的二分查找判定樹(shù)528012345678910013467910ASLsucc=(1*1+2*2+4*3+4*4)/11=3ASLunsucc=(4*3+8
2、*4)/12=3.67對(duì)于有序表528012345678910121824354750628390115134013467910對(duì)于有序表5028012345678910121824354750628390115134013467910對(duì)于有序表50248012345678910121824354750628390115134013467910對(duì)于有序表502490012345678910121824354750628390115134121835476283115134查找90時(shí),需進(jìn)行2次查找查找47時(shí),需進(jìn)行4次查找查找100時(shí),需進(jìn)行3次
3、查找9.2將整數(shù)序列{4,5,7,2,1,3,6}中的數(shù)依次插入到一顆空的二叉排序樹(shù)中,度構(gòu)造相應(yīng)的二叉排序樹(shù),要求用圖形給出構(gòu)造過(guò)程,不需要編寫(xiě)程序.插入44插入545插入74574572插入2插入145721插入3457213插入64572136設(shè)哈希表長(zhǎng)m=14,哈希函數(shù)H(keyy)=keymod11。表中已有4個(gè)結(jié)點(diǎn)addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,基余地址均為空，如用平方探查法處理沖突，求關(guān)鍵字49的結(jié)點(diǎn)地址。解h(49)=49mod11=5有沖突d1=(d0+12)mod11=6
4、仍有沖突d2=(d0+22)mod11=9無(wú)沖突答關(guān)鍵字49的結(jié)點(diǎn)地址為9
