資源描述：
《若對(duì)大小均為n的有序順序表和無序順序表分別進(jìn)行順序查》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第九章查找9.1若對(duì)大小均為n的有序順序表和無序順序表分別進(jìn)行順序查找，試在下列三種情況下分別討論兩者在等概率時(shí)平均查找長度是否相同？（1）查找不成功，即表中沒有關(guān)鍵字等于給的值K的記錄；（2）查找成功，且表中只有一個(gè)關(guān)鍵字等于給定值K的記錄；（3）查找成功，且表中有若干關(guān)鍵字等于給定值K的記錄，要求找出所有這些記錄。答：(1)相同，有序n+1;無序n+1(2)相同，有序；無序(3)不相同，對(duì)于有序表，找到了第一個(gè)與K相同的元素后，只要再找到與K不同的元素，即可停止查找；對(duì)于無序表，則要一直查找到
2、最后一個(gè)元素。9.3畫出對(duì)長度為13的有序表進(jìn)行折半查找的判定樹，并分別求其等概率時(shí)查找成功和查找不成功的ASL。答：查找成功：查找失敗：（P220:查找不成功的過程就是走了一條從根節(jié)點(diǎn)到外部節(jié)點(diǎn)的路徑，和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)等于該路徑上內(nèi)部結(jié)點(diǎn)個(gè)數(shù)）注：在折半查找判定樹中，查找不成功時(shí)的比較次數(shù)即是查找相應(yīng)外結(jié)點(diǎn)時(shí)與內(nèi)結(jié)點(diǎn)的比較次數(shù)。整個(gè)判定樹代表的有序表在查找失敗時(shí)的平均查找長度即為查找每個(gè)外結(jié)點(diǎn)的比較次數(shù)之和除以外結(jié)點(diǎn)的個(gè)數(shù)。例如，長度為10的有序表在查找失敗時(shí)的平均查找長度為： A
3、SL=(3×5+4×6)/11=39/11第二次作業(yè)9.4已知如下所示長度為12的表(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,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
4、.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（2）畫出初始為空，依次插入結(jié)點(diǎn)，生成的二叉排序樹（3）該二叉排序樹查找成功的平均查找長度。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）將二叉
5、排序樹中的結(jié)點(diǎn)Mar刪除，畫出經(jīng)過刪除處理后的二叉排序樹方法（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è)開放定址法處理沖突；（2）用鏈地址法處理。分別求這兩個(gè)哈希表在等概率情況下查找成功和不成功時(shí)的平均查找長度。設(shè)哈希表函數(shù)為H(x)=︱i/2︳,其中i為關(guān)鍵字中第一個(gè)字母在字母表中的序號(hào)。（1）線性探測(cè)法當(dāng)發(fā)生沖突時(shí)，線性探測(cè)法從沖突位置的
6、下一個(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ù)的期望值。等概率情況查找不成功的ASL=（13+12+…+1+4*1）/17=95/17（2）拉鏈法（鏈地址法）用拉鏈法處理沖突構(gòu)造
7、的散列表叫做開散列表等概率情況查找成功的ASL=（7*1+3*2+2*3）/12=19/12等概率情況查找不成功的ASL=（10*1+4*2+1*3+2*4）/17=29/179.7寫出判斷一棵二叉樹是否是二叉排序樹的算法，設(shè)二叉排序樹中不存在關(guān)鍵字值相同的結(jié)點(diǎn)二叉排序樹定義如下，二叉排序樹或者是一棵空樹；或者是具有下列性質(zhì)的樹。??1，若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值??2，若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值??3，它的左右子樹也分別為二叉排
8、序樹intlast=0,flag=1;intIs_BSTree(BitreeT)//判斷二叉樹T是否二叉排序樹,是則返回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ī)算
